9

I am reading Robert Sedgewick's algorithms 4th edition book, and he has the following task:

Suppose that you have an N-story building and 2 eggs. Suppose also that an egg is broken if it is thrown off floor F or higher, and unbroken otherwise. Your cost model is the number of throws. Devise a strategy to determine F such that the number of throws ~c √ F for some constant c.

The first part of the task is to find F in 2 √ N steps, and here's a solution for that:

Solution to Part 1:

  • To achieve 2 * sqrt(N), drop eggs at floors sqrt(N), 2 * sqrt(N), 3 * sqrt(N), ..., sqrt(N) * sqrt(N). (For simplicity, we assume here that sqrt(N) is an integer.)
  • Let assume that the egg broke at level k * sqrt(N).
  • With the second egg you should then perform a linear search in the interval (k-1) * sqrt(N) to k * sqrt(N).
  • In total you will be able to find the floor F in at most 2 * sqrt(N) trials.

He also provides a hint for the ~c √ F part (part 2):

Hint for Part 2: 1 + 2 + 3 + ... k ~ 1/2 k^2.

So what is the algorithm to do it in ~c √ F steps?

Steve
  • 1,553
  • 2
  • 20
  • 29
Pavel
  • 1
  • 3
  • 17
  • 51
  • 1
    Here is a question discussing the general case of the first part, but using cats instead of eggs. http://stackoverflow.com/questions/3974077/throwing-cats-out-of-windows?rq=1 – Klas Lindbäck Apr 30 '15 at 11:41
  • This is a popular interview question in Bay Area 10 years ago. even google ask this question to candidates too. :) – BufBills Apr 30 '15 at 14:03
  • @BufBills, thanks, do you understand how the algorithm the the accepted answer works? I really don't understand why it gives 14 for 100 floors and 2 cats, shouldn't it be 51? We can first look at floor 50, then from floor 51 and up we have to only do linear search because we only have 1 cat left.. – Pavel Apr 30 '15 at 16:28
  • n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100 This summation, as many will recognize, is the formula for triangular numbers (which kind of makes sense, since we’re reducing the step by one each drop we make) and can be simplified to: n (n+1) / 2 >= 100 This is a quadratic equation, with the positive root of 13.651 (Which we have to round up to 14. This is not a John Malkovich movie!). – BufBills Apr 30 '15 at 16:38
  • @BufBills no, I'm talking about the other question! I meant to ask Klas Lindback, sorry – Pavel May 01 '15 at 09:14
  • @KlasLindbäck do you understand how the algorithm the the accepted answer works(in the link that you sent)? I really don't understand why it gives 14 for 100 floors and 2 cats, shouldn't it be 51? We can first look at floor 50, then from floor 51 and up we have to only do linear search because we only have 1 cat left. – Pavel May 01 '15 at 09:15
  • Let's say you have 14 tries. How high a building can you cover? Throw the first egg off floor 14 (leaving 13 tries to cover floors 1-13 if the egg breaks). Next throw it off floor 14+13=27 (leaving 12 tries to cover the intervening floor). Then keep going like that. With 14 tries you can cover a building that is up to (14+13+12+11+10+9+...+1=) 105 stories high. The formula is actually generic, so with k tries you can cover a building that is up to (1+2+...+k=) `k*(k+1)/2` stories high. – Klas Lindbäck May 03 '15 at 18:23
  • @KlasLindbäck thanks, how did you figure it out though? – Pavel May 03 '15 at 19:18
  • By reading (actually skimming) the linked page and Henriks answer to this question and then thinking about what they have in common (and how they differ). As you can see, the sum 1+2+3+4+... appears in both! Note that problem solving skills is a function of aptitude, education and practice, so keep practicing! How to improve one's problem solving skills, that's a good subject for a blog post... – Klas Lindbäck May 04 '15 at 08:26
  • @KlasLindbäck yeah, i participate in codeforces.ru competitions every week, but I'm not that good yet – Pavel May 04 '15 at 17:33

1 Answers1

6

Drop first egg from floors 1, 3, 6, ... (the partials sums of 1, 2, 3, ...). Then do linear search between last two floors.

Henrik
  • 23,186
  • 6
  • 42
  • 92