Algorithmic problems which involve showing that it is possible to achieve some task (rather than finding invariants or proving impossibility). Features selected problems from the IOI, so some CS background is helpful but not necessary.
As avid combinatorialists may note, there is a large intersection between computer science and combinatorics. This unit highlights that intersection by focusing on algorithm-based combinatorics problems.
Despite the emphasis on computer science and the IOI, the unit is quite relevant to the math olympiad, and has more math related questions than IOI ones. Don't be afraid to try it!
In addition, knowledge of programming is NOT required, although you may assume otherwise.
This unit is available on D and Z levels.
Notable Problems
-
IMO 2010/5 Can't spoil it, would ruin the fun.
-
Russia 2005/9.6 Honorable example of greedy algorithm in math contests.
-
SL 2001 C4 Historic example(pun intended).
-
IMO 2017/3 Included as one of the walkthroughs, also from the OTIS application. Not as hard as the legends say it is.
-
IMO 2019/3 One of the 9-pointers. Graph algorithm with weird condition, one of the hardest problems in the unit.
Additional Notes
-
Familiarity with well known algorithms, e.g. greedy, knapsack is helpful. Graph theory is also heavily used in the unit.
-
If you know C#, C++ or Python, you can attempt the problems with code on an online judge.
-
There is an optional concept discussion regarding NP-completeness. It's fun!
-
IOI (International Olympiad in Informatics) is a prestigious contest in computer science. It is effectively the IMO for informatics.