How to prepare for a programming competition? Graphs, Stacks, Trees, oh my!

Question

Last semester I attended ACM's (Association for Computing Machinery) bi-annual programming competition at a local University. My University sent 2 teams of 3 people and we competed amongst other schools in the mid-west.

We got our butts kicked.

You are given a packet with about 11 problems (1 problem per page) and you have 4 hours to solve as many as you can. They'll run your program you submit against a set of data and your output must match theirs exactly. In fact, the judging is automated for the most part.

In any case.. I went there fairly confident in my programming skills and I left there feeling drained and weak. It was a terribly humbling experience. In 4 hours my team of 3 people completed only one of the problems. The top team completed 4 of them and took 1st place. The problems they asked were like no problems I have ever had to answer before. I later learned that in order to solve them some of them effectively you have to use graphs/graph algorithms, trees, stacks. Some of them were simply "greedy" algo's.

My question is, how can I better prepare for this semesters programming competition so I don't leave there feeling like a complete moron? What tips do you have for me to be able to answer these problems that involve graphs, trees, various "well known" algorithms? How can I easily identify the algorithm we should implement for a given problem? I have yet to take Algorithm Design in school so I just feel a little out of my element.

Here are some examples of the questions asked at the competitions: ACM Problem Sets

---

Update:

Just wanted to update this since the latest competition is over. My team placed 1st for our small region (about 6-7 universities with between 1-5 teams each school) and ~15th for the midwest!

So, it is a marked improvement over last years performance for sure. We also had no graduate students on our team and after reviewing the rules we found out that many teams had several! So, that would be a pretty big advantage in my own opinion.

Problems this semester ranged from about 1-2 "easy" problems (ie bit manipulation, string manipulation) to hard (graph problems involving fairly complex math and network flow problems). We were able to solve 4 problems in our 5 hours.

Just wanted to thank everyone for the resources they provided here, we used them for our weekly team practices and it definitely helped!

Some quick tips that I have that aren't suggested below:

1. When you are seated at your computer before the competition starts, quickly type out various data structures that you might need that you won't have access to in your languages libraries. I typed out a Graph data-structure complete with floyd-warshall and dijkstra's algorithm before the competition began. We ended up using it in our 2nd problem that we solved and this is the main reason why we solved this problem before anyone else in the midwest. We had it ready to go from the beginning.
2. Similarly, type out the code to read in a file since this will be required for every problem. Save this answer "template" someplace so you can quickly copy/paste it to your IDE at the beginning of each problem. There are no rules on programming anything before the competition starts so get any boilerplate code out the way.
3. We found it useful to have one person who is on permanent whiteboard duty. This is usually the person who is best at math and at working out solutions to get a head start on future problems you will be doing.
4. One person is on permanent programming duty. Your fastest/most skilled "programmer" (most familiar with the language). This will save debugging time also.
5. The last person has several roles between assessing the packet of problems for the next "easiest" problem, helping the person on the whiteboard work out solutions and helping the person programming work out bugs/issues. This person needs to be flexible and be able to switch between roles easily.

Thanks again SO!

Answer 1

Check out CLRS here. 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 by googling e.g. "ICPC practice problems". For similar problems (with the possibility of cash prizes, prestige, and the like), try TopCoder.

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.

Answer 2

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.

Answer 3

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.

Answer 4

Topcoder, Sphere Online Judge, and UVA 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.

Answer 5

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

Answer 6

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.

Answer 7

For learning the best site in my opinion is USACO. 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.

Answer 8

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 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 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).

Answer 9

Practice, Practice, Practice!

And then a bit more Practice.

Answer 10

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.

Answer 11

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!