What is the ACM programming competition?
The ACM programming competition is just that, a competition during which teams compete by attempting to code correct solutions to as many of the problems that they can within ~5 hours. The problems are not just 'undergrad assignment' questions, they are scenarios that will (usually) require you to develop a non-trivial algorithm that correctly simplifies the problem into a form that can be solved very quickly (solutions must generally be able to solve a multi-thousand solution in under 3 minutes).
Why would I want to enter?
Aside from ego, pride or otherwise aquired bragging rights, the ACM is also a very good opportunity to develop your skills of problem solving under pressure - something which every person this side of the wilderness will need to have throughout their life style. Understanding how you came to a given solution, and even understanding why that solution was wrong (or inelegant), can help you to develop your problem solving skills in ways that just reading a textbook never will.
Boy that sounds hard?
Actually, it is and it isn't. The most common misconception is that you need to be a 'wizard' coder to do well. However, the requirement that your solution run within a given time frame actually makes the competition more to do with a persons ability to develop good algorithms (what the rest of the world calls 'problem-solving' ;) far out-strips a persons need to be able to remember all 6 versions of exec() and what they do. ;) In fact, many successful teams bring with them printed notes of how to perform the more tedious coding tasks so that they can spend their time working on finding a good solution rather than wasting it trying to remember the correct algorithm for a depth-first search.
Can you give me any hints?
Aside from my previous years solutions above, it is my firm
suspicion that in order to fit the time requirement imposed,
each problem will have an O(n) or O(n.log(n)) solution. While
I know for a fact it is possible to have a problem solved by
a (heavily) optimised O(n^2) program, I have yet to be convinced
there is not an elegant solution to every problem. Hence, the
challenge on the day is not to merely code solutions, but to
be able to develop better solutions than the 'easy' ones.
For example, being able to identify which branches in a tree searching
algorithm will never provide a solution will save you from having
to search out all of the leaf-nodes from those branches.
Oh, and always go backwards. ;)
Here are some algorithms you should know how to use:
For people using Java as their programming language, the following classes will be absolutely indespensible for you to reduce your pain to managable levels:
About the solution pages...
I have tried to code my own solution for each of the previous year's Australian ACM questions. Some of them are good, some are not so good (I am always open to suggestion). Be aware that my solutions are designed for maximum transparency, NOT maximum speed. Remember that this competition is all about designing a fast algorithm, not writing illegible code. ;)
I have also tried to classify how `hard' each of the problems are based on three semi-distinct catagories:
Out of a three person team you should have at least one `math wiz', at least two `l33t coderz', and all have a rough understanding of the most important data structures (graphs, lists, hashmaps, trees) and their corresponding algorithms (depth first, breadth first, canonical comparisons, path finding, binary search, heap sort, etc...).
Updated 22 / 9 / 2004