|
Match Editorial |
Online Round 3
September 22, 2004
Summary
With an average rating of about 2317, the competitors in round 3 of the TCO were some of the finest coders in the world. However, only 50 of them could advance, which meant that even some of these fine coders had to be eliminated. Among the titans to fall were notables radeye, WishingBone, and LunaticFringe. On the other end of the spectrum, dmytro, the lowest rated coder in the competition beat the odds and moved one step away from the onsite rounds. While there were a few surprises, no one was too shocked when John Dethridge took first by over 60 points, and snewman was over 100 points ahead of third place coder, ambrose.
The Problems
Boxing
Used as: Division One - Level One:
Value 250 Submission Rate 97 / 100 (97.00%) Success Rate 68 / 97 (70.10%) High Score reid for 233.81 points (7 mins 34 secs) Average Score 174.99 (for 68 correct submissions)
This problem can be solved with a greedy algorithm. First, find the earliest interval less than or equal to 1 second that contains 3 judges scoring a hit. Next, remove all hits that occur during that interval or before it, and repeat. This works because if you can get N hits by time t, that is always better than getting N hits by time t+1. The details of how you do this vary, but all of the algorithms I saw boiled down to this approach.
Volleyball
Used as: Division One - Level Two:
Value 500 Submission Rate 73 / 100 (73.00%) Success Rate 57 / 73 (78.08%) High Score SnapDragon for 486.15 points (4 mins 49 secs) Average Score 321.72 (for 57 correct submissions)
There were a couple of ways to do this one. The most common approach was to use memoized recursion. You want to fill in a 2D table, memo, such that memo[i][j] is the probability that a serving team with i points will beat a non-serving team with j points. Then, you just write the standard recursive memoization function:
double win(int server, int nonserver){
if(memo[server][nonserver] != -1)return memo[server][nonserver];
if(server>=15 && server >= nonserver + 2)return 1;
if(nonserver>=15 && nonserver >= server + 2)return 0;
double ret = 0;
ret = p*win(server+1,nonserver) + (1-p)*(1-win(nonserver+1,server));
memo[server][nonserver] = ret;
return ret;
}
The question, however, is how far we recurse before we give up and call it
quits. Since the probability is between 0.01 and 0.99, we're safe quitting when
one team gets to 1000 points. Even when the probability is 0.01, the game is
sufficiently unlikely to get up to 1000 points that we can just return 0 or 1
if it does.An alternative approach is to handle tie games where the score is greater than 15 with a closed form solution (and deal with the rest of the game as above). I won't work out all the algebra here, but if you churn through it, you end up with a probability of 1/(3-2*probWinServe) that the serving team will win a tie game. Were the constraints less generous, the recursive approach would not have been precise enough. LawnMower
Used as: Division One - Level Three:
Value 1000 Submission Rate 16 / 100 (16.00%) Success Rate 10 / 16 (62.50%) High Score ZorbaTHut for 654.09 points (23 mins 26 secs) Average Score 512.92 (for 10 correct submissions)
The first part to a solution for this problem is to iterate over all possible
placements of the shed. With a yard no bigger than 12x12, there aren't that
many ways to place it. Next, once you have the shed placed, how many spots can
you reach and still put the mower back in the shed? The key to figuring this
out is to first observe that you may go through the shed as many times as you
like while mowing the lawn. So, if you can reach a spot, and then get the mower
back in the shed the same way it started, you can mow that spot regardless of
which other spots you mow. Furthermore, if you can't reach a spot and get the
mower back in the shed afterwards, there is no way to mow it.
To figure out which spots we can reach and then return to the shed, we simply
run two depth first searches. On the first pass, you mark all of the spot,
direction pairs which are reachable going forward from the shed. On the second
pass, you mark all the spot, direction pairs which are reachable going backwards
from the shed. If a spot and direction is reachable going both forwards and
backwards, then you know that you can get to it, and then back to the shed.
Since you can go in both directions with a single method, the implementation is
surprisingly easy, if only you can quickly figure out how to do it.
