Explain this O(n log n) algorithm for the Cat/Egg Throwing Problem

This problem (How many cats you need to throw out of a building in order to determ开发者_开发知识库ine the maximal floor where such a cat will survive. Quite cruel, actually), has an accepted answer with O(n^3) complexity. The problem is equivalent to this Google Code Jam, which should be solvable for N=2000000000.

It seems that the O(n^3) solution is not good enough to solve it. From looking in the solutions page, jdmetz's solution (#2) seems to be O(n log n). I don't quite understand the algorithm. Can someone explain it?

Edit

---

The top solution is actually O(D*B) (using problem's terminology), but the author noticed that for most D and B answer would be greater than 2^32 and thus -1 can be returned.
So, he introduces maxn equal to 1100 - the maximum D and F for which it makes sense to count.
For D, B = 10000 he returns -1 right away. For D, B = 100 recursive formula below is used. Only for some 'corner values', like D = 10000, B = 2, the direct formula is used. (see his comments for details about 'direct formula')

For D, B < maxn, author provides formula in the comments: f(d,b) = f(d-1,b)+f(d-1,b-1)+1. Function f here returns the maximum number of floors for which you can determine 'break point' using no more than d attempts and no more than b eggs.
Formula itself should be self-explanatory: no matter at which floor we throw first egg, there're two outcomes. It can break, then we can check up to f(d-1, b-1) floors below. Or it can 'survive', then we can check up to f(d-1, b) floors above. With the current floor, that makes it f(d-1,b)+f(d-1,b-1)+1 total.

Now, it can be easily coded as DP (dynamic programming). If you leave infinity (2^32) checks out, it gets pretty clean.

    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j] + 1;
        }
    }

When we have array f[D][B] storing those results, finding D' and B' is a binary search. (since function f grows monotonously by both d and b)

PS Although I did say in the answer to the 'cats' problem there's a faster solution, this is actually cooler than what I had in mind :) Thanks to you and sclo (author)!

---

Heavily edited due to question being corrected

Consider the function f(x,y) which gives the number of floors you can test with a limit of x throws and y deaths. If the first throw results in a death, you have x-1 throws and y-1 deaths remaining, so you can check f(x-1, y-1) floors. If the first throw doesn't result in a death, you have x-1 throws and y deaths remaining, so you can check f(x-1,y) floors above the one you threw from. Therefore we have the recurrence f(x,y) = f(x-1, y-1) + f(x-1, y) + 1. The base conditions are that f(x,0) = 0 (because if you make even one throw you risk a death, so you can make no throws and can't even check the first floor), and f(1,x) = 1 where x>0 (you have to make the only throw from the first floor, because if you throw from a higher floor and get a death you don't have a result).

Now, consider the function g(x, y) = SUM 1<=r<=y of ^xC_r. (That's a binomial coefficient, x choose r. I don't think the TeX notation is supported on this site). The assertion is that f(x, y) = g(x, y). To check the base cases, consider that g(x, 0) is a sum over 0 elements, so that matches; and g(1, y) where y>0 gives ¹C₁ = 1. So it just remains to check that g satisfies the recurrence.

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y-1 ^x-1C_r + SUM 1<=r<=y ^x-1C_r + 1

g(x-1, y-1) + g(x-1, y) + 1 = SUM 2<=r<=y ^x-1C_r-1 + SUM 1<=r<=y ^x-1C_r + 1

g(x-1, y-1) + g(x-1, y) + 1 = SUM 2<=r<=y ^x-1C_r-1 + SUM 1<=r<=y ^x-1C_r + ^x-1C₀

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y ^x-1C_r-1 + SUM 1<=r<=y ^x-1C_r

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y (^x-1C_r-1 + ^x-1C_r)

g(x-1, y-1) + g(x-1, y) + 1 = SUM 1<=r<=y (^xC_r)

g(x-1, y-1) + g(x-1, y) + 1 = g(x, y)

QED

In fact this can be derived directly by considering it as a combinatorial problem. If we make full use of every bit of information gained, then each possible sequence of survival or death corresponds to a different maximal floor. E.g. for three throws, one permitted death, the possibilities are death; survival-death; survival-survival-death; or survival-survival-survival. However, we have to discount the case that there are no deaths, because in that case we haven't determined the floor. So if we have x throws and y permitted deaths, we can have an actual number of deaths r from 1 to y, and for each of those we have ^xC_r possible sequences. (If r = y then any "survivals" after the y^th death are actually "didn't throw"s).

jdmetz's solution for F consists of evaluating g(D, B). It can't be done in better than O(min(D, B)) time because there's no closed hypergeometric form for that sum (which fact can be proven using Gosper's algorithm).

Addendum In fact, all three parts of the original problem can be done in linear time (assuming multiplication and arithmetic to be constant-time operations, which we have so far - not true, but we'll leave that aside). The O(n lg n) operation in jdmetz's solution is finding the smallest D such that f(D, B) >= F.

If we combine our original recurrence f(D, B) = f(D-1, B-1) + f(D-1, B) + 1 with the term difference from the form of g, f(D, B) = f(D, B-1) + ^DC_B we get f(D, B) = 2 * f(D-1, B) + 1 - ^D-1C_B. We can then use ^aC_b = ^a-1C_b * a / (a - b) to loop over D from 1.

    private static int d_opt(final long f, final int b)
    {
        int d = 0, dCb = 0;
        long f_db = 0;
        while (f_db < f)
        {
            dCb = (d == b) ? 1 : d * dCb / (d-b);
            f_db = 2 * f_db + 1 - dCb;
            d++;
        }
        return d;
    }