Information for members of EIO organizing team

The main activities of EIO organizing committee are:

1. Creating tasks for various contests, and organizing these contests.
2. Organizing workshops ("õppesessioonid") for students to learn about contest programming.

Tasks and contests

There are 4 main contests during the school year:

• Estonian Open (in October) - usually 7 tasks
• Olympiad preliminary round (early December) - usually 5 tasks from which each contestant picks 3 to solve
• Olympiad final round (mid-February) - usually 5 tasks from which each contestant picks 3 to solve
• National team selection (March-April) - 2 days with 3 tasks each
• Also, we are expected to submit a task to BOI

Total of 24 tasks per season.

Task creation process

Our process is following:

• Before a contest round (as a matter of fact, you can do it any time), people are encouraged to send task ideas to the EIO mailing list and/or "task pile" (https://efo.herokuapp.com/). Ask Targo/Ahto/Sandra for permissions to the site.
• The organizing team meets a few weeks before the contest.
• In the meeting, we choose the tasks, and assign them to members of the organizing team. It is common to assign the tasks to idea authors themselves.
• Also, we choose the technical administrator (usually Kostja) and content coordinator (usually Ahto) of the contest.
• Task owners:
  • Write the final statement for the task, and send it to the content coordinator.
    • Take care to specify the formats and limitations of inputs and outputs as clearly as possible.
    • You can write the text as plain text or use TeX.
    • Note that each task needs a longer title (that will be translated) and a shorter (usually 2-3 letters) name (that will be used by the grading system).
  • Create a set of test cases, and send it to the technical admin.
    • Test cases should be text files named input0.txt/output0.txt, input1.txt/output1.txt etc.
    • The list of test cases should start with the examples from the task text.
  • Write a sample solution for the task, and send it to the technical admin.
    • The solution should read from standard input and write to standard output.
    • In sample solution, include comments describing the solution idea and algorithms that were used.

Creating a good task

For beginners, it is fine to use any creative programming task (example: count valid moves for a chess piece).

For advanced tasks, anything covered by IOI syllabus is fair game. Usually, there would be a brute-force method of solving the problem, and a clever algorithm method. The best tasks have multiple tiers of possible solutions (e.g. O(2^N), O(N^3), O(N*logN) complexity).

"Implement a well-known standard algorithm" is not a good task. A good task should either have an interesting and somewhat original solution idea or a "natural" statement.

Creating tests

Make your tests as thorough as possible, covering various special cases, minimum/maximum inputs etc. If your task has multiple possible solutions with different complexity, make sure the scoring reflects it.

For example, if there's a brute force solution and a clever solution then a good rule of thumb is to give 50% of points for the brute-force (but correct) solution, and 50% for the fast solution. I there's a slow, medium and fast solution, you can do 40%-30%-30% etc.

Creating custom checkers

If the correct output is unique in all test cases, you don't need to write a checker. However, if there are multiple possible correct outputs, we need a custom checker to assess the solution's correctness.

• The checker must compile to an executable that takes three parameters <input file> <correct output file> <student's output file>, and outputs the score to standard output as a number from 0 to 1 indicating the fraction of the value of the test case the solution earned (most common are 0 for nothing and 1 for full score; however, some tasks may also allow partial scores).
• The script should also write a descriptive message (e.g. "OK" or "Wrong answer") to the standard error stream.
• The return code must be 0 in any case.
• The checker must survive any garbage output that the solution might create.

Sample contest timeline

• Any time before contest. Team members send ideas to EIO list or to the "pile".
• Three-four weeks before the contest. Team meets to discuss ideas and assign owners.
• One-two weeks before the contest at the latest (preferably earlier). Task owners send text, solutions and test data to content and tech coordinators.
• A few days before the contest. Content owner sends final versions of the texts for review.
• CONTEST TAKES PLACE.
• Same day: publish all texts, tests, sample solutions and preliminary results.
• Appeals (up to one week for Estonian Open and the preliminary round, same/next day only for other contests).
• Final results published.
  • For results, include students' name, school, and class.

Workshops

Workshops usually have 6 academic hours of work per day. Ideally, about 40% of time would be spent by the lecturer, explaining the material, and 60% would be spent on practical work. Seek out sample problems for the topics; https://codeforces.com/ and https://uva.onlinejudge.org/ are good resources.

Below is a sample division of topics between the workshops. This is not set in stone; bits and pieces may be shifted around. The "UVA" tag denotes task numbers at https://uva.onlinejudge.org/

Traditionally, we have organized the following workshops:

• Fall workshop in November. One weekend with separate tracks for beginners and advanced, total of 12 academic hours per track.
  • Beginners track
    • Analysis of Estonian Open
    • Basics of contest programming
      • Input/output to files and std
      • Data types, their limits and precision
      • String storage
      • Subroutines
      • Recursion; divide and conquer; recursive backtracking
    • Sorting and searching
      • Bubble sort
      • Quicksort
      • Binary search
    • Brute force (exhaustive search)
      • UVA: 861, 10237, 10128, 10270
    • Dynamic programming basics
      • Top-down DP (memorized recursion)
      • Bottom-up DP
  • Advanced track
    • Analysis of Estonian Open
    • Greedy algorithms
    • Advanced dynamic programming
      • Edit distance
      • Travelling Salesman
• Winter workshop in January. Similar structure to the fall one.
  • Beginners track
    • Preliminary round tasks analysis
    • Basic number theory: Euclid's algorithm; sieve of Eratosthenes; efficient exponentiation
      • UVA: 10110, 10035, 10127, 10104, 10202, 10929
    • Basic data structures
      • List
      • Heap
      • Stack and queue
      • Binary search tree
      • Library classes for various data structures in Python, Java, C++
    • Algorithm complexity; common complexity classes (constant, logarithmic, linear, O(n log n), quadratic, cubic, exponential, factorial); time and space tradeoffs in algorithms
    • Basic graph theory
      • Graph theory terms; trees and their basic properties
      • Representations of graphs: adjacency matrix, adjacency list, edge list
      • Graph traversal: DFS, BFS
      • Flood fill
      • Topological sorting
      • Weighted and directed graphs; Dijkstra's algorithm
  • Advanced track
    • Preliminary round tasks analysis
    • Advanced data structures
      • Binary indexed trees (Fenwick trees)
      • Segment trees
      • O(log n) time algorithms for answering lowest common ancestor queries in a static rooted tree
      • 2-D Fenwick trees
      • Lazy Propagation in segment trees; O(log n) algorithms for range assignment, operating (like addition) and queries
      • UVA: 11402, 12086
    • Advanced graphs
      • Topological sorting
      • Spanning tree, Kruskal's algorithm, union-find
      • Finding Euler cycle
      • Floyd-Warshall algorithm
      • Bipartite graphs
      • Max flow/min cut
      • UVA: 00599, 10895, 11991, 00793, 10507, 11503, 820, 11045, 10480
• Estonian team preparation in March. Usually together with the team selection contest.
  • Combinatorics and counting: binomial coefficients; Minimax search
  • Text algorithms
    • Parsing
    • Hashing based quick substring comparison
    • Knuth-Morris-Pratt algorithm
    • Aho-Corasick algorithm
    • Suffix Arrays
  • Geometric algorithms
    • Checking for collinear points, parallel/orthogonal vectors, clockwise turns
    • Intersection of two lines
    • Computing area of a polygon
    • Checking whether a (general/convex) polygon contains a point
    • Coordinate compression; weeping line method
    • O(n log n) time algorithms for convex hull
  • Matrix algebra
    • UVA: 10229, 11582

See also: https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf