Matei Zaharia / Programming Contests

Programming Contests

I started doing programming contests in high school, in grade eleven. That year, I wrote the Canadian Computing Competition and, to my surprise, was selected to the Canadian team for the International Olympiad in Informatics. I'd mostly been learning programming informally on my own until then, so that summer I read a lot about algorithms from the books provided to the team, and learned some actual computer science ;). I ended up getting a silver medal at the IOI that year and next (2002 and 2003). I continued doing contests in college with the 2005 ACM Programming Contest, where my team at the University of Waterloo placed 4^th in the world and 1^st in North America in 2005. I also did some individual contests in college, the most successful of which was the 2005 Google Code Jam where I was 15^th. Unfortunately, but also thankfully, the ACM doesn't let students compete in more than two finals, so I stopped doing contests soon after 2005 and moved on to other things. I've written this page to point other interested people to good resources for getting into programming contests and getting something out of them.

Resources

Here are a few resources I found useful, roughly in the order in which I looked at them:

First of all, be familiar the standard library for your language, especially data structures (lists, hashtables, etc). The easiest way is to look at the documentation for some examples of each one and just play with them.
The USA Computing Olympiad Training Program provides a great online set of problems in increasing difficulty, with an automatic judge for testing out your solutions. It's designed sequentially unlike other problem archive sites that just have a lot of problems.
Algorithms in C (and its equivalent books in Java and C++) is great for learning algorithms while also learning practically how to implement them. It's a good learning book if you have little background in algorithms and also a good reference.
Introduction to Algorithms (the big green book) has all the advanced algorithms you'll want to know about. It's pretty mathematical though and doesn't have much on implementing these rapidly and effectively.
The University of Valladolid has a huge archive of past ACM questions with automated judging.
TopCoder.com runs weekly contests and has a huge problem archive. The problems there are shorter than typical ACM and IOI problems, and some of them are kind of tedious ("just code it and pay attention to all the cases"), but overall it's quite useful and you also get automated judging.
Of course I have to plug Waterloo's ACM Practice Contest Site, which contains a lot of interesting problem sets and test data and also does a contest available internationally though UVA twice a term.

Tips

Here are a few things I found surprising but very useful:

Always write code in such a way that you have something "testable" at each step. This is just good programming practice in general. Too many beginners start writing a huge program in pieces and get lost, then finally put it together, discover that it doesn't work, and can't figure out which of the pieces is causing it. Instead, do iterative development where you first read some input, then print results for some intermediate computation, etc. You'll have confidence in stuff you've written earlier and you'll be making progress at each step.
Debug using print statements, not an interactive debugger. It's faster and the output is around for you and everyone on your team to look at.
Test everything, even things you believe should work. Keep tests around. This is another way in which doing contests teaches you a useful skill for real-world development.
The printer is your friend. It's like a pair of X-ray goggles that makes bugs stand out when you print your code. Maybe not quite, but I can't count how many times I couldn't figure out a bug by playing with my program, then printed it and immediately had it jump out. People are just better at reading paper.