BC Winter Programming Contest Practice

The BC Winter Programming Contest is coming up this Saturday, January 16th. I’ve been making the rounds to different classrooms, trying to encourage some new students to give it a try. Last night I held a three hour practice session and luckily a few new faces showed up to give it a go. I picked five problems from the 2009 Greater New York Regional programming contest. I picked this set as I knew a lot of teams solved all the problems, so I figured it would have some pretty manageable problems for complete newbies.

The students worked on problems A, C, D, H, and I. Most students solved A and D, and John Hawthorn was the only one to solve C.

Problem A is quite straight-forward. You need to read in a list of 10 numbers and print the 3rd largest value. Probably the fastest way to code this is to read in the 10 numbers, sort them and print the 7th number in the array. This should only take a few lines.

int P;
cin >> P;
while(P--) {
  int num;
  cin >> num;
  vector<int> t(10);
  for(int i = 0; i < 10; i++) cin >> t[i];
  sort(t.begin(), t.end());
  cout << num << " " << t[7] << endl;
}

The second easiest problem was problem D. In this problem you have to read in a list of numbers and for every odd-indexed number, print the current median of the list. The key here is to make sure your sort is fast enough to get under the time limit and to follow their output specification exactly. Most students made mistakes with the output format. The built in sort routines in C++ or Java should be fast enough for this problem.

Problem C is a little tricky to understand. The problem describes a scenario where you drop glass balls from different floors. The goal of dropping these balls is to determine what the last floor is that you could drop a ball from without having it break. In the classic version of this problem, sometimes involving eggs, you have to figure out the optimum strategy for this, which is a variation on binary search. However, in this problem they want you to figure out what the minimum number of drops is in the worst case. This means, if we choose the worst strategy, what is the best we can hope for?

To solve this, we can try to enumerate all possible scenarios given the number of balls we have and the number of floors we can potentially drop a ball from. We can enumerate these states through recursion over two variables, our current number of balls left and the number of floors left. We also need to use memoization to store our states so that we don’t repeat states that we’ve already computed. Finally, we need to determine what the conditions are for this recursion. There is basically two cases, we drop a ball b from a floor f and the ball breaks leaving us with one less ball and knowing that we need to search floors below f, or the ball does not break, meaning we need to search floors above f. From these two scenarios, we want to keep track of the worst result, but the minimum overall value.

int rec(int balls, int floors) {
  if(balls == 1) return floors;
  if(floors == 0) return 0;
  if(floors == 1) return 1;
  
  // we already calculated this one
  if(memo[balls][floors] >= 0) return memo[balls][floors];

  int best = floors;
  for(int f = 1; f <= floors; f++) {
    // ball breaks on this floor, one less ball
    int r1 = rec(balls-1, f-1);
    // ball does not break, search above
    int r2 = rec(balls, floors-f);
    // keep track of the worst result
    int result = 1 + max(r1, r2);
    // keep track of the minimum for all worst cases
    best = min(best, result);
  }
  memo[balls][floors] = best;
  return best;
}

Problem H states that you need to find all lattice points contained within a convex polygon. All coordinates for the lattice points and the polygon vertices are integers. There’s several ways you could solve this problem. One way is to do point in polygon tests to determine which lattice points are contained within the polygon. To do this, you can calculate all the potential lattice points by determining the maximum x-coordinate, maximum y-coordinate, minimum x-coordinate and minimum y-coordinate based on all vertices in the polygon. Then, you can loop from the minimum y to maximum y, minimum x to maximum x, and test each point.

Finally, problem I describes a puzzle with 7 positions, 6 of which contain a letter and one position is blank. A valid move is to move a letter from its current position into the blank position. The goal is to convert the game into the winning state as described by the problem statement. The problem states that given an initial configuration, print out the minimum number of moves along with the solution to reach the win state or print NO SOLUTION if it is not possible.

This is a simple example of a “Searchy type problem” that I had blogged about before. The positions can be represented as nodes in a graph, edges exist between the nodes based on how the puzzle is described. You can then perform a breadth-first-search over the graph, where a new state for the queue is added for each valid movement of a letter to the current blank space. Also in the state, you need to keep track of the path you took to reach that state. Once you find the winning state, print the path and length.