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.
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.
ReplyDeleteThis 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 ;-(
The above solution was requesting 10+9 drops.
ReplyDeleteHere it discusses a solution with 14 drops worst case
http://www.ocf.berkeley.edu/~wwu/riddles/eggs.ps
Another way to derive the optimal number of drops is dynamic programming
ReplyDelete1. 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
The sequence goes like:
ReplyDelete14,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.
In other words you would like to have equal number of tests at each drop
ReplyDelete1st 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