My road to the International Olympiad in Informatics 2012
My name is Bouke van der Bijl, a 17 year old Dutch computer enthusiast. In the coming september I will be participating in the International Olympiad in Informatics. This is how I qualified.
At my school everyone is encouraged to participate in the Dutch Mathematics Olympiad and like every year, I joined and this year I happened to make it to the second round. It was there that I found a brochure that portrayed all the Dutch Olympiads, including the Informatics one. The Nederlandse Informatica Olympiade or NIO has three rounds: one online round in which all secondary students can participate, a second on-site round for the best of those and a third final round to decide who will represent The Netherlands at the IOI, with only four people qualifying!
Online qualifications (Q4 2011 - Q1 2012)
The first round consisted of a few tasks including a game of battleships in which your program would be pitted against that of other participants and you would be awarded points based on your relative performance. For this particular program I went the lazy route: I copied the behavior of the example implementation and improved it a little bit. I managed to achieve an almost perfect score, with my program defeating the majority of the competition. You can read the description of the problem here and my solution in Python here, including a description of the algorithm.
One of the other problems in the first round was the game Bao, for this your program also had to battle it out against the other programs. I only implemented the rules and let my AI decide at random, this in combination with the first problem and the others (which I frankly have forgotten about) gave me 212 of 300 points which was enough to advance to the second round.
The first on-site round (24th of March 2012 at the UT)
The second round took place at the University of Twente, featuring the 20 best students from the online qualification round. This round consisted of two categories consisting of multiple each.
The first category was the division of items where each item has a specific value, known as the "Partition problem". The first few problems gave you the description of an algorithm which you then had to implement yourself, with points being awarded based on how well your implementation followed the instructions.
For the last problem in this category you had to think of an algorithm yourself that would find a fair division. Experienced (competitive) programmers would immediately know that this is a NP-hard problem with a pseudo-polynomial solution. At this point I did not know about this (or even what these terms mean) so I tried implementing a naive algorithm (which I later found out is called Greedy) but due to mistakes my solution did not fare that well.
The second category was string processing consisting of problems like checking whether a string is in a dictionary, finding the amount of syllables and finding overlapping words. I ended fifth in this round and got to the finals with 11 other students!
Preparations for the final round
In preparation of the final round we got three days of algorithmic training. This included topics like Greedy algorithms, Dynamic Programming, Graph theory, recursive backtracking etc. This training was really interesting and I felt it really stepped up my programming game. Before this training I knew nothing about algorithms or time complexity but after I got a very good base from which I could expand my programming knowledge.
An example of stuff with a 'practical' use are Tries to find the best words in the game Rumble and display them from longest to shortest, you can find the code here.
The weeks leading up to the final competition day I tried my very best to solve one or more problems every single day on the USACO training page.
The final on-site round (11th of June 2012 at the TU/e)
The final round itself was kind of a disaster. I thought it went really bad for me, but so did the rest which kind of gave me hope, although I didn't expect much pf it. But when we received the results it turned out I actually scored best!
Apparently the final round was much harder than usual, with half of the students scoring only 10 points or less, while I scored 135/400 putting me first and earning me a trophy that I can keep for one year.
Next
In September I will be flying to Italy, joining about 400 other students at the IOI http://www.ioi2012.org/, hoping to win a medal at one of the largest and hardest programming competitions out there. Back to training!
If you found this article interesting, consider reading My journey to the International Olympiad in Informatics by Sirupsen too!
Aug 2012