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

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

    1. v[0]=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:

    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