CLDROP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Nibir Pal
Tester: Soumyadeep Roy
Editorialist: Soumik Sarkar

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

This is just a version of the problem commonly known as the Egg Dropping Puzzle. Provided with N concrete blocks and H floors, it is possible to determine the floors from which a block will break when dropped. The following rules are in effect-

  • All blocks are identical.
  • A block if after dropped doesn't break can be used again for another drop.
  • If a block does not break being dropped from floor **X** then it will not break when dropped from any floor below **X**.
  • If a block breaks being dropped from floor **Y** then it will break when dropped from any floor above **Y**.

The aim is to find the maximum number of drops required to determine the height above which the blocks always break and below which they don’t, if an optimum strategy is used.

EXPLANATION:

Consider we have M usable blocks and we drop a block from floor X. We use one drop. Now there can be only two outcomes:

  1. The block breaks. In this case we now need to check for M$-1** blocks and the floors below it, which number **X-$1.
  2. The block does not break. In this case we can reuse out block, and are left with M blocks and the floors above X, which number H$-$X.

Thus we can recursively define out required function as:
f(N, H) = 1$+min(max(f(N-1, X-1), f(N, H-X))** for all **X** such that **1<=X<=$H)
Our base case would be when N equals 1 or H equals 1. When N equals 1, we need to drop our single block from each floor in turn, thus requiring H drops. When H equals 1, only 1 drop is needed.

Since this problem shows both optimal substructure and overlapping subproblems, we use dynamic programming to solve it. Currently our method requires a table of size N$H** and time complexity **O(N$H^2).

However, another observation can be made to decrease both these requirements drastically, which is that the minimum number of drops required for any particular H decreases with increase in the number of blocks provided, but it can NEVER go below log2(H)$+$1. Here is a table to illustrate this fact.

      Floors 1     7     200     512
Blocks
1            1     7     200     512
2            1     4      20      32
3            1     3      11      15
4            1     3       9      11
5            1     3       8      10
6            1     3       8      10
7            1     3       8      10
8            1     3       8      10

One may also observe that there is a minimum number of blocks from and above which the answer is always log2(H)$+1**, and that this number is always **<= log<sub>2</sub>(H)+1**. Thus a dp table of size maximum possible **N** multiplied by log<sub>2</sub>(**maximum possible H**)+1 is all that we need, which turns out to be **5000*13**. To further decrease time complexity, we can proceed to fill our table floorwise, and whenever we get a value **log<sub>2</sub>(current floor)+$1, we know that all following values will be the same, so we simply skip those calculations.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

1 Like