887. Super Egg Drop #

Problem #

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

Problem Summary #

You are given K eggs and can use a building with floors from 1 to N, for a total of N floors. Each egg functions the same way, and if an egg breaks, you can no longer drop it. You know there exists a floor F such that 0 <= F <= N: any egg dropped from a floor higher than F will break, and any egg dropped from floor F or below will not break. Each move, you can take an egg (if you have an intact one) and drop it from any floor X (where 1 <= X <= N). Your goal is to know exactly what the value of F is. Regardless of the initial value of F, what is the minimum number of moves needed to determine the value of F?

Hints:

1 <= K <= 100
1 <= N <= 10000

Solution Ideas #

Given K eggs and N floors, determine the minimum number of moves t needed to find the safe floor F.
This is a classic Microsoft interview question. The first thing that comes to mind after reading the problem is binary search. But after careful analysis, you will find that simple binary search is incorrect. Repeated binary search can indeed find the final safe floor, but it does not take the K eggs into account. The limitation on the number of eggs may prevent binary search from finding the final floor. The problem asks us to find the minimum number of moves while guaranteeing that the final safe floor can be found. Therefore, simple binary search cannot solve this problem.
If we consider this problem forward according to its meaning, the dynamic programming state transition equation is searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) ). Here X is the floor from which the egg is dropped. As X ranges over [1,N], a searchTime value can be computed; among all these N values, the minimum is the answer to this problem. This solution can AC this problem. This solution will not be expanded in detail here. The time complexity is O(k*N^2).
\[ dp(K,N) = MIN \begin{bmatrix} \, \, MAX(dp(K-1,X-1),dp(K,N-X))\, \, \end{bmatrix} ,1\leqslant x \leqslant N \\\]
Look at this problem from another angle. Define dp[k][m] as the maximum number of floors that can be checked with K eggs and M moves. Consider at which floor an egg should be dropped on some move t. A correct choice is to drop the egg at floor dp[k-1][t-1] + 1. There are two possible outcomes:
1. If the egg breaks, we first eliminate all floors above that floor (no matter how tall the building is), and for the remaining dp[k-1][t-1] floors, we can definitely solve the problem with k-1 eggs in t-1 moves. Therefore, in this case, we can solve for a building of infinite height in total. It can be seen that this is a very good situation, but it does not always occur.
2. If the egg does not break, we first eliminate the dp[k-1][t-1] floors below that floor. At this point we still have k eggs and t-1 moves, so we continue testing floors above that floor and can test dp[k][t-1] floors. Therefore, in this case, we can solve dp[k-1][t-1] + 1 + dp[k][t-1] floors in total.
As long as the first situation occurs once in all m moves, we can solve a building of infinite height. But the problem requires that we can guarantee finding the safe floor, so each egg-drop outcome should be considered in the worst case, that is, the second situation happens every time. Thus we obtain the state transition equation: dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 . This equation can be compressed to one dimension, because each new state only depends on the previous row and the column to the left. Then update each row from right to left, i.e. dp[i] += 1 + dp[i-1]. The time complexity is O(K * log N), and the space complexity is O(N).
Some people may wonder: what if the initial choice is not to drop the egg at floor dp[k-1][t-1] + 1? What happens if we choose a lower floor or a higher floor?
1. If dropping the egg from a lower floor can also guarantee finding the safe floor, then the resulting answer must not be the minimum number of moves. Because this egg drop does not fully exploit the potential of the eggs and the number of moves, there will inevitably be eggs and moves left over in the end; that is, it is not the maximum number of floors that can be detected.
2. If the egg is dropped from a higher floor, suppose it is dropped from floor dp[k-1][t-1] + 2. If the egg breaks this time, the remaining k-1 eggs and t-1 moves can only guarantee checking dp[k-1][t-1] floors, and floor dp[k-1][t-1]+ 1 is still left, so we can no longer guarantee that the safe floor can definitely be found.
By proof by contradiction, we can conclude that at every step the egg should be dropped from floor dp[k-1][t-1] + 1.
This problem can also be solved with binary search. Return to the state transition equation analyzed above: dp[k][m] = dp[k-1][m-1] + dp[k][m-1] + 1 . Use mathematical methods to analyze this recurrence. Let f(t,k) be a function of t and k. The problem asks for the minimum number of moves needed to test up to a maximum floor of N, that is, to find the minimum t such that f(t,k) ≥ N. From the state transition equation, we know: f(t,k) = f(t-1,k) + f(t-1,k-1) + 1. When k = 1, corresponding to the case of one egg, f(t,1) = t; when t = 1, corresponding to the case of one move, f(1,k) = 1. From the state transition equation we get:
\[ \begin{aligned} f(t,k) &= 1 + f(t-1,k-1) + f(t-1,k) \\ f(t,k-1) &= 1 + f(t-1,k-2) + f(t-1,k-1) \\ \end{aligned}\] Let g(t,k) = f(t,k) - f(t,k-1), and we can get:
\[ g(t,k) = g(t-1,k) + g(t-1,k-1)\] We can know that g(t,k) is Pascal’s triangle, i.e. the binomial coefficient: \[ g(t,k) = \binom{t}{k+1} = C_{t}^{k+1}\]
Using telescoping cancellation: \[ \begin{aligned} g(t,x) &= f(t,x) - f(t,x-1) \\ g(t,x-1) &= f(t,x-1) - f(t,x-2) \\ g(t,x-2) &= f(t,x-2) - f(t,x-3) \\ \begin{matrix} .\\ .\\ .\\ \end{matrix}\\ g(t,2) &= f(t,2) - f(t,1) \\ g(t,1) &= f(t,1) - f(t,0) \\ \end{aligned}\]
Thus we can get:
\[ \begin{aligned} f(t,k) &= \sum_{1}^{k}g(t,x) = \sum_{0}^{k} \binom{t}{x} \\ &= C_{t}^{0} + C_{t}^{1} + C_{t}^{2} + ... + C_{t}^{k} \\ \end{aligned}\] Where:
\[ \begin{aligned} C_{t}^{k} \cdot \frac{n-k}{k+1} &= C_{t}^{k+1} \\ C_{t}^{k} &= C_{t}^{k-1} \cdot \frac{t-k+1}{k} \\ \end{aligned}\] Therefore, for the binomial coefficient of each term, the next term can be obtained by multiplying the previous term by a fraction.
\[ \begin{aligned} C_{t}^{0} &= 1 \\ C_{t}^{1} &= C_{t}^{0} \cdot \frac{t-1+1}{1} \\ C_{t}^{2} &= C_{t}^{1} \cdot \frac{t-2+1}{2} \\ C_{t}^{3} &= C_{t}^{2} \cdot \frac{t-3+1}{3} \\ \begin{matrix} .\\ .\\ .\\ \end{matrix}\\ C_{t}^{k} &= C_{t}^{k-1} \cdot \frac{t-k+1}{k} \\ \end{aligned}\] Using binary search, continuously binary-search t until converging to the smallest t such that f(t,k) ≥ N. The time complexity is O(K * log N), and the space complexity is O(1).

Code #


package leetcode

// Solution 1: Binary search
func superEggDrop(K int, N int) int {
	low, high := 1, N
	for low < high {
		mid := low + (high-low)>>1
		if counterF(K, N, mid) >= N {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// Calculate the binomial sum, with the special first term C(t,0) = 1
func counterF(k, n, mid int) int {
	res, sum := 1, 0
	for i := 1; i <= k && sum < n; i++ {
		res *= mid - i + 1
		res /= i
		sum += res
	}
	return sum
}

// Solution 2: Dynamic programming DP
func superEggDrop1(K int, N int) int {
	dp, step := make([]int, K+1), 0
	for ; dp[K] < N; step++ {
		for i := K; i > 0; i-- {
			dp[i] = (1 + dp[i] + dp[i-1])
		}
	}
	return step
}