[E] Egg Drop Problem

Start -- the everyday picture. You have two identical phones and a very tall building, and you want the highest floor you can drop a phone from without cracking it. Drop from too high and the phone breaks -- and now you have one fewer phone to experiment with. With only two phones you can't test every floor one at a time (far too slow), but you also can't leap too greedily, or you might smash both before you've found the answer. The egg drop problem asks the careful version of this: what is the fewest number of drops that is guaranteed to work, even on the unluckiest building?

Build -- name the pieces. Let $n$ be the number of eggs (your breakable tries) and $k$ the number of floors. We want $T$, the number of drops in the worst case. The clever move is to turn the question inside out: instead of asking "which floor do I drop from first?", ask "if I'm allowed $t$ drops and have $n$ eggs, how many floors can I possibly cover?" Call that $f(t,n)$. A single drop splits the building: if the egg breaks, the floors below must be sorted out with $t-1$ drops and $n-1$ eggs; if it survives, the floors above use $t-1$ drops and all $n$ eggs. Add the one floor you just tested: $$f(t,n) = f(t-1,\,n-1) + 1 + f(t-1,\,n).$$ Worked number: with 2 eggs and 3 drops, $f(3,2)=6$. So a 6-floor building is solvable in just 3 drops -- start by dropping from floor 3, not floor 1.

Deepen -- the precise rule. The direct table $dp[i][j]$ holds the minimum worst-case drops with $i$ eggs and $j$ floors: $$dp[i][j]=\min_{1\le x\le j}\Big(1+\max\big(dp[i-1][x-1],\;dp[i][j-x]\big)\Big).$$ The inner $\max$ is the adversary picking the worse branch (break vs. survive); the outer $\min$ is you choosing the smartest floor $x$. As $x$ rises, $dp[i-1][x-1]$ grows while $dp[i][j-x]$ shrinks, so their $\max$ is unimodal -- a binary search on $x$ trims the naive $O(nk^2)$ to $O(nk\log k)$. The inside-out version has a tidy closed form, $f(t,n)=\sum_{i=1}^{n}\binom{t}{i}$, which is exactly the Pascal's-triangle identity behind the $O(n\log k)$ method (check it: $\binom{3}{1}+\binom{3}{2}=3+3=6$).

Try this in the panel above. The animation steps through a worked trace and tallies Operations and Comparisons as it goes. (1) Drag the $n$ slider from 4 to 16 and watch the step count climb -- more elements means a longer trace, the same way more floors means more drops. (2) Use the >| button to walk one step at a time and read the message bar to follow each move. (3) Press Play at 0.25x, then switch to 8x, to feel the difference between a slow, careful search and a fast one.

Step 1 -- Problem Statement. Given n eggs and a building with k floors, find the minimum number of trials (worst case) to determine the highest safe floor. An egg breaks if dropped from above the critical floor; doesn't break if dropped from at or below. Broken eggs are discarded.

Step 2 -- Minimax Recurrence. dp[i][j] = min trials with i eggs and j floors. Try floor x: egg breaks (dp[i-1][x-1] trials below) OR survives (dp[i][j-x] trials above). Worst case = max of two outcomes. Minimize over all x: dp[i][j] = min_x(1 + max(dp[i-1][x-1], dp[i][j-x])).

Step 3 -- Time O(nk^2) Space O(nk). For each (i,j) pair: linear search over x=1..j is O(j). Total: O(n * k^2). With binary search on the optimal x (since max(dp[i-1][x-1], dp[i][j-x]) is unimodal in x): O(nk log k).

Step 4 -- Inverse Formulation O(n log k). Alternative DP: f(t,n) = max floors solvable with t trials and n eggs. f(t,n) = f(t-1,n-1) + 1 + f(t-1,n). Solve for minimum t such that f(t,n) >= k. Binary search on t: O(log k) iterations, each O(n). Total: O(n log k).

Step 5 -- Base Cases. dp[1][j]=j (1 egg: must try linearly from floor 1 to j). dp[i][0]=0 (0 floors: 0 trials). dp[i][1]=1 (1 floor: 1 trial). dp[0][j]=0 is undefined (cannot solve with 0 eggs -- treat as infinity).

Step 6 -- Optimal Strategy Insight. With enough eggs, use binary search (O(log k) trials). With 1 egg, use linear search (O(k) trials). In between: hybrid. With 2 eggs and k floors, optimal is sqrt(k) trials -- try floors sqrt(k), 2sqrt(k),... and then linear within the block.