Menu
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?
Edit
265
Simplest answer The simplest way to obtain the minimal floor is to throw an egg from the first floor, then from the second and so on. This way when the egg is finally broken then we will know that this is the floor. This is a reliable algorithm, but in the worst-case scenario it would take 100 throws.
Egg dropping refers to a class of problems in which it is important to find the correct response without exceeding a (low) number of certain failure states. In a toy example, there is a tower of n floors, and an egg dropper with m ideal eggs.
From above two equations, we can say. ∑xCj >= k 1 <= i <= n Basically we need to find minimum value of x that satisfies above inequality. We can find such x using Binary Search.
To drop an egg without breaking it, wrap the egg in wet paper towels and place it in a plastic bag of puff rice cereal. Fill 4 small bags with puffed cereal too, then put all the bags into 1 large container. You can also wrap the egg in packing material, like bubble wrap, packing peanuts, or inflated plastic packets.
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)!
195
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
