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.
DQuads
Used as: Division 1  Level 1:
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.
Robot
Used as: Division 1  Level 2:
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[t1][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[t1][x+dx][y+dy])/8 + (number of directions that you can't go) *
(prob[t1][x+dx][y+dy]) / 8
SkewTree
Used as: Division 1  Level 3:
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(bottomup) or
Memoization(topdown). Here I will describe a topdown 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.
By brett1479
TopCoder MemberAuthor Profile
