CareerCup

My solution is 11.

Suppose the solution is dropping the egg from k. If the egg breaks, then we use the second egg to do binary search. Then the maximum number of drops would become 1 + k/2. Knowing this number, we follow the same idea as dropping two eggs.

How about dropping it from 10, 20, 30....so on...If it breaks at 20 and not at 10...Do a linear between 10 and 20...
Minimizes the eggs broken to 2.

11

I can think of 14 tries can you please tell me more about solution of 11 tries.

matrix[i][j] = min(max(matrix[i-1][m], matrix[i][N-m])), 1 < m < N

Assume N = 100, mine requires 9 times. The first egg is tried on 36, 64, 85, 100. Depending on the result of first egg drop, the second egg is tried on (8, 15, 21, 26, 30, 33, 35), (43, 49, 54, 58, 61, 63), (70, 75, 79, 82, 84), (90, 94, 97, 99). The third egg is just for linear search. The worse case is 9 drops, though it might be possible to reduce to 8 times.

The idea follows from the two-egg dropping problem and this problem is reduced to solving the following inequality: sum_{k=1}^{n} k + sum_{k=1}^{n-1} k + ... + sum_{k=1}^{1} k > 100.

log2(N) tries are needed normally... but what is the trick of 3 eggs, i did not understand that...

Friend ur solution is not clearer to me could u plz throw more light on it.

Following are the key thoughts of mine:
1. this problem is a search algorithm. For a stable algorithm, my beliefe is the equal spliting is the best approach
2. Say D is the difference between each search step. For 3 eggs scenaio, the worst cases are:
a. O(Step1) = N/D (ceiling)
b. O(Step2) = O(Step1) = N/D (ceiling)
c. O(Step3) = D/O(Step1) = D/(N/D) = D^2/N (ceiling)
then: O(Step1)+O(Step2)+O(Step3) = 2*N/D + D^2/N
Calculate the D which make the total cost function min.

Detail:
First derivative = 0
=> -2*N/D^2 + 2*D/N = 0
=> D^3 = N^2

In case N = 100 => D = 22