2003 ACM Programming Competition Solutions

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

Question 1 - Wacmian Numbers

  • Problem Sheet
  • This is a simple problem of converting a number from base 6 into base 10, with the slightly annoying fact that the alphabet is not the usual numbers. The -1 is not a big deal if you just use the generic conversion loop, so the only non-trivial part is remembering that back-slash is the escape character, so to actually write a back-slash character you need to write two in a row.
  • Sample Solution [input=>output]


Question 2 - CD Titles

  • Problem Sheet
  • This is quite unusual, as it is one of the only questions I have seen that requires you to read in *all* the input before you can do *any* processing. Apart from that you just need to watch your indicies when you start going off the end of the smaller strings.
  • Sample Solution [input=>output]


Question 3 - Caesar Cipher

  • Problem Sheet
  • The first of the "% != mod" questions this year (there were a lot ;). The fact that the different character sets wrap into themselves instead of having a single continuous character set makes the problem a tiny bit more complicated (and the fact that characters not in this set are *not* moved at all), but this is still one of the 'no-brainer' questions.
  • Sample Solution [input=>output]


Question 4 - Water Tanks

  • Problem Sheet
  • The first 'thinking' problem - the goal here was to open the minimum number of gates that every collection of tanks had exactly the same ratio of volume:tanks as each other (which will be the same as total_water:total_tanks). This is thus a searching problem, but the annoying part is the wrapping you get when you open the right-most gate currently not open (which then flows 'back' to the first tank).
  • Sample Solution [input=>output]


Question 5 - Spots

  • Problem Sheet
  • This question looks simple, and but for one small detail it wouldn't be that hard. That tiny problem is the fact that there can be up to 1000 instructions of a 1,000,000 repitions! This means that a basic 'lock-step' simulator will not actually meet the timing requirements when tested against the judges 'super-large' data. To reduce this problem requires you to understand a little linear algebra that occurs in cycles: the minimum list of squares travelled in a path that loops back on itself, whether they hit each other, and if not who painted any intersecting squares last (that's the really annoying part ;). In essence, for each pending instruction we attempt to generate the smallest sub-cycle that brings both painters back onto their current square. We can then simply subtract multiples of that cycle-length from the instruction's repeat-count without simulation until one of those counts drops below the calculated cycle-length. There are two valid ways of approaching this problem: calculate the cycle first, or keep a recent 'history' HashMap that 'triggers' the short-cut once both painters return to a square they have visited recently. Either way, you are still going to need to know about the lowest common multiple of the order of (?.dx,?.dy) mod (width,height). No matter which one you picked, I still think this is definately the second hardest problem after number 8. ;)
  • Sample Solution [input=>output]


Question 6 - Mobile Phones

  • Problem Sheet
  • This problem wasn't supposed to be hard if you didn't panic. The problem requires you to build a recursive look-up 'dictionary', and to perform some string pattern matching. I personally like to abstract away the alphabet change into a HashMap, just in case in a future question they decide to have the alphabet also be dynamic. The *real* catch is that the sample output for this question is WRONG. ;) One of the lines is sorted lexically, one is sorted on input order. The problem was supposed to be sorted by input order, and that has been fixed in the text file below. I consider this to be the easiest of the 'hard' questions, and yes, I like HashMaps. ;)
  • Sample Solution [input=>output]


Question 7 - Grids

  • Problem Sheet
  • This might look like a rotational geometry question, but it's not really. This question is really more like a 'connect-four' game: at each generation you only need to care about the holes in the current pile, and everything else must match perfectly. If a tile doesn't have *any* non-transparent matches we can completely ignore it any given branch.
  • Sample Solution [input=>output]


Question 8 - Vans

  • Problem Sheet
  • It turns out that this problem is talking about Hamilton Cycles, which I had never heard of until I started trying to find a solution for this problem. ;) It turns out that there was a paper or book of some kind published which provided a solution for a grid of 4xN neighbour-connected verticies (of which I could only find an excellent reference, not the original). Considering the fact that the solution is a 5th degree recursive equation:
       H(n) - 2.H(n-1) - 2.H(n-2) + 2.H(n-3) - H(n-4) = 0
    I am extremely suprised this question was included, since the general construction of these recurrence relations was only published in 1998 (unlikely to be text book material in all but the most 'cutting-edge' geometry or algorithm text books). Obviously, we need to use the BigIntegers. I also used a HashMap to cache the previous results so that the time needed for a given problem set was only equal to the time needed to calculate the largest result (plus formatting time). If this still failed requirements you could then have used an offline generator to physically embed the numbers in a hard-coded array, then simply return the string at a given index.
  • Sample Solution [input=>output]


Question 9 - Trees

  • Problem Sheet
  • This problem is not necessarily as hard as the question sheet might suggest, all you need to do is come up with a unique well-ordered comparison for two trees, then you can generate a canonical form for each tree and thus only compare that form, rather than the whole of both trees each time. I used the traditional ordering, which is that every node with N+1 children is bigger than every node of <N elements (even if the tree below it has more nodes further down), and two trees are equal if their kids have been ordered recursively as such, and they have the same numbers in the same position of their canonical form. The other trick I use is the encoding technique for removing the 'right encloser' by having beginning every list with the number of elements in that list (which could then recursively be another list) so I don't have to write lots of {}s. ;)
  • Sample Solution [input=>output]

Updated 20 / 8 / 2003