Explain this O(n log n) algorithm for the Cat/Egg Throwing Problem
- by ripper234
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