The 2002 ACM International Collegiate Programming Contest,
     Sponsored by IBM
East Central North America Region

Problem Notes

Problem A - Ball Toss

number of submissions: 193
number of correct submissions: 77

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.

Problem B - Galactic Breakup

number of submissions: 54
number of correct submissions: 3

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.

Problem C - Increasing Sequence

number of submissions: 48
number of correct submissions: 4

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.

Problem D - Pre-Post-erous

number of submissions: 7
number of correct submissions: 7

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.

Problem E - Knockout

number of submissions: 76
number of correct submissions: 44

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.

Problem F - Plugged In

number of submissions: 44
number of correct: 26

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.

Problem G - Price is Right

number of submissions: 44
number of correct submissions:26

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.)

Problem H - Slots

number of submissions: 45
number of correct submissions: 24

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.