Egg Dropping
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. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor \(n^*\) or above, and will have no damage whatsoever if it is dropped from floor \(n^*1\) or below. The problem is to find a strategy such that the egg dropper can determine the floor \(n^*\) in as few egg drops as possible. This problem has many applications in the real world such as avoiding a call out to the slow HDD, or attempting to minimize cache misses, or running a large number of expensive queries on a database.
Contents
\(2\) eggs, \(100\) floors
Suppose you have two eggs and you want to determine from which floors in a one hundred floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy.
If the egg doesn't break at a certain floor, it will not break at any floor below
If the eggs breaks at a certain floor, it will break at any floor above
The egg may break at the first floor
The egg may not break at the last floor
One would be tempted to solve this problem using binary search, but actually this is not the best strategy, you will see why. Try to work it out yourself and answer this question, or read on to see a detailed explanation of the problem.
From which floor should drop your first egg to optimize your chances of dropping the eggs as few times as possible?
Using binary search, you would have to drop the first egg from the \(50^\text{th}\) floor. If it doesn't break, you would drop the same egg from the \(75^\text{th}\) and so on, in the best case scenario you would be able to cover all floors with 7 drops.
But what if the egg broke in your first attempt, i.e in the \(50^\text{th}\) floor? If this happens you are obligated to drop the remaining egg from each floor until finding \(n^*\), which has the potential for \(49\) drop tests, which is \(O(n)\).
Remember, the problem is to determine the critical floor \(n^*\), so you can't let your last egg break before finding it. Dropping your last egg from the \(25^\text{th}\) floor would be quite risky, if it broke you wouldn't be able to determine the critical floor. It is clear that binary search is not the optimal solution. Knowing that, what is the best strategy? From which floor should you start? What's the minimum number of drops you would have to do in the worst case while using the best strategy?
Starting from the \(14^\text{th}\) floor is the best strategy because, as we will show, the number of attempts in the worst case is always 14.
 What if the first egg drops at floor 14?
If the first egg breaks at the \(14^\text{th}\) floor then we should check the first floor, then the second one, until the \(13^\text{th}\) floor. Doing this the total number of attempts would be 14.
 What if it doesn't break?
