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[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
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(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.
By brett1479
TopCoder MemberAuthor Profile
|