Take the 2-minute tour ×

This problem (How many cats you need to throw out of a building in order to determine 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?


share|improve this question
Explanation of an algorithm seems like a suitable question for StackOverflow to me. –  Mark Byers Jan 15 '11 at 10:29
It can be migrated to Algorithms once it's up: area51.stackexchange.com/proposals/5120/… –  ripper234 Jan 15 '11 at 10:37
If this algorithm was O(n*logn) (regardless of which of three variables you denote n), it would still be too slow. n is up to 10^9. –  Nikita Rybak Jan 15 '11 at 11:49
If you see my latest update to my answer, I can do better than O(n lg n). –  Peter Taylor Jan 17 '11 at 8:09
add comment

2 Answers

up vote 7 down vote accepted

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)!

share|improve this answer
This is still not good enough, but can be tweaked. I implemented these few optimizations: 1. Only iterate from b=2, not b=1. 2. Stop iteration once you overflow maxint, and save a map maxBForD (for a given D, the max B that doesn't overflow). 3. Save maxDForB2 (max D that doesn't overflow for B>=2). Finally, this works :) Code available on github: github.com/ripper234/Basic/blob/master/java/src/main/java/org/… –  ripper234 Jan 15 '11 at 13:34
This doesn't answer the (changed) question, which was amended to refer to jdmetz's solution. –  Peter Taylor Jan 15 '11 at 19:50
add comment

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 xCr. (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 1C1 = 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-1Cr + SUM 1<=r<=y x-1Cr + 1

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



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


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


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 xCr possible sequences. (If r = y then any "survivals" after the yth 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) + DCB we get f(D, B) = 2 * f(D-1, B) + 1 - D-1CB. We can then use aCb = a-1Cb * 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;
        return d;
share|improve this answer
Sorry, I was looking at the wrong file. Take a look at jdmetz's solution - it's O(n) for getMaxF() and getMinB(). getMinD() is implemented using a binary search of getMaxF() - total O(n log n) –  ripper234 Jan 15 '11 at 11:21
I thought F might be related to Pascal's triangle, and now I see I was right. Still haven't proved it, but it's what jdmetz's code does. First observation: if j > i then F[i][j] = F[i][i], because you can't have more deaths than thrown cats. Therefore we can consider only the triangle formed with i>=0, 0<=j<=i. If we make i index the row, F[i][j] + 1 forms Bernoulli's triangle ( oeis.org/wiki/Bernoulli%27s_triangle ), the partial sums of rows of Pascal's triangle. –  Peter Taylor Jan 15 '11 at 11:51
add comment

Your Answer