Then you should check the \(27^\text{th}\) floor. Why? Because if it breaks, you would have to check all the floors from the \(15^\text{th}\) until the \(26^\text{th}\) one (thirteen floors), which keeps the total number of attempts at 14 (First attempt at the \(14^\text{th}\) floor, second at the \(27^\text{th}\) floor, and the twelve remaining drops from the \(15^\text{th}\) floor until the \(26^\text{th}\) floor).
And if it doesn't break, you would have to check the \(39^\text{th}\) floor, if it breaks you would have to check all the floors from the \(28^\text{th}\) until the \(38^\text{th}\) one. (Remember, one attempt at the \(14^\text{th}\) floor, the second attempt in the \(27^\text{th}\) floor, the third attempt at the \(39^\text{th}\) floor, and the 11 remaining attempts at the floors: \(\{28,29,30,31,32,33,34,35,36,37\}\) and 38 , totaling 14 attempts in this case).
Using the same reasoning, you should check the \(50^\text{th}\) floor, the \(60^\text{th}\), the \(69^\text{th}\), the \(77^\text{th}\), the \(84^\text{th}\), the \(90^\text{th}\), the \(95^\text{th}\), the \(99^\text{th}\) and finally the \(100^\text{th}\) one. See? Using this strategy you would cover all the floors and the number of attempts would never be greater than 14, even in the worst cases.
Using other strategies, like the binary search, fewer attempts would be required in some cases (like in our first example), but it would require a high number of attempts in the worst case (in our second example, where the egg broke in the \(50^\text{th}\) floor, 50 drops were necessary in the worst case).
Therefore we can conclude that using another strategy you would need more than 14 attempts in the worst case.
\(2\) eggs, \(k\) floors
Now let's try to find a solution for the case where you have 2 eggs and a building with \(k\) floors.
A good way to start this problem is to ask: "Are we able to cover all the floors with \(x\) drops?"
Suppose that in the best strategy, the number of drops in the worst case is \( x \). Then, you should start at the \(x^\text{th}\) floor, because if the egg breaks, you will have to check floors \(1,2,3\ldots,x2\) and \(x1\), hence the total number of drops will be \(x\). If it doesn't break, you will have to check the \(\left(x+(x1)\right)^\text{th}\) floor. If the egg breaks, you will have to check the floors \(x+1,x+2, \ldots, \left(x+(x1)1\right)\). Hence, the number of drops will be: \(\left(x+(x1)1\right)(x1)+1+2=x\).
Do you realize what we are doing? Based the assumption that the number of drops will always be \(x\) in the worst case, we find the floors where we should drop the egg. The crucial point here is understanding that we are not trying to find the minimum number of drops knowing the best strategy, actually, we are trying to find the best strategy supposing that the minimum number of drops is \( x \), and we have to determine if covering all the floors using at most \( x \) attempts is possible or not.
We can find an analytical solution to this problem
Suppose the minimum number of attempts in the worst case, while using the best strategy, is \(x\). In our attempt, we will drop the egg at the \( x\) th floor, covering \(x\) floors, then we will drop it at the \(\left(x+(x1)\right)^\text{th}\) floor, covering \(x1\) floors, the third drop would be at the \( \left(x+(x1)+(x2)\right)^\text{th}\) floor, covering \( x2\) floors. We can see that using this strategy we would cover:
\[ x+(x1)+(x2)+(x3) + \ldots + 2+1=\frac{x(x+1)}{2} \]
floors.
If we are able to cover \(\frac{x(x+1)}{2}\) floors using this strategy and the building has \(k\) floors, we just have to find the minimum value of \(x\) such that:
\[\frac{x(x+1)}{2} \geq k \]
Hence:
\[ x^2+x2k=0 \implies x = \frac{1+\sqrt{1+8k} }{2} \]
But x must be an integer, hence:
\[ x = \displaystyle \lceil \frac{1+\sqrt{1+8k} }{2} \rceil \]
In our first example, \(k=100\), plugging it into the previous equation: \(\lceil 13.65\rceil = 14\).
\(N\) eggs, \(k\) floors
Suppose you have \(N \) eggs and you want to determine from which floors in a \( k \)floor building you can drop an egg such that is doesn't break. You are to determine the minimum number of attempts you need in order find the critical floor in the worst case while using the best strategy. Now the problem is a bit more complicated because we must find a general solution for any number of eggs and floors. There are three different solutions:
The recursive solution: This solution is more straightforward and can be implemented with ease, but it is also the slowest one. Using this solution on programming contests is not advisable due to its bad performance.
The Dynamic Programming Solution: This solution is similar to the previous one, but it's faster and may be used to solve the problem for medium or small values of \(k \) and \( N\).
A solution that combines both binary search and recursion, this is the faster one, and once the strategy is understood, is rather easy to implement.
Recursive solution
Imagine the following situation: you have \(n \) eggs and you have \( h\) consecutive floors yet to be tested*, and afterward you drop the egg at floor \(i\) in this sequence of \(h\) consecutive floors:
 If the eggs breaks:
The problem reduces to \( n1 \) eggs and \( i1 \) remaining floors.
 If it doesn't break:
