2002 ACM Programming Competition Solutions

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

Question 1 - House Numbering

  • Problem Sheet
  • This is a simple problem of converting a number into binary and then counting the number of 1s and the number of 0s in the binary form. Notice that it there is no need to actually store the binary form itself, you can simply count the ones and zeros as you go.
  • Sample Solution [input=>output]


Question 2 - Book Pages

  • Problem Sheet
  • This was the first problem which sounds trickier than it really is. The idea of working out how many pages there were from the number of digits printed was easily reduced to working out which range of digit counts a problem came from. Not only would this eliminate the bulk of the page counting, it would also give you the divisor to use to find out how many more pages there were from the last 'check-point' (or whether the count was invalid).
  • Sample Solution (includes break-point generator algorithm) [input=>output]


Question 3 - Vowels Frequencies

  • Problem Sheet
  • A simple question about counting vowels from a piece of text. The only two snags where that you ignore case and you have to print the counts out in numerical order (with alphabetical order as the tie-breaker).
  • Sample Solution [input=>output]


Question 4 - Company Parties

  • Problem Sheet
  • This problem was deceptively hard. The actual solution to the question of who should go to the parties is a simple mini-max tree traversal of working out the "fun" rating whether a person does or does not go to the party. The hard part of this question was that the input data is randomly ordered - meaning that you had to build the tree *after* you read in the data (since you don't get the root node first). It turns out that the problem was structured in such a way that building a hash-map of (boss, [employees+]) enabled you to build the tree 'on-the-fly' with O(n) efficiency.
  • Sample Solution [input=>output]


Question 5 - Lollies

  • Problem Sheet
  • This was the second question that sounded much harder than it really was. The good thing is that each month is actually a seperate case, despite the cunningly labelled example input. It turns out that an even simpler mini-max problem going backwards over the month produces the total in one pass, and you can then check on what days you took lollies by checking to see if the number of lollies taken on that day is different than the number possible for the next day (if it is different that must mean you took the lollies that day). Notice on the question sheet that the tie-breaker given actually supports you doing it backwards rather than forwards when using this method. Beware the hidden requirement for using the singular *and* plural form of lolly though (as many teams pulled out their hair trying to find the 'bug' in their solution that made it fail).
  • Sample Solution [input=>output]


Question 6 - Maze Madness

  • Problem Sheet
  • Another theoritically simple problem, also a mini-max issue, based on the minimum number of moves required for someone to exit the maze. Unfortunately, the hardest (and most irritating) part of this problem was its intensive input processing. Assigning N/S/E/W boundaries to the array required a very careful approach to working out the offsets of each of the characters in the input, and then you will need to spend most of the rest of the program managing that array to make sure you correctly identify the neighbours based on thier offsets in the same grid. Once that was done a simple recursive breadth-first search algorithm would provide you with the 'cost' of every square in the grid (with the starting square being 0), then we simply check which of the squares qualifying as "exits" have the smallest cost attached to them (with Integer.MAX_VALUE representing an 'unreachable' part of the maze).
  • Sample Solution [input=>output]


Question 7 - Spreading Gossip

  • Problem Sheet
  • BEWARE! This is actually an NP-complete edge-colouring problem (think of the sub-graph created from the phone calls actually made and the colour as the generation since no phone can have two edges of the same generation). I have solved this with two nested A* searches: at the top-level we perform a breadth-first search of all the possible states of knowledge the village can be in at the end of each hour. At the child generation level we perform a depth-first search on the actual pairs of calls that can be made. I suspect the answer could be made slightly clearer by storing the phone grid as a set of Edges, which we then delete once used or useless, but the fundamental problem of finding pairs seems to require an exhaustive search of the phone network no matter which form you express it in. In particular, I have yet to be convinced there is any good way of eliminating the time wasting border-line cases of 'single-call' states a search causes, without eliminating sub-graph-connecting 'router' nodes which have to have a higher priority.
  • Sample Solution [input=>output]


Question 8 - Clock Synchronisation

  • Problem Sheet
  • I do not have a good solution to this problem. I suspect (very strongly) that this is a matrix inversion problem modulo 4, with the matrix no larger than 12x12 pivoting should not be too expensive. Notice this is a rotational geometry problem (like Rubix cube), but with a possible 124 choices I don't think a depth-first search will work for those cases where there is no solution.
  • Sample Solution (incomplete) [input=>output]


Question 9 - Polygonal Lines

  • Problem Sheet
  • This problem is not necessarily as hard as the question sheet might suggest, but it is one of those questions for which the solution is finicky. This trick is realising that in order to 'slide' the two pieces away along a certain line, every other cut must, for at least one 'side' of the line, be either all to the 'left' of the line or all to the 'right' of that line. In other words, if you place all of the cuts in a circle based on their angle, if more than half the circle is used there is no solution, otherwise whichever of the two 'outer-most' angles came first is the solution. In practice we solve this by only tracking the two 'boundary' angles right from the start, one of which is only allowed to move clock-wise and the other anti-clockwise. This is one of the relatively heavy 'maths' questions where you needed to understand how concave and convex verticies interact with the shape formed on either side of the line. The trickiest part is dealing with the angles that cross-over the 360/0 degree mark, and making sure that a 180 degree line doesn't 'activate' both the clockwise and the anti-clockwise boundary markers.
  • Sample Solution [input=>output]

Updated 20 / 8 / 2003