Last Wednesday, I participated in the fourth edition of the Vlaamse Programmeerwedstrijd (VPW), hosted by PHL in Hasselt. The VPW is a Flemish programming contest inspired by the ACM International Collegiate Programming Contest (ICPC). Participants compete in teams of 3 and are divided into three different categories: high school students (category I), undergraduate students (category II), and graduate students or professionals (category III). Teams get 3 hours to solve 5 problems in one of 12 supported programming languages, using a single computer.
My team competed in category III and consisted of myself and two colleagues. Our main motivation was fun, and curiosity of how well (or bad) we would do. Also, since I was encouraging students to participate, it wouldn’t hurt to set an example by participating myself too.
Or so I thought Our team eventually did not do well, as we only managed to correctly solve 1 out of 5 exercises. There was a big gap between the top 5 and the other teams in our category. Only the teams ranking 1st and 2nd correctly solved all problems. The 3rd team solved 4 problems, the 4th and 5th ranked teams solved 3 problems, and from then on teams only solved 2 problems or less (four teams didn’t solve any problems). All except 1 team in the top 5 already participated in this contest before. This year’s winner actually ranked 21st last year in the Northwestern European Regional Programming Contest (NWERC), which is a European contest that serves as a qualifier for the ACM ICPC World Finals. By the way, kudos to the two teams of Master’s students from our university who managed to rank 7th and 9th (and beat us too).
Nevertheless, I had a lot of fun participating. I think I have a better idea now of what matters in this kind of contest and how we could do better in the future. Here is a quick list of factors that I feel are important:
Speed
You have to work really fast. Teams get 3 hours for 5 problems, which comes down to 36 minutes per problem. That includes reading the problem description, thinking about the solution, actually coding it up and verifying that it works!
You can bring notes, books and existing code along (although, obviously, you are not allowed to use the web), so it makes sense to build your own library of useful algorithms and data structures which you can use, either written down on paper or available in code. This includes things like graphs, trees, DFS, BFS, backtracking, the Sieve of Eratosthenes, Dijkstra and Floyd-Warshall. For example, we skipped one of the problems since we didn’t have a well-tested data structure available for it. Of course, you should also understand these algorithms and data structures and know when to use them.
Since speed is important, this means you have to be proficient in the language you’re using. You don’t have time to look up how a certain feature works, so make sure you know how to read input (obviously), how to work with built-in data structures (e.g. lists, strings, dictionaries, stacks, tuples) and how to perform common operations (e.g. copying containers, mathematical operations on numbers, replacing characters in strings, regex matching). We used Python, which has a few nice features such as built-in eval (useful for evaluating strings of mathematical expressions with the right operator precedence), easy I/O, list comprehensions, built-in combinations and permutations functions, while also being easy to learn. I heard that most of the top-scoring teams were using Haskell.
Know about Time Complexity
This is really essential. You have to be able to quickly assess the time complexity of your algorithm and decide whether it will good enough. Most problem descriptions include upper bounds on their inputs, which you should take into account (even if the example input is very small). This helps you to discard inefficient algorithms, and gives you more time to work out a better one. Most programs will have to perform well on large inputs, which means you will usually have to do better than O(N^2).
We made this mistake twice, because we were stressing over the amount of time left and wanted to quickly code up a working solution. While you can optimize your code, you don’t have time to change your algorithm when you have just finished a working (but slow) solution. With about 25 minutes left, we had a working version for one of the problems, but didn’t succeed in optimizing that solution further to avoid exceeding the time limit for the contest input. So eventually, we didn’t get any points for our solution. What we should have done instead was think about the time complexity of our algorithm first, and then discard it when we would have noticed that it didn’t scale.
Moreover, C, C++ (and Java) have an advantage over scripting languages in terms of performance, since a suboptimal algorithm in C/C++ (e.g. O(N^2) instead of O(NlogN)) might get very close to the time limit but could still be fast enough. The same algorithm implemented in a scripting language will almost always be too slow. If you’re programming in Python, just try running your code with CPython and PyPy to see what I mean. Here’s an example of running naive matrix multiplication (takes cubic time) of two randomized 500×500 matrices in CPython versus PyPy:
$ time python n3matrix.py 500
real 2m30.598s
user 2m30.189s
sys 0m0.068s
$ time pypy n3matrix.py 500
real 0m13.244s
user 0m13.137s
sys 0m0.064s
The PyPy version runs in 13 seconds and would probably not exceed the contest time limit, while the CPython version takes a whopping 150 seconds! Even though there are great libraries for matrix operations in Python (hello NumPy!), this still matters since most programming contests don’t allow the use of external libraries.
Here’s a similar example of sorting a list of 10.000 elements using bubble sort (a quadratic algorithm):
$ time python n2sort.py 10000
real 0m38.837s
user 0m38.730s
sys 0m0.016s
$ time pypy n2sort.py 10000
real 0m2.284s
user 0m2.192s
sys 0m0.036s
Of course, one could also argue that scripting languages allow you to implement and debug a solution more quickly than C/C++, but I guess it all depends on how fluent you are in your language of choice.
Teamwork
Although you work in teams of 3 people, you can only use one computer, which means only one person at a time can do the actual coding. You will have to divide tasks. For example, one team member could try to get a head start on the next problems, or could sort problems in order of difficulty to select the next problem to work on collectively. I think this actually worked quite well in our team.
In our case, it helped to have the fastest programmer/typist on the keyboard most of the time, although we did switch several times when someone had an idea they wanted to try. If you switch a lot, make sure you standardize somewhat on the setup you use, or at least allow easy switching between tools. We made sure we had different editors on the laptop set up to work in a way that the other team members were comfortable with. Because we used Python, we also had to standardize on the number of spaces used for indentation.
Practice and Study
Finally, the best way to get better is by practicing (exemplified by the number of top-scoring teams who also participated in previous editions of the contest). You can practice on problem sets from previous years or online problems sets (e.g. Project Euler, UVA, or SPOJ). Once you get better, it will probably also help to practice problems in contest conditions: as a team, with a time limit and just a single computer.
However, just practicing more probably won’t cut it. You are also going to need a good reference book on algorithms to look up problems, and suitable algorithms or heuristics for these problems. Since you won’t have enough time to read through books during the competition, you need to have this knowledge in your head (i.e. by putting the theory from the books into practice). I think you can only get better through a combination of theory and practice: studying different techniques and applying them in solutions to programming problems. Books on algorithms and data structures that I liked myself are: Skiena’s The Algorithm Design Manual, CLRS and Sedgewick’s Algorithms.
Of course, these are just my own observations, so comments are always welcome!
