What are some good competitive problems for a programming contest?

What types of programming contest problems are there?

• Basically, I want to make a great reference for use with programming contests that would have all of the algorithms that I can put together that I would need during a contest as well as sample useage for the code. I'm planning on making this into a sort of book that I could print off and take with me to competitions. I would like to do this rather than simply bringing other books (such as Algorithms books) because I think that I will learn a lot more by going over all of the algorithms myself as well as I would know exactly what I have in the book, making it more efficient to have and use. So, I've been doing research to determine what types of programming problems and algorithms are common on contests, and the only thing I can really find is this (which I have seen referenced a few times): Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are: Dynamic Programming Greedy Complete Search Flood Fill Shortest Path Recursive Search Techniques Minimum Spanning Tree Knapsack Computational Geometry Network Flow Eulerian Path Two-Dimensional Convex Hull BigNums Heuristic Search Approximate Search Ad Hoc Problems The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms - or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are ``obvious''. Now that's good and all, but that study was conducted in 1999, which was 13 years ago! One thing I know is that there are no BigNums problems any more (as Java has a BigInteger class, they have stopped making those problems). So, I'm wondering if anyone knows of any more recent studies of the types of problems that may be seen in a programming contest? Or what the most helpful algorithms on contests would be?

• Answer:

  Been there, done that. My experiences with these contests are from the early 2000s, so still some 8-9 years old, but I hope I may still provide you with some insights. I can definitely agree on this list, however, these entries are almost never suited for bringing along an implementation on paper. Several of these "problems" are far from always being the same, but rather are a technique or problem-area. That being said, some are very specific algorithms, which do make sense to prepare ahead of time. Here are some algorithms, that we found most profitable to bring along: Network flow computation - lengthy non-trivial code for implementation, yet applicable to numerous problems Convex Hull - again a stable Voronoi diagrams - falls into the "computational geometry" problem area We did take along many more than that, but most often did not make use of them. The "problem" with these kinds of problems is that you can never solve them with existing code and need to adapt for each individually. The complexity/difficulty of the adaptation itself is way beyond the difficulty of implementing the simpler algorithms, hence, the limited use of a prepared implementation for a specific purpose. Let's take a few examples from your list and look at them in more detail: Dynamic Programming: This is a whole class of problems, which basically just share an array. I am pretty damn sure that you know how to create an array. Everything else you bring along will be useless though, because each DP problem has a different recursion formula. Finding that formula is the actual problem, writing it into code fast and correctly is simply a matter of practice. Greedy: An algorithm technique. Again, the problem is not implementation, but ensuring that your problem has the desired properties to be solvable with a greedy approach. Once you acertained that, the rest only needs practice again. Complete Search: another technique. You should know by heart how to write DFS/BFS and the like, yet the problem is again not the implementation. It's about how to design your search space and search function. and so on and so forth. From the whole list, only the following entries lend themselves to a prepared solution: Minimum Spanning Tree - but it's so simple, that practice experience makes you implement it as fast as copying it from the paper. Network Flow - as said above, this one may be worth it Eulerian Path - a bit more involved, but very small ROI as it is seldomly needed Convex Hull - see above. There is a whole different aspect though if you happen to work on the contests in a team - and if you are a student still, I highly suggest you do that, or find/create a team ASAP. At my alma mater we had several competition teams and a history of teaching. The better students/teams gave lessons and advice to the new students (often because we were no longer allowed to compete in some competitions due to rule limits). Once you have such a legacy, it does make much more sense to provide default implementations of various algorithms. However, you do not use them during competitions, but rather as an aid in your preparations.