So I blinked and I missed the fact that qualifying round 3 had already happened. I thought it was this coming weekend. Having got through in QR1, forgetting about it is no drama, but it does mean my analysis of the problems is a bit late.
Q1) Given the top row and left column of a grid of numbers, where each number is supposed to satisfy the property of being equal to the sum of the 3 numbers to the bottom/right/bottom-right of it, determine the value of the bottom right number. If the result cannot be uniquely determined return 0. Maximum grid size 10×10.
A1) First to get rid of the trivial cases. If row length is 1, return last column entry. If column length is 1, return last row entry. Otherwise we actually have to fill in the grid. This is pretty trivial since each cell is the sum of the 3 bottom/right/bottom-right, if you know the cell, the bottom and the right, you can subtract the bottom and the right to get the bottom-right cell. Given you have the top and left sides, you can fill 1 cell immediately. That cell lets you fill 2 more, and those, 3. So you could diagonally fill the grid. Or you could just fill row by row, or column by column. In any case the cannot be uniquely determined scenario doesn’t exist so it can be ignored.
Q2) Given 6 numbers representing number of semitones to offset a guitar string (or -1 if that guitar string is not played), determine whether a major or minor cord is being played and if so which one.
A2) When I first started reading this question I had dreaded flashbacks to an old Top coder problem which was very similar. However this one is relatively easy. Modulo arithmetic comes into play. Simply add the offsets (where not -1) to the numerical value of each guitar strings open note (as given in the problem for those who don’t play guitar) modulo 12. Then reduce your (upto 6) notes to the unique values. If you have more or less than 3 values you can return not-a-chord immediately. Otherwise, sort the 3 values. For each of the 3 values, check to see whether the next one (wrapping round if you start with the greatest value) is equal to the original + 4 or 3 modulo 12. Then check if the remaining value is equal to the original + 7 modulo 12. If both conditions are matched, return Major ‘letter’ by mapping the original value to the letters if the first condition was +4, or Minor ‘letter’ if the first condition was +3. Otherwise return not-a-chord.
Q3) Given a pane of glass with width and height (both at most 1000), a starting position, and up to 2500 LRUD unit movements which cut the glass, starting from the starting position, how many pieces has the pane of glass been cut into?
A3) This is a simulation problem combined with a disjoint set enumeration. The thing I find most annoying with problems like this is the data structure to store the results of the actions. So used to a grid, storing details about edges is just annoying. I usually end up storing the 4 edges of each cell and dealing with the fact that most edges belong to 2 cells by ensuring I always update both. A grid of numbers can be used with numbers between 0-15 indicating which combination of surrounding edges have been cut, you can store these in bytes even making the grid require 1meg of ram. Once the simulation is complete, calculating the pieces comes in to play. I would do this with a disjoint set tracker (copying my code from TMD.Algo – since this is top coder… or maybe just writing it from scratch using arrays instead of dictionaries), creating a node for every square, then for each square unioning it with every neighbour which is on the other side of a non-cut edge. Then for each square get the representative, and use a dictionary to accumulate the count of unique representatives. Disjoint set tracker is practically O(1) for union and get operations, so even though there are a million cell locations the running time will not be a problem. Memory usage will be a few megabytes, but within the 64meg limit. This is really just showing my bias to disjoint set tracker, which I think is awesome. For a similar approach which uses a tad less memory, you can just do floodfill counting using breadth or depth first searches which can’t pass the cut walls, which is also O(1) per grid cell.
Alternatively one could construct a graph out of the path followed and the edges of the puzzle. Due to the limit on 2500 moves and 4000 edge positions, the memory usage will be much lower. You can then walk the graph starting at each edge using a turn right at intersection approach, mapping each location visited (and handling dead-ends by turning around and keeping on walking). Once you find a loop where you enter an edge from a direction other than the one you left it, you increment a counter and in any loop found case go back to starting at the next edge not already visited. Once done the counter is the number of pieces. Each edge is visited at most three times, so O(N) in edges (moves + perimeter), which is far more efficient. I would however consider it more complicated to implement, so I doubt I would have bothered.
All in all this looks like it was a pretty easy set. Although being a qualifying round that is probably expected.