2004 ACM Programming Competition Solutions

<=
2004 Problem Set
2004 Regional Results
 
  Question 1
  Question 2
  Question 3
  Question 4
  Question 5
  Question 6
  Question 7
  Question 8
  Question 9
 

The 2004 Adelaide ACM competition had a few hiccups. It is important to realise just how much effort is required to put together a competition of this magnitude and recognise that accidents do happen. Having said that however, the wording on many of the questions was quite tangled, making it harder to understand what was actually expected from the solution (even if the solution itself was easy).


Question 1 - Jelly

  • Problem Sheet
  • The first easy problem - you need to read in a list of jelly measurements and then print out the two names which had a different total volume from the average (or a message if they all came out the same).
  • Sample Solution [input=>output]


Question 2 - Change

  • Problem Sheet
  • This question is quite easy because you are assumed to have an infinite amount of change available. In that case it is just a simple matter of decrementing through the denominations available from largest to smallest until you have paid it all out (the question would only be harder if Australian denominations couldn't be expressed as smaller amounts). There is also a bit of string parsing to do, and a simple rounding towards 0 or 5.
  • Sample Solution [input=>output]


Question 3 - Necklaces

  • Problem Sheet
  • The first medium problem could have been much harder - assuming the judges tried to overwhelm you with huge amounts of input. However, this turned out not to be the case as many teams simply calculated every single possible combination available. Clearly, the minimum value is the complement of the maximum value. Also, the largest value is going to be the one which has the most consecutive 1-bits in front of it, so you don't have to calculate from those starting points 'inside' a string of identical letters.
  • Sample Solution [input=>output]


Question 4 - Graphics

  • Problem Sheet
  • This problem is about navigating through an n-deep co-ordinate system. You are given a particular starting position, which also implicitly implies the number of hierachical tiles, and a list of commands. Each command initially only applies to the most nested grid, but if that move causes you to change to a different grid at a higher level of the problem you will have to track that change as well. What might not be clear (since this is supposedly a "software" problem) is that if you *ever* go outside the grid at *any* part of the process the final result is immediately "OUT".
  • Sample Solution [input=>output]


Question 5 - Shopping

  • Problem Sheet
  • A mildly tricky problem, although not as hard as the later questions. The question is really just producing a scheduling algorithm that minimises the total waiting time for a list of process with different arrival and calculation times. I actually created a class for the customers because I find that much simpler than trying to manage a half-dozen arrays (especially as they get re-ordered). Esentially you maintain a priority queue based on busy-time remaining, and you add new customers to that queue as their arrival time comes up. Each new arrival is inserted into that priority queue, so if they end up at the front they start getting processed instead. I could have probably used slightly faster sorting algorithms if the time requirement was actually violated. Ironically, this is also the theoritically optimum solution for teams competing in the ACM competition! :)
  • Sample Solution [input=>output]


Question 6 - Trees

  • Problem Sheet
  • This is a pretty clever problem, in that it is obviously very easy to check your solution is correct but not so obvious how to best produce that solution. The two main solutions were either to parse the input to actually produce a tree, and then just perform an N-L-R traversal to get the output, or parse the input using a simple stack machine that produces the output on the fly.
  • Sample Solution [input=>output]


Question 7 - Monks

  • Problem Sheet
  • Pretty standard search problem. Each day you can choose to pour beads from a larger bowel into a smaller bowel until the smaller bowel has doubled. You continue this process until one of the bowels has been completely emptied (ie. right after two bowels had exactly the same amount of beads in them). The main trick is to remember to re-sort the bowels after each move so that they are always well-ordered.
  • Sample Solution [input=>output]


Question 8 - Squares

  • Problem Sheet
  • Pretty standard search problem. In fact, the difference between my solution for Q8 and Q7 was minimal (mostly altering the internal structure of the 'configuration' object). Basically as long as you don't keep backtracking with C+CC+C+CC+C+CC+... of the same tiles you would eventually settle upon a magic square or exhaust your solution space completely.
  • Sample Solution [input=>output]


Question 9 - Colours

  • Problem Sheet
  • This problem was so daunting that not a single team completed it, not even the UNSW 'uber team' which had about 3 hours spare to spend on it! At a staggering four pages long, it took me over an hour to actually understand what the question was even asking, which turns out to be two seperate problems. The first part of the problem is processing an LL(2) language to produce a graph. The second part of the problem is to determine if that graph can be coloured with only three distinct colours so that adjacent nodes are different colours. The help that the complicated 'tracks' system gives you is the knowledge that those nodes on the same track are never linked, but in hindsight I can't say that this ended up balancing the hideous complication the question ended up becoming. My solution is based on the (unproven) suspicion that provided that each node connects to no more than two distinct tracks then the graph is 3-colourable. Let me know if you find a proof or counter-example. A full searching solution can be found amongst previous year's solutions.
  • Sample Solution [input=>output]

Updated 22 / 9 / 2004