East Central North America Region
A straightforward problem. Keep track of the current position of the ball, the current directions for each person, who has been tossed the ball, and how many have been tossed. Update the appropriate data for each toss until everyone has been tossed the ball.
The wrong approach here is to repeatedly use a graph traversal algorithm to check whether the graph is connected or not - this takes too much time for large graphs (and yes we put some large graphs in). This takes worst case O(n) time after each secession. One approach that works is the following: process the secessions backwards, inserting each cube into a disjoint set data structure. Then check after each secession whether the cubes are in separate sets or not. Efficient disjoint set implementations are effectively O(1) per operation.
A backtracking algorithm will work here as the numbers grow fast enough that the branching factor is not too bad. The tricky part comes in handling the 0's (which gave all of the judges fits). A dynamic programming approach will also work,but two passes are necessary: one to get the smallest last number, then another to resolve the tie-breaker.
The approach here is to recognize that ambiguous trees only occur when any node does not have a full contingent of children. If a node can have m children but has only n then there are m-choose-n different trees which have the same pre and post order traversals. Applying this recursively to the tree will eventually give you the correct answer. The key thing to know is which node is an ancestor of another.
Since the trees are binary and complete, an array representation of the tree (a la heapsort) is a convenient way to store it. Initially we assign player k a "low" ranking of 2^n and a "high" ranking of 1. As we move up the tree, as long as k is the winner we subtract successively higher powers of 2 from its "low" ranking. As soon as k loses we then follow the progression of the winners, adding 1 to the "high" score when the winner changes. Or use transitive closure to see who beats who, then count.
Once you figure out formulas for determining how row and column numbers are altered by 90-degree rotations and by horizontal and vertical reflections, the rest of the problem is easy -- using nested loops, enumerate all combinations of rotations and reflections and, for each combination, find the average distance.
Use dynamic Programming: Let N[i][j] = the largest price with i guesses and j lifelines. The boundary cases are N[i][0]=i (Guesses would be 1,2,...,i) and N[1][j]=1. Then N[i][j] = 1 + N[i-1][j] + N[i-1][j-1]. (When a wrong guess is made, it is either too high (and a lifeline is lost) or too low.)
There are two basic methods to solve this problem: the first is the brute force method - after finding three circles with the same letter inside, you calculate the centers of the circles and see if they lie equal distances from each other. The second approach involves using rotations: you find two circles that have the same letter, determine translations needed to move from one to the other, then rotate them by 120 and 240 degrees and see if either lands in a circle with the same letter.