Ok, so many of you have heard about Informatics Olympiads from me or other people. But what exactly are these things? This is your quick survival guide.
At a glance. The IOI (International Olympiad in Informatics) is the Computer Science equivalent of the IMO (International Math Olympiad). Each country sends 4 high-school students, who spend 5 hours on 2 consecutive days solving problems (3 problems are assigned each day). This is an individual contest (no team rankings, no collaboration).
The problems. A typical problem looks like this: write a program that takes an input of n ≤ .... things (numbers, edges in a graph, whatever), and outputs ..... based on the input in less than ..... miliseconds. At the end of the 5 hours, each contestant submits 3 programs. The committee has prepared a bunch of tests for each problem, and the grading is entirely automatic -- your programs are run on all tests, and your score is the percentage of tests that where answered correctly within the given time bound.
The tests typically have a growing complexity (growing n). As a contestant, you reason like this: the problem says n ≤ 10000, and 50 miliseconds / test. An algorithm of complexity, say, O(n2) will definetely handle all tests; one of complexity O(n2lg2n) will probably also work for most tests (getting say 80% of the score); one of complexity O(n3) definetely runs out of time for the bigger tests, but still should get around maybe 50% of the score; an exponential algorithm 2O(n) will only get the very small tests (say 10% of the score).
Topics. The ideal problem is 90% algorithmic inspiration and 10% programming perspiration. The faster the algorithm, the more points you get, so the main challenge is algorithmic. It is assumed that contestants know a lot of algorithms theory (certainly anything in [CLRS] is fair game, and usually more). That is why you can't really trick the contestants by giving a problem where a classic algorithm applies. The good problems are very creative and contestants have to discover some interesting idea specific to the given problem.
An important requirement is that the solution needs to have an easy implementation. Programming should be a small component of the contest, and most of the 5 hours each day are spent thinking. The only important programming skill is that you can implement something correctly. A brilliant algorithmic idea plus a bug will not earn you points, because the program will output incorrect results...
Tuesday, August 14, 2007
Informatics Olympiads (I): The Contest
Subscribe to:
Post Comments (Atom)
![[home]](http://people.csail.mit.edu/mip/images/home.gif){kind=small}
6 comments:
So Michael had talked about including programming assignments in an algorithms class, and I had pointed out the difficulty of finding good questions (that challenge students' abilities without obscuring the problem with the code).
Do you think problems from past Olympiads might be suitable as assignments in an algorithms class ? with basically the same setup (i.e your code must run in so and so time, for values of n at most blah)
Oh yes, I'm convinced they make excellent programming assignments, and that we are doing ourselves harm by not assigning such problems.
We should realize that people have perfected the art of such problems over almost 20 years of olympiads, and should learn from them.
There is a huge collection of good problems. Give me a couple of days to do some data gathering, and I promise to post a few samples.
That would be great. I'd definitely use some in a class if I had such examples.
The only catch is that at least for 2005, the solutions were also available at the same website :)
Another minor complication would be implementing the server, or some environment that could create the artificial memory-capped world that the code needs to run in. But I see excellent opportunities for undergrad projects.
Virtually all solutions are available, but again there are thousands of problems. Change the text and don't quote the source :)
As for the grading system, one of my "community service" projects was to write one... It has been used in many Romanian olympiads, and at the Balkan Olympiad 2003, so it is fairly well tested and secure.
I guess one question is: how is this different from the ACM programming contest ?
Not only the ACM programming contest -- there are a bunch of other important contests that you should know about. I promise to address the question soon in another installment of this practical survival guide :)
Post a Comment