Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/887.html
887. Super Egg Drop (Hard)
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 <= 1001 <= N <= 10000
TLE Solution
Assume we choose to throw the egg at floor i:
- If the egg breaks, we continue throwing between floors
[1, i - 1], with one less egg available - If the egg doesn’t break, we continue throwing between floors
[i + 1, N], with the same number of eggs. In this way, for whichever floors region[m, n] (1 <= m <= n <= N), we can regard floorm - 1is safe while floorn + 1is not safe. So the 2nd case above is analogous to throwing between floors[1, N - i].
Denote f(K, N) as the result. The 1st case corresponds to f(K - 1, i - 1), and the 2nd case f(K, N - i). We have to pick the max of them to ensure certainty. Denote g(K, N, i) as this max.
Thus, f(K, N) = 1 + min{ g(K, N, i) | 1 <= i <= N }. This is the equation of DP.
In the worse case we need to visit all the combinations of k and n (k in [1, K], n in [1, N]), thus time complexity is O(KN).
// OJ: https://leetcode.com/problems/super-egg-drop/
// Time: O(KN)
// Space: O(KN)
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
return std::hash<T1>{}(p.first * 10000 + p.second);
}
};
class Solution {
private:
unordered_map<pair<int, int>, int, pair_hash> m;
public:
int superEggDrop(int K, int N) {
if (!K || !N) return 0;
if (K == 1) return N;
auto p = make_pair(K, N);
if (m.find(p) != m.end()) return m[p];
int val = INT_MAX;
int prev = INT_MAX;
for (int i = (N + 1) / 2; i >= 1; --i) {
int v = max(superEggDrop(K - 1, i - 1), superEggDrop(K, N - i));
if (v > prev) break;
prev = val;
val = min(val, v);
}
return m[p] = 1 + val;
}
};
Solution 1.
Denote f(K, S) as the max number of floors that is solvable given K eggs and S steps.
After I throw an egg:
- If the egg is broken, I should continue throw the eggs within lower floors. The max number of lower floors I can handle is
f(K - 1, S - 1). - If the egg is not broken, I should continue throw the eggs within upper floors. The max number of upper floors I can handle is
f(K, S - 1).
So the max total number of floors I can handle is 1 plus the result of the above two cases, i.e. f(K, S) = 1 + f(K - 1, S - 1) + f(K, S - 1).
// OJ: https://leetcode.com/problems/super-egg-drop/
// Time: O(SK) where S is the result.
// Space: O(K)
// Ref: https://leetcode.com/problems/super-egg-drop/discuss/159508/easy-to-understand
class Solution {
public:
int superEggDrop(int K, int N) {
int step = 0;
vector<int> dp(K + 1);
for (; dp[K] < N; ++step) {
for (int k = K; k > 0; --k) {
dp[k] += 1 + dp[k - 1];
}
}
return step;
}
};
-
class Solution { public int superEggDrop(int K, int N) { int[][] dp = new int[N + 1][K + 1]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) dp[i][j] = i; } dp[1][0] = 0; for (int i = 1; i <= K; i++) dp[1][i] = 1; for (int i = 0; i <= N; i++) { dp[i][0] = 0; dp[i][1] = i; } for (int i = 2; i <= N; i++) { for (int j = 2; j <= K; j++) { int low = 1, high = i; while (low < high) { int mid = (high - low + 1) / 2 + low; int remain1 = dp[mid - 1][j - 1]; int remain2 = dp[i - mid][j]; if (remain1 > remain2) high = mid - 1; else low = mid; } dp[i][j] = Math.max(dp[low - 1][j - 1], dp[i - low][j]) + 1; } } return dp[N][K]; } } ############ class Solution { public int superEggDrop(int K, int N) { int[] res = new int[K]; Arrays.fill(res, 1); while (res[K - 1] < N) { for (int i = K - 1; i >= 1; i--) { res[i] = res[i] + res[i - 1] + 1; } res[0]++; } return res[0]; } } -
// OJ: https://leetcode.com/problems/super-egg-drop/ // Time: O(KN) // Space: O(KN) struct pair_hash { template <class T1, class T2> std::size_t operator () (const std::pair<T1,T2> &p) const { return std::hash<T1>{}(p.first * 10000 + p.second); } }; class Solution { private: unordered_map<pair<int, int>, int, pair_hash> m; public: int superEggDrop(int K, int N) { if (!K || !N) return 0; if (K == 1) return N; auto p = make_pair(K, N); if (m.find(p) != m.end()) return m[p]; int val = INT_MAX; int prev = INT_MAX; for (int i = (N + 1) / 2; i >= 1; --i) { int v = max(superEggDrop(K - 1, i - 1), superEggDrop(K, N - i)); if (v > prev) break; prev = val; val = min(val, v); } return m[p] = 1 + val; } }; -
class Solution: def superEggDrop(self, K: int, N: int) -> int: dp = [1] * (K) while dp[K - 1] < N: for i in range(K - 1, 0, -1): dp[i] = dp[i] + dp[i - 1] + 1 dp[0] = dp[0] + 1 return dp[0] ############ class Solution: def superEggDrop(self, K, N): """ :type K: int :type N: int :rtype: int """ h, m = N, K if h < 1 and m < 1: return 0 t = math.floor( math.log2( h ) ) + 1 if m >= t: return t else: g = [ 1 for i in range(m + 1) ] g[0] = 0 if g[m] >= h: return 1 elif h == 1: return h else: for i in range(2, h + 1): for j in range( m, 1, -1): g[j] = g[j - 1] + g[j] + 1 if j == m and g[j] >= h: return i g[1] = i if m == 1 and g[1] >= h: return i -
func superEggDrop(k int, n int) int { f := make([][]int, n+1) for i := range f { f[i] = make([]int, k+1) } var dfs func(i, j int) int dfs = func(i, j int) int { if i < 1 { return 0 } if j == 1 { return i } if f[i][j] != 0 { return f[i][j] } l, r := 1, i for l < r { mid := (l + r + 1) >> 1 a, b := dfs(mid-1, j-1), dfs(i-mid, j) if a <= b { l = mid } else { r = mid - 1 } } f[i][j] = max(dfs(l-1, j-1), dfs(i-l, j)) + 1 return f[i][j] } return dfs(n, k) } func max(a, b int) int { if a > b { return a } return b } -
function superEggDrop(k: number, n: number): number { const f: number[][] = new Array(n + 1) .fill(0) .map(() => new Array(k + 1).fill(0)); const dfs = (i: number, j: number): number => { if (i < 1) { return 0; } if (j === 1) { return i; } if (f[i][j]) { return f[i][j]; } let l = 1; let r = i; while (l < r) { const mid = (l + r + 1) >> 1; const a = dfs(mid - 1, j - 1); const b = dfs(i - mid, j); if (a <= b) { l = mid; } else { r = mid - 1; } } return (f[i][j] = Math.max(dfs(l - 1, j - 1), dfs(i - l, j)) + 1); }; return dfs(n, k); }