Match Editorial

This afternoon's challenge was one of the wackiest in recent memory. Division 2 featured a couple of math problems that could lead to issues of double imprecision if solved the wrong way, and a simple dynamic programming problem about binary search trees. Division 1 seemed very simple at first glance, with almost everyone submitting the first two problems. And while the 450 ended up being as simple as it looked, the 300 timed out in a way that was not caught by the examples. As a result, almost everyone submitted the 300 immediately, only to find out during the challenge phase that the examples were less than exhaustive. This allowed InsaneParadox to get a whopping 11 challenges on one problem, probably a new TC record.

The Problems

Value	250
Submission Rate	192 / 202 (95.50%)
Success Rate	116 / 192 (60.42%)
High Score	anup for 249.33 points

To find the overall rate, all you have to do is take each individual rate times the associated probability, and add all that up. At the end, divide by 100, since probabilities are always percent/100.

Value	550
Submission Rate	164 / 202 (81.19%)
Success Rate	101 / 164 (61.59%)
High Score	anup for 544.28 points

This problem required a bit of trickery. The task given to you is very simple: Given a formula, find the smallest integer that satisfies it. However, the formula involves large exponents which produce numbers that are so large, they even overflow double, which goes up to around 10^300. So, to make it work, you have to use the log identities given to you as a note:

log(x^y) = y * log(x)
log(x*y) = log(x) + log(y)

Value	1000
Submission Rate	64 / 202 (31.68%)
Success Rate	54 / 64 (84.38%)
High Score	BryanChen for 986.41 points

Value	450
Submission Rate	90 / 118 (76.27%)
Success Rate	87 / 90 (96.67%)
High Score	John Dethridge for 444.93 points

Reference Solution: John Dethridge

Trying to construct all of the BST's and then count them is an approach that would probably work, since there are at most 10 nodes, but it would probably take quite a long time to do. Instead, you should use a little bit of dynamic programming (or catalan number, more on that later). The first thing to notice is that the numbers on the nodes are of no consequence. Furthermore, we can pick the root node in such a way that there are anywhere i nodes in the left subtree, and n-i-1 nodes in the right subtree, where n is the total number of nodes. Since each subtree is itself a BST, we can count the number of BSTs with i nodes, and the number with n-i-1 nodes, and multiply those two numbers together to get the total number of BSTs with a given root. So, we can define a recurrence bst(n) = sum(i = 0 to n-1)(bst(i)*bst(n-i-1)), with a base case of bst(0) = 1. An iterative approach is the quickest way to solve this, which can be seen in John Dethridge's solution.

This is a fairly well-known problem, and it turns out that it can be solved with a simple closed form solution, called a Catalan number:C(2n,n)/(n+1), where C means stands for choose (C(m,n) = fact(m)/fact(n)/fact(m-n)). It turns out that the number of BSTs with n nodes is exactly equal to the nth Catalan number. For more on Catalan numbers, check out what MathWorld has to say about them.

Value	300
Submission Rate	115 / 118 (88.97%)
Success Rate	55 / 115 (47.83%)
High Score	RyanPai for 289.09 points

Reference Solution: WishingBone

This problem appears to be absolutely trivial. So trivial in fact, that one has to wonder about the 300 points assigned to it. Most people looked at it, and right away and coded it up exactly as given. This solution passed the examples, and a number of people submitted for scores of around 299. However, as a result this problem ended up with what was probably the lowest submission accuracy ever. If one spends a couple minutes to look at the recurrence, he or she would realize that it is far from obvious how many recurrences it will take. The moral of the story is that the given examples are not always exhaustive, even on the easy problems. Especially when it is relatively simple to try a few large numbers, as in this case, you should invest the minute or two it will take. That rant over, on the the problem analysis.

The naive implementation is very close to correct and can easily be fixed to work by using a technique called memoization. To do this, we simply have to cache the results of our recursion, and use the cache if we already know the result. WishingBone's implementation is a good example of how to do this. The idea is that, for a given value of m and n, f always evaluates to the same thing. So, there is no need to reevaluate the function each time. Instead, we save the returned value of f for each input m and n, and then if f gets called again, we just used the saved value. You can do the same thing with g.

Another way to solve this is iteratively, as seen in Maris's code. The trick to this approach is to realize that f(m,n) depends only on f(m-1,n) and g(m-1,n-1). Similarly g(m,n) depends only on f(m,n) and g(m,n-1). So, if we already know f(m-1,n) and g(m-1,n-1), it is easy to calculate f(m,n). You can do essentially the same thing with g. As a result, the problem can be solved easily with two nested for loops.

Though no one realized it during the contest, it turns out that f(m,n) = sum(i = 1 to n)i^m. For a proof of this, click here.

Value	1000
Submission Rate	25 / 118 (21.19%)
Success Rate	12 / 25 (48.00%)
High Score	John Dethridge for 828.78 points

Reference Solution: John Dethridge

This is a fairly standard dynamic programming problem. There are 2^(number of lanes) possible configurations of lights being on or off. So, what we should do, is initialize an array with 2^lanes elements, and set them all to 0, except for the element representing all off. Then, for each time that the ball goes up and back down, we need to calculate the probabilities that the lights are in each possible configuration. To do this, we can simple look at all possible paths that the ball can take for each configuration. So, we have something that looks like this:

int state[1<<lanes];
state[0] = 1;//0 represents all off, and in general, the ith bit represents the ith light.
foreach(time){
    int nextState[1<<lanes];
    foreach(state s){
        foreach(lane i){
            foreach(lane j){
                nextState[s with up and down lanes toggled] += 
                  state[s]*(probability of rolling down lane j, given it rolled up lane i);
            }
        }
    }
    state = nextState;
}