

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 nontrivial part is remembering that backslash is the escape character, so to actually write a backslash 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 'nobrainer' 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 rightmost 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 'lockstep' simulator will not actually meet the timing requirements when tested against the judges 'superlarge' 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 subcycle that brings both painters back onto their current square. We can then simply subtract multiples of that cyclelength from the instruction's repeatcount without simulation until one of those counts drops below the calculated cyclelength. There are two valid ways of approaching this problem: calculate the cycle first, or keep a recent 'history' HashMap that 'triggers' the shortcut 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 lookup '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 'connectfour' 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* nontransparent 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 neighbourconnected verticies (of which I could only find an excellent reference, not the original). Considering the fact that the solution is a 5^{th} degree recursive equation:
H(n)  2.H(n1)  2.H(n2) + 2.H(n3)  H(n4) = 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 'cuttingedge' 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 hardcoded 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 wellordered 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]

