Throwing eggs from a building

10

1

This is exercise problem 1.4.24 from Robert Sedgewick's Algorithms 4th Edition.

``````Suppose that you have an N-story building and plenty of eggs. Suppose also that
an egg is broken if it is thrown off floor F or higher, and unhurt otherwise.
First, devise a strategy to determine the value of F such that the number of
broken eggs is ~lgN when using ~lgN throws, then find a way to reduce the cost to
~2lgF.
``````

While the `lgN` solution is easy to think up, I totally have no idea about the `2lgF` solution. Anyway, we are not given the value of `F`, so where the ground of `2lgF` solution is?

Can anyone give some light on this question? Thanks.

it's a search problem given an ordered set. maybe that helps :). – Randy – 2013-07-01T12:38:08.553

Hay Randy, any links or further reading? – Guibao Wang – 2013-07-01T12:39:39.103

Do binary search on the building, drop from n/2 floor, if it is broken, then go down which is n/4 and so one. So u may break at most lgN eggs and will get to that point in lgN steps – Elbek – 2013-07-01T12:41:40.287

possible duplicate of Generalised Two-Egg Puzzle

– David Eisenstat – 2013-08-03T00:39:11.277

15

logN: start at the top, always cut search space in half -> binary search

2 * logF start at 1, next 2, 4, 8 (i.e., 2^i), once the egg breaks (after log F steps) do binary search in the smaller search space (range < F and hence number of searches < log F) --> exponential search

Nice explanation, very useful. @timothy-shields your solution's good as well, thanks very much. – Guibao Wang – 2013-07-01T12:54:02.447

And how does that determine the value of F? – Pavel – 2015-04-30T09:32:48.070

I don't understand how in the lgN part we get lgN broken eggs with lgN throws, if we keep dividing we get to the 1st floor at the end, but what if F = 7 and N = 8? we don't get lgN broken eggs.

In the 2lgF part I don't understand how we get 2lgF broken eggs either, sounds like you just do 2lgF steps but your amount of broken eggs is 1. – Pavel – 2015-04-30T09:53:34.540

Ohh, okay, sorry, I thought that the point of the exercise was to achieve the given number of broken eggs, but it's actually to find F, thanks. I get really confused with these exercises, most of the time I don't understand what they ask. – Pavel – 2015-04-30T09:58:13.467

4

The `lg(F)` solution is to do `1, 2, 4, 8, ...` until the first egg breaks at `2^(k+1)`, then do a binary search in the range `2^K` to `2^(k+1)`.

Another alternative is to carry out the same process until the first egg breaks at `2^(k+1)` then start over except adding `2^k` to each height: `2^k + 1, 2^k + 2, 2^k + 4, 2^k + 8, ...`. You can keep repeating this process to keep reducing the size of the range you do exponential search in.