Programming Contest Resources
I started doing programming contests in high school, in grade eleven. That year, I wrote the Canadian Computing Competition and, to my surprise, was put on the 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 went on to win a silver medal at the IOI that year and another the next. In college, I was on Waterloo’s team for the ACM programming contest, which placed 15th in the world in 2004 and 4th in the world and 1st in North America in 2005. Individually, I also placed 15th in the 2005 Google Code Jam. I found programming contests to be great fun and also an excellent way to learn algorithms, data structures, and how to write correct and efficient computer programs.
I’ve written this page to provide interested students with a concise list of resources for getting into programming contests and getting something out of them. Hopefully it is helpful to both high school students just getting into computer science and college students looking for some practice problems and tips.
Tutorials, Books and Problems
Here are a few resources I found useful, roughly in the order in which I looked at 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.
- Finally, 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. SGI’s site is a good reference for the C++ standard library. Some versions of the standard libraries also contain hidden gems - for example, there is a GCD function in GCC.
Here are a few of the more surprising tips I found useful. These apply not just to contests but to programming efficiently and correctly in general:
- Always write code in such a way that you have something “testable” at each step. This is just good programming practice. 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 the interactive debugger. It’s faster, and the output stays around for you and everyone on your team to look at.
- Print code when you can’t figure out why it’s broken. Print debug output too. The printer has a magic property of making bugs stand out. Well, maybe not quite, but I can’t count how many times I couldn’t figure out a bug by testing the program, then had it immediately jump out on paper. People are just much better at reading paper than monitors.
- Finally, a lot of people ask about languages. While many languages work fine in contests, if I had to suggest one, I’d say learn C++. It seems to be the least clunky one to write code in that provides full control when you need it. Just make sure you also know a language with big integers and regular expressions in its standard library, such as Java, in case some problem requires those.