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 ProblemsBoxingUsed as: Division One  Level One:
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. VolleyballUsed as: Division One  Level Two:
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 nonserving 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) + (1p)*(1win(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/(32*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:
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. 
