## Monday, February 9, 2009

### Dropping Swarovski Crystals

A building of 100 floors, there is a threshold N s.t. if a Swarovski Crystal from Nth floor and above it will break. If it's dropped from any floor below, it will not break. Given 2 Crystals, find this N, and minimize the number of drops for the worse case.

1. Given N=100, a sqrt(N) solution is to drop the first crystal every sqrt(N) step -- complexity sqrt(N). Suppose that the 1st crystal breaks at step j but not at step j-1, then the second crystal can be used to linear scan all the floors starting from the one following the j-1 test up to the one preceding the j test.

This is a solution that costs sqrt(N) number of drops, in the worst case.

Note that the number of physical floors that a man has to climb are O(N + sqrt(N)) = O(N) in the worst case ;-(

2. The above solution was requesting 10+9 drops.

Here it discusses a solution with 14 drops worst case

http://www.ocf.berkeley.edu/~wwu/riddles/eggs.ps

3. Another way to derive the optimal number of drops is dynamic programming

1. v=0
2. assuming v[i] is computed for all i , 0 <= i < k
v[k] = min ( max(j-1 , v[k-j]) ) + 1

v[k] is the optimal solution and is built starting from 0 floor, which request 0 drops.

Suppose you know the optimal solution for each floor under k. Then the optimal solution for k-th floor is given by the index j such that we have a minimum value between j-1 drops, used to reach k-th floor and the optimal solution in v[k-j], plus 1 for the current drop

4. The sequence goes like:
14,27,39,50,60,69,77,84,90,95,99,100

So if the crystal breaks after the first drop, you have max of 13 more (1 to 13) for a total of 14 drops -- you already took 1 drop
If the first crystal breaks on the 2nd drop, you have max of 12 more (15 to 26) for a total of 14 drops -- you already took 2 drops

The total of drops is 14.

5. In other words you would like to have equal number of tests at each drop

1st time you have N tests left. total N
2nd time you have N-1 tests left. total N
3rd time you have N-2 tests left. total N
...

N+ (N-1) + (N-2) + (N-3) + .. +

Sum_i (N - i) = N - Sum_i i = [ N^2 - (N)(N-1)/2 ] = (2N^2 - N^2 + N )/2 = (N^2 + N )/ 2 = N(N+1)/2

We need N(N+1)/2 > 100 i.e. N^2 + N > 200