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 floors, and an egg dropper with ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor or above, and will have no damage whatsoever if it is dropped from floor or below. The problem is to find a strategy such that the egg dropper can determine the floor 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.
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 to 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 break 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, and 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.
You are asked to find the highest floor of a 100-story building from which an egg can be dropped without breaking. You have two eggs to test-drop from the building, and you can continue to drop your eggs until they break.
From which floor should you 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 floor. If it doesn't break, you would drop the same egg from the 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 floor? If this happens, you are obligated to drop the remaining egg from each floor until finding , which has the potential for drop tests, which is .
Remember, the problem is to determine the critical floor , so you can't let your last egg break before finding it. Dropping your last egg from the floor would be quite risky because 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 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 breaks at floor 14?
If the first egg breaks at the floor, then we should check the first floor, then the second one, until the floor. Doing this the total number of attempts would be 14.
- What if it doesn't break?
Then you should check the floor. Why? Because if it breaks, you would have to check all the floors from the until the one (thirteen floors), which keeps the total number of attempts at 14 first attempt at the floor, second at the floor, and the twelve remaining drops from the floor until the floor
And if it doesn't break, you would have to check the floor; if it breaks you would have to check all the floors from the until the one. Remember, one attempt at the floor, the second attempt at the floor, the third attempt at the floor, and the 11 remaining attempts at the floors and 38, totaling 14 attempts in this case.
Using the same reasoning, you should check the floor, the , the , the , the , the , the , the and finally the 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.
Wonder how this table might look if there were 3 eggs!!...
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 floor and 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.
Now let's try to find a solution for the case where you have 2 eggs and a building with floors.
A good way to start this problem is to ask "Are we able to cover all the floors with drops?"
Suppose that in the best strategy, the number of drops in the worst case is . Then, you should start at the floor, because if the egg breaks, you will have to check floors and , so the total number of drops will be . If it doesn't break, you will have to check the floor. If the egg breaks, you will have to check the floors . Hence, the number of drops will be .
Do you realize what we are doing? Based on the assumption that the number of drops will always be 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 , and we have to determine if covering all the floors using at most 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 . In our attempt, we will drop the egg at the floor, covering floors, then we will drop it at the floor, covering floors, and the third drop would be at the floor, covering floors. We can see that using this strategy we would cover
If we are able to cover floors using this strategy and the building has floors, we just have to find the minimum value of such that
But must be an integer, implying
In our first example, , so plugging it into the previous equation gives .
Suppose you have eggs and you want to determine from which floors in a -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 and .
A solution that combines both binary search and recursion:
This is the faster one, and once the strategy is understood, it is rather easy to implement.
Imagine the following situation: you have eggs and consecutive floors yet to be tested, and afterward you drop the egg at floor in this sequence of consecutive floors:
If the eggs break:
The problem reduces to eggs and remaining floors.
If it doesn't break:
The problem reduces to eggs and 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 all three situations, we tested 20 floors.
Now we can define a function 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 :
Recursion for the egg dropping puzzle:
Pay attention: =current number of eggs, =total number of eggs, =number of consecutive floors that still have to be tested, =number of floors in the building.
The basis cases are as follows:
Because we need drops if only egg remains,
Because we need only one drop to test one floor, regardless of the number of eggs,
Because 0 floors requires no drops,
The pseudo-code 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
The previous solution is very slow, and the same function is called more than once, which is 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 two-dimensional 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
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
Before advancing to the next section, we must see some useful mathematical relations related to binomials.
We know that
We also know that the Pascal triangle is
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:
And the basis cases are
With this knowledge in hand, let's define a function that represents the number of floors we can cover using eggs and with remaining drops. If the egg breaks, we will be able to cover floors; otherwise we'll be able to cover floors. Hence, the total number of floors we will be able to cover is
We must find a function that's a solution for this recursion. First, we will define an auxiliary function :
Plugging it into our first equation gives
This is precisely the same recursion that we saw in the previous section, and thus the function can be written as
But we have a problem: is 0 for every , as well as , according to the relation between and . However, a contradiction occurs when because . But should be for every ! We can fix this problem by defining as follows:
And the recursion is still valid (you can check it by yourself!).
Now, using a telescopic sum for , we can write it as
We know that , and therefore
And we also know that
Now that we have a nice formula for how can we find the minimum number of drops?
It's simple! We know that is the number of floors we can cover in the building with floors using eggs and no more than drops in the worst cases. We simply have to find a value for such that
Using our last formula,
This solution is very fast. We can do a linear search to find a value for , or we can binary search it for an even faster 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Solution using binomials: