What types of programming contest problems are there?
- by Alex
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?
