ACM Programming Competition Information

South Pacific ACM
  General Tricks
  Valladolid Online
  Valladolid Solutions
  2004 Solutions
  2004 Heat 1 Solutions
  2003 Solutions
  2003 Heat 2 Solutions
  2003 Heat 1 Solutions
  2002 Solutions
  2001 Solutions
  2000 Solutions

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.
Update: Going further back through previous year's solutions I suspect my previous comment was slightly too harsh - some problems are clearly generational search problems. For these problems you will usually need to identify a way of rooting out identical branches early - that is, you will have to implement an A* search.

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:

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

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:

  • - 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