Programming contest approach [closed]

Question

This is broad question, but would like to know views of experts. I came across one document Suffix arrays – a contest approach, also found some comments that participant should be ready with such data structures already in hand. now a days lot of online programming puzzles are coming with time bound. So I would like to know what are the other data-structures/algorithms should one be ready with.

Answer 1

I have been competing for about 10 years now and have created a not-so-bad library myself. Most of the really good competitors have their blogs for instance the legend Petr Mitrichev and there they explain ideas they got on some competitive problems. Reading these can help you - if you see a nice idea implement it and have it stored. I add algorithms to my library when I see a problem that involves them. That way I can verify that my implementation is correct- I only add an algorithm if I have passed at least one problem with its implementation.

Here is a list with some of the algorithms I have:

• I have a huge geometrial library with classes representing points, lines, polygons, segments, circles and some operations with them(for instance intersection, convex hull of set of points etc)
• Tarjan's algorithm for strongly connected components
• Dinitz flow algorithm
• Bipartite matching implementation
• Min cost max flow implementation
• Aho-Corasic string searching algorithm
• Knuth-morris-pratt string searching algorithm
• Rabin-Karp string searching algorithm
• Linear time suffix tree using ukonnen's algorithm
• Fast exponentiation
• Polynom implementation
• Big integer implementation
• Fractional numbers implementation
• Matrix class implementation
• Prime factorization
• Eratosthenes Sieve
• Segment Tree
• Hungarian algorithm
• 2-Sat algorithm. For this I use Tarjan's algorithm mentioned above.

You will notice that some of the most basic algorithms(like BFS,DFS, Dijkstra) are not mentioned above and that is because I don't have them implemented. These algorithms can not be easily generalized in a way that you will simply copy and paste them and everything will work. Also it takes me less then 5 minutes to write them - I usually put in my library only algorithms that are either hard to implement or are easy to make an error when implementing them.

Answer 2

Check out these featured articles @ TopCoder. They are really cool.

While you are at it, I suggest taking part in the programming contests at TopCoder. Because the best way to improve is to practice & keep taking part in such contests.

Also Project Euler too is really addictive.