LeetCode 887 - Super Egg Drop
Dynamic Programming | Set 11 (Egg Dropping Puzzle) | GeeksforGeeks
Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.
The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.
1) Optimal Substructure:When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.
Dynamic Programming | Set 11 (Egg Dropping Puzzle) | GeeksforGeeks
Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.
The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.
1) Optimal Substructure:When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.
1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
Auxiliary Space: O(nk)
https://xizha677.gitbooks.io/codenotes/content/drop-eggs-ii.html
https://discuss.leetcode.com/topic/58366/drop-eggs-dp-solution
int[][] F = new int[c + 1][d + 1];
for (int[] element : F) {
Arrays.fill(element, -1);
}
return getHeightHelper(F, c, d);
}
static int getHeightHelper(int[][] F, int c, int d) {
if (c == 0 || d == 0) {
return 0;
} else if (c == 1) {
return d;
} else {
if (F[c][d] == -1) {
F[c][d] = getHeightHelper(F, c, d - 1)
+ getHeightHelper(F, c - 1, d - 1) + 1;
}
return F[c][d];
}
}
http://www.datagenetics.com/blog/july22012/index.html
Many Eggs
the number of drops required for this solution is log2 n, where n is the number of floors of the building.
Back to two eggs
Minimization of Maximum Regret
if the solution lays somewhere in a floor low down, then we have extra-headroom when we need to step by singles, but, as we get higher up the building, we have already used drop chances to get there, so there we have less drops left when we have to switch to going floor-by-floor.
If it doesn't break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to one-by-one floors), so the next floor we should try is floor n + (n-1)
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
n (n+1) / 2 >= 100
This is a quadratic equation, with the positive root of 13.651 == 14.
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trails needed to find the critical
floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
x in {1, 2, ..., k}}
Time Complexity: O(nk^2)Auxiliary Space: O(nk)
int eggDrop(int n, int k){ /* A 2D table where entery eggFloor[i][j] will represent minimum number of trials needed for i eggs and j floors. */ int eggFloor[n+1][k+1]; int res; int i, j, x; // We need one trial for one floor and0 trials for 0 floors for (i = 1; i <= n; i++) { eggFloor[i][1] = 1; eggFloor[i][0] = 0; } // We always need j trials for one egg and j floors. for (j = 1; j <= k; j++) eggFloor[1][j] = j; // Fill rest of the entries in table using optimal substructure // property for (i = 2; i <= n; i++) { for (j = 2; j <= k; j++) { eggFloor[i][j] = INT_MAX; for (x = 1; x <= j; x++) { res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]); if (res < eggFloor[i][j]) eggFloor[i][j] = res; } } } // eggFloor[n][k] holds the result return eggFloor[n][k];}https://xizha677.gitbooks.io/codenotes/content/drop-eggs-ii.html
There is a building of n floors. If an egg drops from the k th floor or above, it will break. If it's dropped from any floor below, it will not break.
You're given m eggs, Find k while minimize the number of drops for the worst case. Return the number of drops in the worst case.
Example:
Given m = 2, n = 100 return 14
Given m = 2, n = 36 return 8
public int dropEggs2(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
//state: f[x][y] represents the minimum number of trials that needed for verifying the worst case of y floors with x eggs
int[][] f = new int[m + 1][n + 1];
//initialization:
//when there is only one egg
for (int i = 1; i <= n; i++) {
f[1][i] = i;
}
//when there is only one floor
for (int i = 1; i <= m; i++) {
f[i][1] = 1;
}
//function:
/* drop one egg (out of m) on any arbitrary floor k (out of n), there will be two cases:
* (1). egg - break, number of trials is reduced to subproblem(m - 1, k - 1)
* (2). egg - !break, number of trails is reduced to subproblem(m, n -k)
* The worst case amoung these two will be the total trials required after floor x
*/
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
f[i][j] = Integer.MAX_VALUE;
for (int k = 1; k < j; k++) {
int worstCase = Math.max(f[i - 1][k - 1], f[i][j - k]) + 1; // add one for current drop
f[i][j] = Math.min(f[i][j], worstCase); //find the minimum amoung these decisions
}
}
}
//answer:
return f[m][n];
}
There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case.
Let us check the DP solution , Thanks to @zhouyangnk
- sub-problem def.dp[n][m] : the minimal max drops we need if we have n-floor building and m eggs.
- base case def.dp[0][m] = 0 (m >= 1)dp[n][1] = n (n >= 1)dp[n][m] = min { max { dp[i-1][m-1], dp[n-i][m] } } + 1 ( n >= i >= 1 )
When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.
1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.
Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.
k ==> Number of floors
n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trials needed to find the critical
floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)):
x in {1, 2, ..., k}}
int eggDrop(int n, int k){ // If there are no floors, then no trials needed. OR if there is // one floor, one trial needed. if (k == 1 || k == 0) return k; // We need k trials for one egg and k floors if (n == 1) return k; int min = INT_MAX, x, res; // Consider all droppings from 1st floor to kth floor and // return the minimum of these values plus 1. for (x = 1; x <= k; x++) { res = max(eggDrop(n-1, x-1), eggDrop(n, k-x)); if (res < min) min = res; } return min + 1;}EPI Java Solution: Determine the critical height HeightDetermination.java
Max number of floor that you can tets in worst-case.
static int getHeight(int c, int d) {int[][] F = new int[c + 1][d + 1];
for (int[] element : F) {
Arrays.fill(element, -1);
}
return getHeightHelper(F, c, d);
}
static int getHeightHelper(int[][] F, int c, int d) {
if (c == 0 || d == 0) {
return 0;
} else if (c == 1) {
return d;
} else {
if (F[c][d] == -1) {
F[c][d] = getHeightHelper(F, c, d - 1)
+ getHeightHelper(F, c - 1, d - 1) + 1;
}
return F[c][d];
}
}
http://www.datagenetics.com/blog/july22012/index.html
Many Eggs
the number of drops required for this solution is log2 n, where n is the number of floors of the building.
Back to two eggs
Minimization of Maximum Regret
if the solution lays somewhere in a floor low down, then we have extra-headroom when we need to step by singles, but, as we get higher up the building, we have already used drop chances to get there, so there we have less drops left when we have to switch to going floor-by-floor.
If it doesn't break, rather than jumping up another n floors, instead we should step up just (n-1) floors (because we have one less drop available if we have to switch to one-by-one floors), so the next floor we should try is floor n + (n-1)
n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100
n (n+1) / 2 >= 100
This is a quadratic equation, with the positive root of 13.651 == 14.
http://www.writeulearn.com/category/puzzles/
http://tech-queries.blogspot.com/2014/04/question-you-are-given-2-identical-eggs.html
Related: http://massivealgorithms.blogspot.com/2014/07/2-egg-puzzle-programming-interviews.html
Read full article from Dynamic Programming | Set 11 (Egg Dropping Puzzle) | GeeksforGeekshttp://tech-queries.blogspot.com/2014/04/question-you-are-given-2-identical-eggs.html
Related: http://massivealgorithms.blogspot.com/2014/07/2-egg-puzzle-programming-interviews.html