The problem reduces to \( n \) eggs and \(hi\) remaining floors. This is an important point. The floors we want to test aren't important, in fact, the number of remaining floors is what matters. For example, testing the floors between 1 and 20 (both 1 and 20 included) , would require the same number of drops to test the floors between 21 and 40, or between 81 and 100, in the the three situations, we tested 20 floors.
Now we can define a function \( W(n,h)\) that computes the minimum number of drops required to find the critical floor in the worst case scenario, whilst using the best strategy.
We can codify the above findings to find the following recursion for determining \( W(n,h)\):
Recursion for the egg dropping puzzle
\[ W[n,h]=1+\min(\max (W(n1,i1),W(n,hi))\]
(Pay attention: \(n\)=current number of eggs, \(N\)=total number of eggs, \(h\)=number of consecutive floors that still have to be tested, \(k\)=number of floors in the building )
And the basis cases are:
\[W(1,h)=h\]
Because we need \(h\) drops if only \(1\) egg remains,
\[W(n,1)=1\]
Because we need only one drop to test one floor, regardless of the number of eggs. And:
\[W(n,0)=0\]
Because 0 floors requires no drops.
The pseudocode for this algorithm is given by
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

C++ code that uses the recursive solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 

DP Solution
The previous solution is very slow, the same function is called more than once, and this not necessary. However, due to its overlapping subproblems, and to its optimal substructure property (we can find the solution to the problem using the subproblem's optimal solutions), we can solve the problem via dynamic programming.
We can avoid recalculation of the same subproblems by memoizing the function egg(n,h)
with a twodimensional array numdrops[n][h]
. Then, we just have to fill it up.
Here's the pseudocode:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 

C++ code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 

Working with binomials
Before advancing to the next section we must see some useful mathematical relations related to binomials.
We know that:
\[C^n_k=C(n,k)= \binom{n}{k} = \frac{n!}{k!(nk)!}\]
We also know that the pascal triangle is:
(Image from: Wikipedia)And we can easily find a recursion if we write the Pascal Triangle in this way:
By looking at the table or by a simple mathematical proof we get the following recurrence:
\[ C ( n , k ) = C( n  1 , k ) + C ( n  1 , k  1 ) \]
And the basis cases are:
\[ C(n,0) = \frac{n!}{0!(n0)!} = 1 \]
and,
\[ C(n,n )= \frac {n!} {n!(nn)!} = 1 \]
A better approach
With this knowledge in hand, let's define a function \( f(d,n) \) that represents the number of floors we can cover using \( n \) eggs and with \(d \) remaining drops. If the egg breaks we will be able to cover \( f(d1,n1) \) floors, otherwise we'll be able to cover \( f(d1,n) \) floors. Hence, the total number of floors we will be able to cover is:
\[ f(d,n) = 1 + f(d1,n1) + f(d1,n) \]
We must find a function \( f(d,n) \) that's a solution for this recursion. First, we will define an auxiliary function: \( g(d,n) \):
\[ g(d,n)=f(d,n+1)f(d,n) \]
Plugging it into our first equation we can see that:
\[\begin{align} g(d,n) &= f(d,n+1)f(d,n) \\ &= f(d1,n+1)+f(d1,n)+1f(d1,n)f(d1,n1)1\\ &=[f(d1,n)f(d1,n)]+[f(d1,n)f(d1,n1)] \\ &=g(d1,n)+g(d1,n1) \end{align}\]
This is precisely the same recursion that we saw in the previous section, thus the function \( g(d,n) \) can be written as:
\[ g(d,n)= \binom{d}{n} \]
But we have a problem: \( f(0,n) \) is 0 for every \( n \), as well as \( g(0,n) \), according to the relation between \(f\) and \(g\). However, a contradiction occurs when \(n=0\). Because \(g(0,0)=\binom{0}{0}=1\), but \(g(0,n\) should be \(0\) for every \(n\)! We can fix this problem defining \(g(d,n)\) as:
\[ g(d,n)= \binom{d}{n+1} \]
And the recursion is still valid (you can check it by yourself!).
Now, using a telescopic sum for \( f(d,n) \), we can write it as:
\[\begin{align} f(d,n)= &[f(d,n)f(d,n1)]\\ +&[f(d,n1)f(d,n2)]\\ +&\ldots \\ +&[f(d,1)f(d,0)] \\ +&f(d,0) \end{align}\]
We know that \(f(0,d)=0\), therefore:
\[ f(d,n)=g(d,n1)+g(d,n2)...+g(d,0)\]
And we also know that:
\[ g(d,n)=\binom{d}{n+1} \]
Hence:
\[ g(d,n1)+g(d,n2)...+g(d,0)=\binom{d}{n}+\binom{d}{n1}+\ldots+\binom{d}{1}\]
Finally:
\[ f(d,n) = \sum_{i=1}^{n}{\binom{d}{i}} \]
Now that we have a nice formula for \( f(d,n)\) how can we find the minimum number of drops?
It's simple! We know that \( f(d,N) \) is the number of floors we can cover in the building with \(k\) floors using \(N\) eggs and no more than \( d \) drops in the worst cases. We simply have to find a value for \( d \) such that:
\[ f(d,N) \geqslant k \]
Using our last formula:
\[ \sum_{i=1}^{N}{\binom{d}{i}} \geqslant k \]
This solution is very fast. We can can do a linear search to find a value for \( d \), or we can binary search it for an even faster solution!
C++ code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 

Complexity
DP Solution:
Solution using binomials: