Came across the Google Egg Problem, which essentially says: Given n floors and m eggs, what is the approach to find the highest floor from which eggs can be thrown safely, while minimizing the throws (not broken eggs).  Most interesting is this answer by “Brandon”:

This entire “puzzle” is based on an assumption that an egg really can survive a 100 story drop. Personally I have never seen an egg fall more than about 8″ without breaking so this is a theoretical, hypothetical question with no factual basis. Both eggs could break after the 1st drop from the 1st floor which means your whole experiment is screwed…

Well said Brandon!  That kind of sense of humor is worth more than a dynamic programming solution I was working on silently.  🙂

But for the readers for whom humor will not suffice, here is a link to the original problem, at least the most original link I know.  The recursive formulation kind of goes like:

Let f(n,m) be the minimum number of attempts given n floors and m eggs. There is no guarantee that we will still have the egg intact after the test.

Then, f(n,1) = n   // We have no option but to climb floors one by one.

Similarly, f(1,m) = 1 // We just need one try if there is only one floor

The recursion is built around the first action – which floor do we try the first egg from.  If that is j, and if the egg breaks, then we have j-1 floors left, m-1 eggs left.  If the egg doesn’t break, then we have n-j floors and m eggs left.  Then the recursion we get is:

This leads to a straightforward dynamic programming formulation, which has mn entries in the DP table and each entry can be computed in at most n time, Therefore, the algorithm runs in O(n^2 m) time.

The time complexity can be improved to O(n m) by making two observations:

• optimal first attempt floor for (n,m) >= optimal first attempt floor for (n-1,m). So, when running the loop, we don’t need to start the j counter with one.
• Consider the function max{f(j-1,m-1),f(n-j,m)} as g(j,n,m). This function has the property that g(j,n,m) first decreases as j increases, then once it starts increasing, it never decreases again. [We could call this a “convex” function if it was a continuous function.]

Here are some sample results – the Java source code is here.

100 floors, 2 eggs.  Optimal number of attempts: 14  [Try first egg at floor # 9]     [This matches the result given here, but the floor number for first egg attempt is not the same.]
200 floors, 3 eggs.  Optimal number of attempts: 11  [Try first egg at floor # 25]
400 floors, 5 eggs.  Optimal number of attempts: 10  [Try first egg at floor # 19]
1000 floors, 3 eggs.  Optimal number of attempts: 19  [Try first egg at floor # 13]
1000 floors, 4 eggs.  Optimal number of attempts: 13  [Try first egg at floor # 207]
1000 floors, 5 eggs.  Optimal number of attempts: 11  [Try first egg at floor # 363]
1000 floors, 20 eggs.  Optimal number of attempts: 10  [Try first egg at floor # 489]
1000 floors, 30 eggs.  Optimal number of attempts: 10  [Try first egg at floor # 489]

Update 1: My first version of this post had a fatal flaw in it – a plus instead of a comma.  Catastrophic result, but problem wasn’t just a typo – problem was in approaching the recursion from a divide and conquer perspective, rather than a “first action” perspective.

Update 2: Nikita Rybak mentions that he has an O(n log n) solution.  If I find it, I will link it to the solution.  (Nikita: If you find it, can you put it up on your website?)

Update 3: Logical next question – what is the closed form expression of f(n,m)?

1. Nikita Rybak

Hi there,
Could you please describe your ‘straightforward dynamic programming formulation’? I particular, I’m interested in meaning of ‘k’ and why exactly we use ‘+’ operation in ‘f(..)+f(..)’. This ‘+’ hints exponential growth of answer, which is not realistic.

As for my solution, I’ve edited the SO answer with description. (it was pretty late when I wrote the answer, so the formula seemed absolutely obvious to me :))

Also, if you’re interested, there’s a O(n*logn) solution (although, not exactly evident). I submitted it on Timus five years ago, so it’s guaranteed to be correct.

Nikita

2. Amrinder Post author

Hi Nikita,

Firstly – obviously there is something wrong with my formula – either I messed up entirely or messed up the google chart API. I am at a conference past 2 days and today, and will get back later tonight or sometime tomorrow.

Thanks!
Amrinder

3. Amrinder Post author

Nikita – as you may have noticed, I fixed up the post. Tested the code too (using your code sample), and the link is in the post. Thanks!

4. Nikita Rybak

Amrinder,

O(n*logn) complexity can be reached by two optimizations.

1. There’s a solution I made 5 years ago giving O(n*m) complexity. The problem is, now I can’t prove all assumptions it makes, even though it generates correct result for any input.

2. You can notice that if we have no shortage of eggs, then the optimal strategy is a simple binary search. It’ll give us optimal number of attempts, ~ logn. (floor(logn) + 1, to be exact). It means, we can do something like this:

if (m > logn + 1) {
m = logn + 1;
}

So, technically complexity is O(n * min(m, logn)), but logn never gets too big, so I just remove ‘m’ part.

Now, if you want to see solution in 1, drop me a mail. Posting it in a comment will probably screw code and I don’t have any personal website (I’m not into blogging in general).
I’m thinking about posting it on SO, but want to try to prove it first. And anyway, on SO there’re no more than a few people who would care about such optimization.

5. Amrinder Post author

Your m vs log n comment is clear. So, it is essentially the O(mn) proof that we really want. If you would like, you can send it to me. My email is aarora at this domain name.

Also, there may be one idea to optimize (perhaps your proof uses it): Essentially, when looking f(n,m), we are using 2m numbers. One set of numbers are in the same row (n-j,m), Second set of numbers is in the previous column (m-1,j-1). As we slide to right to compute f(n+1,m) we can use the row of numbers, delete the left most number, and adding f(n,m), and possibly avoiding the O(m) time to compute a table cell. (just a thought at this point.)

6. Amrinder Post author

And obviously, not to forget that the numbers in the row are in non-decreasing order (when traversing to the right), and the numbers in the column are in non-increasing order (when traversing upwards).