Competitive Coding And Dreams Of Winning A Medal At The Olympics of Informatics
Hackathons everywhere, most weekends there's probably one near you. Hundreds of app developers competing for cash, trips, and seed capital.
This past weekend, AOL in Palo Alto (above), hosted angelHACK, where several hundred developers, mostly in their mid-to-late twenties, competed in small teams, over a sleepless 48 hours.
But those events are easy-peasy compared with international coding competitions, such as the qualifying rounds for the International Olympiad in Informatics, (IOI). Getting there involves grueling rounds of regional competitions with devilishly hard computational problems. You have to think hard, fast, and creatively. It's an experience that can transform good coders into great coders - or it can send you home feeling beaten and humbled.
What's great about competitions such as IOI is that knowing how to program is not enough. You have to think on your feet, you are forced to innovate, to tackle hard problems in different ways. Your brain, paper and pen are your main tools - coding is often the smallest part of the challenge.
Simon Hørup Eskildsen, a 17 year old Danish high school student, has written an excellent account of his experience in taking part in the regional competitions that make up the qualifying stages to the IOI in Italy, later this year. Or, as he puts it:
Simon started out at 10 years old, with some web site scripting languages: HTML and CSS, but it wasn't until he was 14 that he plunged into coding, teaching himself Ruby.
But knowing how to program is not the same as knowing how to solve problems - and that's what these competitions test.
Plus, there's always unexpected problems to solve even before you get to the competition.
Initially I thought the Nationals would conflict with my study trip to Barcelona in mid-March, but when the final dates regarding Barcelona were set, the possibility of making it only 8 hours late to the Nationals appeared.
This sudden change of plans meant I had to tackle the qualification round with almost no training. I also discovered all solutions had to be written in C, C++ or Pascal, none of which I knew.
A resourceful competitor never says never. Simon managed to quickly solve the first problem in the competition but the second one was much tougher.
The score in IOI-style competitions is based on speed, correctness and memory usage of your program. Furthermore it shows which errors occurred (wrong answer/timeout) during execution on different, unknown test cases.
A test case is a pair of input, data given to your program, and output, data expected to be given back by your program for the input. With 500 lines of horrible C code, I was proud to have implemented my "perfect solution".
When I uploaded it, I received just 25 points.
There was little time left to upload a new program, but he managed to try some different approaches and push his score above 30. But, and here's a great example of how to solve problems even if you aren't quite sure how to do it the right way:
I later found out what I had been trying to solve was an NP-hard problem (basically it means that the perfect solution can only be achieved in exponential time, growing by the length of input), without even knowing what an NP-problem was.
My program did find optimal solutions, but ran in exponential time, thus it did not receive maximum score because it timed out. You were supposed to find suboptimal solutions, however, not knowing about NP-problems I was certain I could find the optimum solutions (the better the solution, the more points, for this particular task)!
Although Simon was disappointed he didn't score the full 100 points for the second problem, he was encouraged that his thinking was on the right track. His creative approach got him noticed and in February, 2012, he got the call to take part in national competitions.
Here's the scene when he arrives very tired from a class trip to Barcelona. It's late at night and he's 8 hours behind all the others:
I was met by 9 guys completely claimed by their laptop screens. I was immediately given all the tasks the other participants were working on or had already completed, and were told they had had lessons in "Recursion" and"Divide and Conquer", I was familiar with recursion, but not Divide and Conquer...
Around 2 hours after my arrival at 10pm I was almost falling asleep writing my recursive routines, so I decided to close my eyes till we were all advancing to the sleeping quarters.
After breakfast on Saturday, I felt much more energized. The routine was that every 4 hours we'd be introduced to a new "programming concept", and receive ~2-6 tasks where this, combined with previously introduced concepts, had to be applied.
The tasks were incredibly challenging, like nothing I had ever tried before. Sometimes in extreme desperation combined with tiredness from the trip, I'd think about taking the next train home.
This feeling would disappear with the utter joy and confidence that arose whenever I would finally solve a task, and creep back once again when I found myself still struggling after an hour on a new problem. But this kept me going.
By Saturday afternoon, I had almost managed to get up to speed with the others, and were doing the same tasks as them.
Although Simon was pleased with his performance - coming back from an eight-hour handicap to draw level with the others, and then score 60 points - he believed his chances for progressing to the next stage, the Baltic Olympiads would be slim. However, when he later attended an event revealing the names of the Danish national teams, he heard his name.
I was flabbergasted. I took the train back home, happy that my informatics adventures were not over yet for this year.
Intellectual athletes have to train just like sports athletes. And he had just one week to prepare for the Baltic Olympiad.
I armed myself with a borrowed copy of "The Art of Computer Programming" [it's the programmer's "bible" written more than 50 years ago by Donald Knuth] working through the exercises, read up on common algorithms on Wikipedia, completed tasks on USACO [USA Computing Olympiad], and memorized the critical parts of my Vim config for the competition computers.
Now that I have you hooked on his story, find out how Simon did, and how he dealt with a multitude of challenges - not just computational - in Ventspils, a small town in Latvia. And read some of the lessons he learned in:
My problem-solving skills have increased tremendously. Coming from doing only Web development where the difficulties lie in structuring your application, it has been amazing to try and solve hard problems using algorithms and hours of thinking. It's so incredibly satisfying to solve a problem you've worked several hours on.
It opens many possibilities for me as a developer. Combining different algorithms and data structures, I can make applications I never dreamt of creating. It has a brought a unique and fundamental missing tool to my toolbox.
The Olympiad is coming up in September, in Italy. I'm looking forward to reading Simon's next chapter, and his dream of winning a medal at the Informatics Olympiad.
Above, Simon Hørup Eskildsen.