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).
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
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.
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. ;)
- Heap Sort
- Radix Sort (a.k.a. 'bucket' sort)
- The CoSine Rule
For people using Java as their programming language, the following classes will be absolutely indespensible for you to reduce your pain to managable levels: - HashMap - O(1) add, seek and remove.
- Object.hashCode() - you overload this to use a HashMap properly on your customised objects.
- Vector - for when you must store items by order (this is the same beast as ArrayList).
- BufferedReader - for reading in lines of input from System.in instead of mucking about with characters (NOTE: when we hit EOF this thing will return null).
- StringTokenizer - for cutting the input into the chunks for you.
- Integer.parseInt - this is just a no-brainer (there is also a base-n version if you need to convert between base X to base 10).
- Math.* - for all the operations you'd expect as well as never having to rewrite min(x,y) say.
- Multi-dimensional arrays - while technically a class, most people should know how to use two-dimensional arrays for problems which are unavoidably two-dimensionally solved.
- Big Integer - occasionaly there may be a need for riduculously large arithmatic.
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: - - coding - how much fiddly stuff you'll need to do
- - mathematics - how much `hard maths' you need to know
- - ADT - whether a specific data structure is helpful for this problem
- - warning - this problem contains a GOTCHA! Beware!
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