Saturday, April 5, 2002

Problem Set Analysis & Opinion

The first run at the finals had to be cancelled midway due to network issues. While TopCoder tried hard to work through the issues, in the end it was decided that the contest was disrupted beyond salvaging, and I think that all of the competitors agreed. The second run had much easier problems - more on par with round 3 of the semifinals, and 3 of the finalists were able to finish all 3 problems during the coding phase. At the end of the coding phase, dgarthur was on top, with 1447.71 points. Yarin was 2 challenges behind, with 1382.79. dmwright and sjelkjd rounded out the room, in third and fourth places, respectively. The problems turned out to be easy enough that everyone's submissions were correct, and dgarthur walked away with the big check.

Value	275
Submission Rate	4 / 4 (100.00%)
Success Rate	4 / 4 (100.00%)
High Score	Yarin for 237.49 points

This was a pretty simple problem, and could be easily solved with 4 nested loops. You can simply iterate through all possible sets of 4 ordered points, check if they formed a loop with no cross edges, and increment a counter if they did. It the end, you have counted each loop 4 times (once for each possible start spot), so you have to divide by 4.

Value	450
Submission Rate	4 / 4 (100.00%)
Success Rate	4 / 4 (100.00%)
High Score	Yarin for 385.26 points

Again, nothing really tricky here. You need to keep track of the probability for each location at each time step, and at each time step, update the probabilities according to the following recurrence:
prob[t][x][y] = sum over all directions(prob[t-1][x+dx][y+dy])/8
If one of the directions contains an obstacle, then you have to take that into account, so that the robot stays in the same location. So, you can modify the recurrence so that you also add in each invalid direction. So, you get:
prob[t][x][y] = sum over all directions(prob[t-1][x+dx][y+dy])/8 + (number of directions that you can't go) * (prob[t-1][x+dx][y+dy]) / 8

Value	950
Submission Rate	3 / 4 (75.00%)
Success Rate	3 / 3 (100.00%)
High Score	dgarthur for 863.41 points

Balanced binary search trees are used frequently in algorithms. Their guaranteed O(nlgn) access time makes such trees quite versatile. In specific cases, where the probability distribution governing access to the tree is known a priori, it may be possible to improve access times via an unbalanced binary search tree. Suppose a node had relative access probability P and depth D in the tree. By summing P*(D+1) for each node in the tree we have a statistic that can be used to measure the overall tree access time. To minimize this value in an efficient manner, we can use Dynamic Programming(bottom-up) or Memoization(top-down). Here I will describe a top-down approach. Assume we have a list containing each node, sorted by value, and their corresponding probabilities. Iterating through the list, we can elect any element to be the root of our tree. This leaves a group of nodes that must be on the left, and group on the right. Since the left and right set of nodes are simply smaller versions of the same problem, we recursively apply this method to each side. The value for any given rooted tree is the sum of the values from each of its subtrees, plus the sum of all the probabilities in the tree. Taking the minimum from all possible roots produces the best value.