CODEWITHSUNDEEP
algorithmdynamic-programming
Jenna Kwon
Jenna Kwon

Reputation: 1252

Maximum number of floors you can test given C cases and D allowable drops

This question is from "Elements of Programming Interviews" and has puzzled me for a couple days.

The question reads, "Given c cases and D allowable drops, what is the maximum number of floors you can test in the worst-case"?

Assumptions are the following:

1) All cases have identical properties and if one breaks from a level, so will all others

2) A case that survives a fall may be used again but broken one is discarded

3) If a case breaks when dropped, then it would break if dropped from a higher floor. If it survives, it would survive a shorter fall.

To me, this question seems like a variant of a "generalized two egg problem" where you are trying to minimize the number of drops. This problem instead seeks to maximizes the number of floors, given a determined number of drops.

The recurrence relation given in the solution is the following:

F(c + 1, d) = F(c, d - 1) + 1 + F(c + 1, d - 1)

Where F(c, d) = max # floors we can test w/ c cases and d drops. This recurrence relation is confusing me, despite the book's explanation that the term on the right is the floor we proceed to in case a case doesn't break when tested at floor F(c, d - 1) + 1. My confusion is - what accounts for when case does break? This does not appear in the recurrence relation.

The question also poses additional question - solving the same problem with O(c) space. Implementing above recurrence relation would naturally render to dynamic programming with 2D memoization matrix. How would you do this with 1D array?

Upvotes: 1

Views: 182

Answers (1)

Sayalic
Sayalic

Reputation: 7650

How would you do this with 1D array?

1.rewrite your function to: F(c, d) = F(c - 1, d - 1) + 1 + F(c, d - 1)

2.write code as this:

for (i=1; i<=D; i++)
for (j=C; j>=0; j--)
  a[j] = a[j-1] + a[j] + 1

Explanation:

a[j](after assignment, a[j] equals F(c, d)) 
   = a[j-1](F(c-1, d-1)) + a[j](F(c, d-1)) + 1

My confusion is - what accounts for when case does break?

Test a case at floor x:

  1. if case survives, then you know the case never breaks on floor [1, x+1](corresponding 1 + F(c + 1, d - 1) in formula).
  2. if case breaks, then you know the case always breaks on floor [1, x].(corresponding F(c, d - 1) in formula)

Upvotes: 1

Related Questions