Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
I dont know any reasearches, but if you want to complete your list, you could add "Number Theory" (prime numbers, generation of sequences). Project Euler is mostly based on that problems. –  matcauthon Nov 8 '12 at 8:05
    
I think sorting and cryptography would have interesting problems too, though not sure if they are actually used anywhere. –  thorsten müller Nov 8 '12 at 8:08
    
There are exactly two kinds of problems: those you've seen before and those you haven't. –  Blrfl Nov 8 '12 at 11:14
    
Why is "Two-Dimensional Convex Hull" listed separately from "Computational Geometry"? –  Peter Taylor Nov 8 '12 at 13:59
add comment

closed as not constructive by gnat, World Engineer, Blrfl, Walter, Robert Harvey Nov 8 '12 at 16:16

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
    
Thank you for that explanation, I put more focus on getting algorithms for Minimum Spanning Tree, Network Flow, Euclidean Path, and Convex Hull problems. I am a student at university. Unfortunetly the professors and student's don't take the programming contests as seriously as your university did. Most of the people that compete here only seem to compete once. And sometimes will simply drop out two days before the contest (as one team did this year), or decide not to go the morning of (as a team member did last year). –  Alex Nov 8 '12 at 16:39
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.