Wednesday, January 5, 2005 Match summary In Division 2, Oleksiy took top honors with a commanding lead, while bluequark and wickedman took second and third. A special mention goes to wickedman for being the highest scoring newbie. In Division 1, haha picked up his second SRM victory (his first was way back in SRM 187), with John Dethridge and natori coming in a close second and third. The Division 1 coders saw a quirky problem set, wherein the hard problem had a 95% success rate, while the others were successfully solved by less than 40% of those who submitted a response. In fact, the total number of correct submissions was nearly equal for all three problems (44, 37, and 40, respectively). The ProblemsVLNStringUsed as: Division Two  Level One:
The basic idea behind this problem is to work from left to right, building words, and stopping the build when you get to one or more spaces, then adding the first letter if it wasn't "and", "or", or "the". Trying to use a standard library split function could get you into trouble because of multiple consecutive spaces; a simple parsing approach is safer. ExperimentalAnalyzerUsed as: Division Two  Level Two:
This problem is not too difficult to code, once the methodology is determined. A simple approach is, for each variable, determine the minimum and maximum value of that variable where the result is 0, and where the result is 1. If those two ranges are nonoverlapping (note however, that all result 1 values could be less than the result 0 values, or vice versa), that variable is a predictor. ManhattanMovementUsed as: Division Two  Level Three: Used as: Division One  Level One:
This is a classic type of problem that can be solved very easily once you see the "ahha". In this case, the big "ahha" is that the answer is always a single vertical or horizontal line. There is never any advantage in changing direction. Need further convincing? If the road is vertical or horizontal, then only one direction is possible to travel towards the road, and it's trivial. For any diagonal road, consider the two direct paths (vertical and horizontal). If both direct paths are the same, the case is again trivial. In any other case, one or the other is shorter. Now, suppose you were to do some of your travel along the short path, then change directions. After travelling the short path, you're left at another point, with the same setup, whereby the same direction is still shorter. Thus, it always makes sense to continue on the short path. So, calculate the distance to the line horizontally and vertically (be careful of cases where a or b is 0!) and return the shorter of the two. Also, it's important to cast all of the variables to double before calculating, otherwise an overflow can result. This is possibly the biggest gotcha that left percentages so low. OneArmedBanditUsed as: Division One  Level Two:
In spite of a lot of numbers floating around, this problem is fairly straightforward. Knowing that expected outcome = probability * payout, we really have all the information we need to calculate our result. First, we determine the expected outcome of each of the nonjackpot payout lines. This is simply the probability of each wheel landing on the appropriate symbol (or 1, if the symbol is a wildcard) multiplied by the payout. We add these together. If this is greater than or equal to 1, then the slot machine is a winner, even without the jackpot, and we return 0. Finally, we determine the probability of the jackpot line coming up. If it's 0, then we return 1, since it doesn't matter what the jackpot is if we can never win it. Otherwise, we know that the expected outcome of the jackpot payoff must be sufficient to make our total expected outcome at least 1. So, solving the simple formula, the payout then needs to be at least (1  nonjackpot expected payout) / jackpot percentage. TestScoresUsed as: Division One  Level Three:
This is the type of problem where either you saw the solution and coded it, or you didn't. With a very high success rate among those who submitted a solution, obviously many saw the solution. The first thing to realize is that calculating the mean is simple: sum the probabilities of each question being answered correctly; standard deviation is a little more subtle. But, for a very large set of data, knowing the probability of obtaining each raw score (which, in the worst case ranged from 0 to 50) suffices to calculate the standard deviation. The procedure to do this is pretty simple:
I'll leave it as an exercise to the reader to work out exactly why that works. The final piece of the puzzle is simply calculating the probabilities of each raw score. Obviously, with 50 questions, there are 2^50 possible ways the questions could each be correct/incorrect, so a more efficient calculation is necessary. A simple dynamic programming approach works well. If P(a, n) is the probability that a of the first n questions were answered correctly, and Q(a) is the probability of an arbitrary person answering question a correctly, then we can use the recurrence P(a, n) = P(a  1, n  1) * Q(a) + P(a, n  1) * (1  Q(a)), P(0, 0) = 1 to build our DP. 
