Match Editorial

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 Problems

Value	250
Submission Rate	149 / 170 (87.65%)
Success Rate	119 / 149 (79.87%)
High Score	lingo for 248.68 points (2 mins 4 secs)
Average Score	212.18 (for 119 correct submissions)

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.

Value	600
Submission Rate	83 / 170 (48.82%)
Success Rate	63 / 83 (75.90%)
High Score	nickel for 522.10 points (11 mins 19 secs)
Average Score	323.80 (for 63 correct submissions)

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 non-overlapping (note however, that all result 1 values could be less than the result 0 values, or vice versa), that variable is a predictor.

Value	800
Submission Rate	60 / 170 (35.29%)
Success Rate	14 / 60 (23.33%)
High Score	Oleksiy for 669.55 points (13 mins 4 secs)
Average Score	514.14 (for 14 correct submissions)

Value	250
Submission Rate	115 / 129 (89.15%)
Success Rate	44 / 115 (38.26%)
High Score	haha for 245.78 points (3 mins 44 secs)
Average Score	201.56 (for 44 correct submissions)

This is a classic type of problem that can be solved very easily once you see the "ah-ha". In this case, the big "ah-ha" 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.

Value	500
Submission Rate	103 / 129 (79.84%)
Success Rate	37 / 103 (35.92%)
High Score	LuckyLibran for 438.05 points (11 mins 0 secs)
Average Score	310.45 (for 37 correct submissions)

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 non-jackpot 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 - non-jackpot expected payout) / jackpot percentage.

Value	800
Submission Rate	42 / 129 (32.56%)
Success Rate	40 / 42 (95.24%)
High Score	antimatter for 769.78 points (5 mins 40 secs)
Average Score	548.22 (for 40 correct submissions)

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:

• For each raw score value, multiply the probability times the square of the deviation from the mean
• Add up each of the values obtained above.
• Calculate the square root of that sum.

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.