Information for members of EIO organizing team
The main activities of EIO organizing committee are:
- Creating tasks for various contests, and organizing these contests.
- 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.
- Write the final statement for the task, and send it to the content coordinator.
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
- Beginners track
- 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
- Beginners track
- 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