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

We will solve this problem to a general problem with k mugs and n floors.

Optimal Substructure:

When we drop a mug from a floor x, there can be two cases (1) The mug breaks (2) The mug doesn’t break.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.

n = Number of Floors

k = Number of Mugs

mugDrop(k, n) = Minimum number of trails needed to find the critical floor in worst case.

mugDrop(k, n) = 1 + min{max(muggDrop(k - 1, x - 1), mugDrop(k, n - x)) , Where x = {1, 2, ..., n}}

Procedure with Example:

Here we are using the Binary Search Method. For example let n=100floors.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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