Check out CLRS here ^[1]. It's widely considered to be the premiere algorithms book out there. However, I would suggest that doing the practice problems using an online validator is by far the best way to prepare for these things. For actual previous ACM problems, try CS Department websites ^[2] by googling e.g. "ICPC practice problems". For similar problems (with the possibility of cash prizes, prestige, and the like), try TopCoder ^[3].

Building up a toolbox of algorithms and data structures will take time, but by the far the most important part is being able to translate an efficient-enough algorithm into code, and the only recipe for that involves lots and lots of practice. It's no surprise that the teams that win at the World Finals treat ICPC as a full-time job, and most who advance to the World Finals at least do practice problems on a weekly basis or so.

Topcoder ^[1], Sphere Online Judge ^[2], and UVA ^[3] are a few online programs that have puzzles and competitions. I prefer them in the order I listed them above. As far as team strategies, I'm not too certain on those, as I've never done them myself.

I've found that the best approach is to learn how to work with your teammates. You have one computer, so all three of you need to determine who gets to be at that computer when. Sometimes a couple minutes of online debugging is all that's needed. Other times you should step aside so that your teammate who has just written up an algorithm for another problem can code it up. Sometimes you're working on a problem that you know a teammate has a key piece for (i.e. you know that you need to do Dijkstra's algorithm but can't remember how to code it), so you need to be able to explain the piece that you need, and prepare the algorithm trusting them to fill in that one piece.

Sometimes you'll be unable to spot the bug in your code, or you're unsure that your algorithm is correct. Explaining it to someone else on your team is a good way to get that key insight.

Yet none of this can work if you don't trust each other. If you are arguing about who should be at the computer, then you will not be successful. If you have two people spending the first 30 minutes both working on the same problem independently, you won't be successful. If you have one person spending an hour at the computer debugging a problem, you won't be successful.

And yet you'll still need the skill to solve the problems.

The most basic skill needed for the ACM contest is a set of patterns for dealing with input and output. You'll likely see the same patterns "Here's N; Here's M; Here's K; here are N lines of M items each" for input. Practice enough problems so that the parsing strategy becomes second nature (the exact techniques depend on the language you use).

Another important skill is knowing the tools you have. If you're using C++, learn the STL and what it gives you inside and out. If you're using Java, then java.util is your friend. If you're spending time during the contest implementing a quicksort, you're probably wasting your time. That said, know the limitations of your libraries. Know what you'll need to implement by hand.

A third important tactic is to know your algorithms. DFS, BFS, Dijkstra's algorithm, Floyd-Warshall, max-flow, finding the area of a polygon. You should understand all of these algorithms, and ideally have psuedo or actual code for them ready to go.

Finally, learn how to extract the key information from the problems. A lot of times you might misread some key aspect of a problem, causing your code to have a bug (see the first section of this post about getting a second pair of eyes looking at the problem).

From there it's up to you to learn how to apply the tools you have to the problems. Good luck next year!

For learning the best site in my opinion is USACO ^[1]. Their training pages have problems in a good order, and pages explaining the common algorithms as well as an online judge. Its a high school contest, but the problems get as hard as ACM problems.

From my experience (won our regional this year) the most common algorithms are dynamic programming, and Dijkstra. Dynamic programming you really have to code a ton of times to get good at, but it comes up constantly. Dijkstra you can memorize, but you should also know it inside and out because you will commonly have to make slight variations to it.

ACM allows you to bring in as much paper material as want. Take advantage of this. Have printouts of any common algorithm you might need (especially graph algorithms). That way, as soon as you realize the problem requires Floyd-Warshaw or Dijktra's or whatever, you barely have to think about the implementation details.

Other than that, practice is the best way to get better. Log onto Topcoder ^[1] and just start working problems. The more of these types of problems you do, the better you'll be. Topcoder also has a whole bunch of tutorials ^[2] on common techniques like Dynamic Programming (also very important).

Keep at it and good luck! I've never been on a team that got more than 4 of the problems and that wasn't even good enough for the top 10 at our site (the west coast is rough).

I used to participate in such competitions(although none at ACM level). Here's what I used to do:

• Since this basically boils down to solving maximum questions, pick the easy ones and solve them first.
• Have faith in your team mates. Every one have a look at all the questions first, then tear up the question paper and let each team mate solve the easy questions on their own parallely.
• If you have time left, discuss the algos for the hard ones together.. and learn to think about algos as a team, Teamwork is the key for hard algorithmic problems.
• Test yourselves with Topcoder ^[1]

Practice and study. Look at the sample problem sets and try to figure them out. Hold mock competitions with them to see how well you do. Read books on algorithms and computer science math.

Take the class in Algorithm Design, and take other classes on discrete math.

It sounds mostly like you're new enough that you need experience and knowledge more than anything else.

Yes, practice and study. Look over not just the sample problem sets, but problem sets from several previous years. Practicing with your team and developing strategy is very important. You must all be able to work together on it (kind of like the real world for once).

We tried to maximize keyboard time, with one person solving problems only (perhaps with pseudocode, perhaps with real code as time permits), and the other two switching between inputting the program and debugging on paper.

You can also use a online programming contest practice server (like UVA) to help get used to just the process of how it would be judged, even if it won't work exactly like the real thing. http://icpcres.ecs.baylor.edu/onlinejudge/

EDIT: I don't know if the above UVA site works as it did before, to be able to have easy practice, etc. or not. There should be plenty of other implementations around however if it does not.

Here's one thing that we found incredible useful on my team's trip to the ACM, where we tied for second (tiebreaker put us at 9th though).

You're allowed to bring paper... even paper with pre-written programs on it. Write simple implementations of basic algorithms in your favorite language; Bellman-Ford is one of my favorite, as its a graph search that's even simpler than Djikstra's and doesn't break on negative-weight paths.

This makes it much easier and quicker to solve some problems since you can just type in the algorithm you brought with you, making the challenge one of adapting it to fit the problem rather than having to implement something of the sort on the spot.

It might seem a bit cheesy, but it helps a bit.

Practice, Practice, Practice!

And then a bit more Practice.

try http://www.codechef.com/ with lots of practice problems ranging from easy to hard. They have monthly competitons too.

It's great that you're tackling this kind of challenge, but if it is disheartening, why bother? Speed-programming of tricky algorithms is a very strange skill.