

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 'checkpoint' (or whether the count was invalid).
 Sample Solution (includes breakpoint 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 tiebreaker).
 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 minimax 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 hashmap of (boss, [employees+]) enabled you to build the tree 'onthefly' 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 minimax 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 tiebreaker 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 minimax 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 breadthfirst 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 NPcomplete edgecolouring problem (think of the subgraph 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 toplevel we perform a breadthfirst 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 depthfirst 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 borderline cases of 'singlecall' states a search causes, without eliminating subgraphconnecting '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 12^{4} choices I don't think a depthfirst 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 'outermost' 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 clockwise and the other anticlockwise. 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 crossover the 360/0 degree mark, and making sure that a 180 degree line doesn't 'activate' both the clockwise and the anticlockwise boundary markers.
 Sample Solution [input=>output]

