Your boss has given you an assignment to find the lowest floor in your n floor b

Question

Your boss has given you an assignment to find the lowest floor in your n floor building such that dropping a mug from that floor to the ground will cause the mug to break. Your boss has given you k mugs to use for testing, where a test is simply done by going to a floor and dropping a mug from that floor. If the mug breaks when you drop it, you can not use that mug again, but you also know that you don’t have to consider any higher floors. Likewise, if the mug does not break, you can use it again, and you know that dropping a mug on a lower floor will still not cause the mug to break. There are many different strategies for deciding where to do your tests, and your strategy should minimize the number of tests you have to conduct in the worst case. Give a O(n2k) time Dynamic Programming algorithm to determine, in the worst case, how many tests you will need to conduct.

NOTE: The answer does not need to be coded in any language or pseudocode, just give a step-by-step algorithm in english of how to achieve this so that I may be able to understand it.

Explanation / Answer

Imagine we drop our first egg from floor n, if it breaks, we can step through the previous (n-1) floors one-by-one.

If it doesn’t break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to one-by-one floors), so the next floor we should try is floor n + (n-1)

Similarly, if this drop does not break, we next need to jump up to floor n + (n-1) + (n-2), then floor n + (n-1) + (n-2) + (n-3) …

We keep reducing the step by one each time we jump up, until that step-up is just one floor, and get the following equation for a 100 floor building:

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

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.