# 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) - 3 difficulty groups with 3 tasks each
- Olympiad final round (mid-February) - 3 difficulty groups with 3 tasks each
- National team selection (March-April) - 2 days with 3 tasks each.
- Also, we are expected to submit a task to BOI.

Total of 32 tasks per season.

### Task creation process

Our process is following:

- The organizing team meets about a few weeks before the contest.
- Before that (as a matter of fact, you can do it any time), people are encouraged to send task ideas to the EIO mailing list.
- 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 text 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, input1.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 name of the input file is short_name+'sis.txt' and the name of the output file short_name+'val.txt'.
- In sample solution, include comments describing the solution idea and algorithms that were used.

- Write the final text 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).

### 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 colution, you can do 40%-30%-30% etc.

### Creating custom checkers

If the output of the task is always the same, you don't need to write a checker. However, if there are multiple possible solutions, you can create a custom checker to assess the solution's correctness.

- The checker must compile to an executable, which takes three parameters <input file> <true output file> <student's output file>, and outputs:
- "1" to the stdout if all is fine
- "0" to the stdout if all is not fine

- The script should also write a descriptive message to the stderr (e.g. "OK" or "Wrong answer").
- 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.
- Two weeks before contest. Team meets to discuss ideas and assign owners.
- One week before contest. Task owners send text, solutions and tests to content and tech coordinators.
- Two days before 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://uva.onlinejudge.org/ is a good resource.

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 trakcs 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 precisions.
- 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,
- queue,
- binary search tree.
- Library classes for various data structures in Python, Java, C++

- Algorithm complexity. Standard 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 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 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.
- Text algorithms
- Parsing
- Hashing based quick substring comparison.
- Knuth-Morris-Pratt algorithm.
- Aho-Corasick algorithm
- Suffix Arrays

- Geometric algorithms
- Checking for colinear 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.
- O(n log n) time algorithms for convex hull
- Sweeping line method

- Matrix algebra
- UVA: 10229, 11582

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