The problem statement is not very clearly stated. Why min, why max - not really explained. Simulation is really hard to keep up with at first. But after watching it repeatedly many times and after visiting other sites about this problem, things finally became clear! But, this video then really helped.
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Tushar, There is a flaw in your video in the sense that the explanation you gave is for dynamic programming using a nxk matrix while your formula is based on recursion. In the explanation you had used the following formula - f[n][k] = min(1 + max( f[n-1][j-1] , f[n][j-x] ) where x ranges from 1 to j ) Here n = number of eggs and k = number of floors
MISTAKE (always droop from the middle if you have more than one egg): There is a fundamental logical MISTAKE and while it does not affect the result, it does simplify the solution when realized. See: If you have more than one egg, you can start drooping the first egg from any of the N floors. So, you evaluate the cost of dropping from each floor and stay with the floor that yields the minimum cost (min). But when you think better, that is completely unnecessary: you don't need to evaluate all the floors, because the middle floor will always yield the minimum drooping cost. Always! Now, depending on N (even or odd), the middle floor might or might not have an equal number of floors above and below. When it does not, you stay with the worst case scenery: solve the problem with more floors (max). Applying this logic, you eliminate the min operation that evaluates all possible floors (go always with the middle) and the solution to the problem cuts down as follows: def eggs(N,e): if e==1: return N if N==1: return 1 mid=math.ceil(N/2) if (N-mid)>(mid-1): return eggs(N-mid,e)+1 else: return eggs(mid-1,e-1)+1
Explanation of the middle selection: Suppose you have 100 floors and just 2 eggs. You droop the first egg from 99: in the best case it does not break and with the remaining egg you scan the only floor left, the floor 100 (the one above you). So the best case is 2 droops! But in the worst case (it did not break), you have to scan 98 floors below you one by one with the only remaining egg. This makes 98 droops for the worst case. Thus, you are risking a lot (too much difference between the best and the worst case, and you don’t know what the case will be). So: 99: 2 (best)-98(worst) 98: 3(best)-97(worst) 97: 4(best)-96(worst) . . 4: 4(best)-96(worst) 3: 3(best)-97(worst) 2: 2 (best)-98(worst) Look! When you go downwards the risk reduces (the difference between best and worst case tends to zero) but, it happens like that also when you go upwards. So, in the middle point the risk will be near zero (depending of N being even or odd). But, in any case, the middle point (as Buddha said) will always be the most neutral or best option to droop any time you have more than one egg (the one with minimum cost).
It seems that you are proposing a binary search. An example for why binary search might not be ideal: Let N = 100 We have 2 eggs Use first egg to perform Binary Search 50 (egg crack) Now we need to iterate over 1 to 50 with the second egg. Total number of iterations: 1 + 50 = 51 Alternative algorithm: Use first egg and jump 10 steps each time, 0, 10, 20, 30, ..., 90, 100 (10 iterations) In worst case scenario, crack at 100. Second egg, iterate from 91 to 100. Total number of iterations: 10 + 10 = 20. Here we see that a binary search is not ideal. The idea here is basically that a binary search only works well if it truly can narrow the search space. Each iteration shortens the bounds from 0 to n, 0 to n/2, 0 to n/4, etc. However, if it fails early on, which this problem could cause it to, then it leaves us with half the remaining space to search.
my friend you are wrong. Just Check for 2 eggs and 9 floor. if you drop from mid answer will be 5. but if you try from every floor you will find answer is 4.
That's EXACTLY what I was thinking. 100 floors so from from 50 -> then halve again (either 25 or 75)-> then halve again(say 88)->halve again (say 94) ->then halve again(say 98)-> 99->then 100. So worst case is 7. This was until I realized ONE FUNDAMENTAL DIFFERENCE. These are floors.You do not run till 50th floor, then run till 75 then come down then go up.No! You proceed from either top to bottom or bottom to the top...one traversal. A main condition easily missed mentioning in many tutorials.
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
For logarithmic complexity, A divide and conquer approach for this problem can be tried(similar to binary serach). example: drop an egg from the middle floor i.e number_of_floors/2 if it breaks, work with 1 to mid - 1 floor else, work with mid to number
***** Yes Agreed. If there is a constraint on number Eggs, the minimum number of eggs needed to solve the problem in binary serach approach is log(n) to base 2.
actually this is first time i've seen someone posted a detailed solution for this problem instead just a stupid math equation without any explanation. good work. i m officially a fan
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
The first video which explains the problem with a logical explanation instead of moving to equation.Thanks a lot, Tushar for making video and putting ur effort on it.
@Tushar Solution will always come when you drop first egg from floor/2 floor and when consider the cases. For example for floor =6, we do 6/2 = 3, we drop from floor 3, there are two possibilities 1)Egg breaks in which case we have 2 floors and 1 egg 2)Egg doesn't break, in which case we have 3 floors and 2 eggs so, solution will be 1+max(2,2) = 3 So, time complexity will reduce to n*k, rather than n*(k^2) Please tell if I am missing something. P.S., I think in case of even no. of floors, we will need to consider both n/2 and ((n/2)+1), but not the rest.
Hey Ankit, good thought experiment. But, look how your simplification behaves at floor = 9 dp[2][9] = 1 + max(dp[1][4], dp[2][4]) dp[1][4] = 4 dp[2][4] = min(1 + max(dp[1][1], dp[2][2]), 1 + max(dp[1][2], dp[2][1])) dp[1][1] = 1 dp[1][2] = 2 dp[2][1] = 1 dp[2][2] = min(1 + max(dp[1][1], dp[1][0]), 1 + max(dp[1][0], dp[1][1])) = min(1 + max(1,0), 1 + max(0,1)) = 2 dp[2][4] = min(1 + max(1,2), 1 + max(2,1)) = 3 dp[2][9] = 1 + max(4,3) = 5 (which is not the answer) correct answer is 4 You can also think like this let floor be any odd number > 8 (2n + 1) dp[2][2n + 1] = 1 + max(dp[1][n], dp[2][n]) = 1 + max(n, something); = at least (1 + n); you can observe similar behavior in the program for floor = 35 output = 18, floor = 16 output = 8 // code #include using namespace std; int main(){ int n, k; int dp[1001][1001]; cin >> n >> k; for(int i=1;i
What if no of eggs =2 and no of foors=10. According to you we will check for n=5 and n=6 but this gives answer 1+max(4,3)=5, but the answer is 4 if we consider the first egg drop from 4th floor. ie 1+max(3,3);
Binary search wouldn't be feasible for this problem. If you have less than log(N) eggs, narrowing down to the threshold floor is not always possible. Eg: 100 floors and 2 eggs. Throw the egg on floor 50. Breaks. Throw the egg on floor 25. Breaks. Uh oh...
Assuming , the egg will break on some floor . The base case: 1 egg for 2 floors is 1 Example : Drop it on 1 if it breaks we know that the solution is 1 if it doesn't break , we know the only other floor it could break on is 2 . The base case 1 egg on 1 floor = 0 . We don't need a drop to know that the only floor is the one it breaks on.
@@karthiks846 The program does not guarantee that the egg will break if dropped from a particular floor. It just helps to find the optimal floor from where the egg should be dropped in such a way that even if it does not break in total number of floors, the answer is optimal.
Sir, we can even find out using binary search, so if n is number of eggs, and f is number of floors, time complexity will be O(nlog(f)) and space complexity will be O(1).
The formula (at ~11.08) in case of when number of eggs < number of floors is incorrect probably. You are adding 1 to the minimum each and every time(in your formula), hence the value at T[i][j] does not retain the minimum (since it gets updated each and everytime, not considering whether the current value is < the previous value) (possibly) if(i>j) T[i][j]=T[i-1][j] else { prev=val val=1+max(T[i-1][k-1],T[i][j-k]) if(val
Thank you very much!I've seen similar code in other places before, but I don't really understand what the third level loop does, which is K variables, and the formula for recursion, but I got it through your video!Thanks again!
for n floors and 2 eggs , the min number of attempts to find where eggs breaks is n formula being n(n+1)/2 = numberofsteps. For ex : take 10 floors and 2 eggs - start with 4 th floor - if it breaks then one could find with the other egg starting with 1st floor in (1 + 3 (1st floor ,then 2nd ...then 4th floor) ) , if it doesn't break try 7th floor , if it breaks then try with second egg from 5th - 7th floor - so number of attempts is 1+1+2( 4th,7th,5th,6th) ... similar logic for 9th floor and 10th floor ... Logic is lets say egg is dropped at different floors x,y,z,,, abs( (0-x) + (x+1-y) + (y+1-z)...) should be equal to n . and they should be consecutive. so n*(n+1)/2 = numberofsteps
Great work! I saw your link from geekforgeek, and I think your explanation is much clearer! Also I have a question that can most of the dynamic programming problems be solved by matrix like you made? cause I have watched some of your videos and you solved them all by making a matrix. And again, awesome work and TX a lot!!
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
You should explain/write out the algorithm first before you start going through the matrix, it's not clear why your taking the min of the max's for example.
I actually have the same question. The minimum makes sense, since you want the minimum number of attempts. What's the max for? If you do know the answer, you mind explaining it? Thanks!
I will try to add my 2 cents for why Maximum is needed here. On each floor, you are trying to see what's the worst possible scenario you can encounter when you drop eggs. For Ex: on floor 2, 2 eggs, your worst possible number is 2 (since if you start with 1st floor, and egg doesn't break, you will have to do 1 more attempt at 2nd floor). Now, out of all these possibilities , you are trying to get the minimum number. Hope this helps !!
Please try to do the real time solving on the left side of the meta content you have already written. It would make it easier for the learners to get the full view. Thanks
This was a good explanation of this problem. I really liked it and learned a lot. Thank you. Some problem statements ask for the maximum number of floors which can be covered at each step. That is the inverse of the minim attempts I guess. So in case of six floors/2eggs, the maximum floors at each step is 2. Right?
If you want to see the superb acting of Don with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Thanks for great video. I have one doubt, at 2:31 when you are explaining 2 floor and 2 scenario. When you are talking about to drop egg from 1st floor then you mentioned "1 egg and 1 floor is remaining" but actually it should be "2 eggs and 1 floor". You are pointing out matrix(1,1) block while explaining but it should be matrix(2,1). Please make me correct if I misunderstood. Thanks again for such a great video
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
When calculating the case for 2 floors 2 eggs I am kinda confused because he considered remaining egg as one when egg did not break from the first floor, and in the case of 3 floors and 2 eggs when dropping from 2 nd floor he considered 2 eggs and 1 floor.
Hi Tushar ..... if there are 2 floors and 1 egg then max attempt will be 1. How ? As follows - I drop the egg from 1st floor - if it breaks I know its the 1st floor, if it doesn't break then without dropping from 2nd floor , I know that it WILL break from 2nd floor I dont have to actually frop from 2nd floor. I am assuming that the egg WILL break from one of the floor
Thanks a lotttt for making me understand DP....Can you please tell why we are taking MAX(attempts when egg broken, not broken) and MIN from all the cases of throwing from each floor (k from 1 to j). Thanks in advance
Great video! Correct me if I'm wrong, we are trying to find the min. number of attempts of all the worst case scenarios (egg breaking at floor k), hence we take min. of all maximums?
I found another variant of the problem where an egg can survive one fall from it's breaking height but not a second one.....Any idea on how to find the answer in that case??
I'm having a hard time interpreting the 1 +max and then taking the min of the results. Can this be said in the following way: Add 1 to the worst case possible from each floor. Then take the minimum possible from the worst case and this is the min number of attempts.
i understood how table got filled but still couldn't understand how the formula was derived for i>j case why is that iteration of x required from 1 to j
Hi, Thanks a lot for your videos. I am a great fan of yours. I have a question regarding the tabulation in all the dynamic programming problems you solve. In each problem , the qay you start is different . I know that each problem has a different requirement but still, for some problems you start with 0th row and 0th column and for some with 1. For e.g in the rod cutting problem, you directly say, in the first row, we take the rod length from 0 to 5, but in the egg dropping puzzle, you start from one to number of floors and you started with an empty set in Travelling salesman. Also, how do you determine which is the row and which is column ? Thanks Girish
Thank you so much for your videos! Why can't we solve this problem here using binary search? it seems like you're searching for a number between a set of sorted number, floors (1, 2, 3, 4, 5, 6). The result is Ceil(log2(6)) = 3.
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Wow, This is awesome. Thanks man. Can you please tell the time complexity since we would be having 3 for loops? I am assuming its O(floors*Egg*floors) worst case
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
any underlying assumption too ? In case of 2 eggs and 2 floors if you drop the first egg from second floor, then shouldn't the noofattempts be 1 + max(0,1) too for if ? and if not, is the intent on finding the minimum floor for this too ?
If you want to see the complete code with concept all the way to superb acting of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
What would be the time and space complexity of this algorithm. usually your github links have the complexity specified. Thanks for the the explanatory videos :)
Please pause the above video at 3:07 minutes and it should be observed that when three floors are taken into consideration and the egg is dropped from the first floor if the egg does not break then 2 eggs and 2 floors(3rd floor) must be left out but in the video it is told that one egg and two floor will be left out. Can anyone please explain this?
Can you please tell me how you decide if egg breaks or not. everyone is talking about egg breaks but the question is what condition we should put while coding to know if the egg breaks or not?
at 2:32 there is a problem. You said if it is not broken then I have 1 floor and 1 still egg it is true but you show the wrong index of array you show us 1,1 but you show us 2,1. It does not change the answer but it is a mistake.Thanks
Even I was initially assuming that way, but if you see closely even for the remaining floors ie j-k part, the attempt to drop from the current floor ie K is not counted, so in both case ie when the egg is broken or not broken, the 1 that is added to the result is drop attempt from current floor.
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
~ @2:28 In the scenario where you have two floors and two eggs to work with If you drop the egg from the first floor and it does't break, then you have two floors and one egg to work with instead of one floor and one egg. Correct?
I think this problem can be solved much faster if you use this strategy: given n eggs, perform a binary search with the first n-1 eggs. Then when you reach the last egg, count up the number of spaces remaining in the largest interval that can be left from your binary search. The answer is the number of steps in the binary search + the size of the largest interval. I don’t see why we need dynamic programming for this problem since we already know an optimal strategy for dropping the eggs.
![Burst Balloon Dynamic Programming[Leetcode]](http://i.ytimg.com/vi/IFNibRVgFBo/mqdefault.jpg)
The problem statement is not very clearly stated. Why min, why max - not really explained. Simulation is really hard to keep up with at first. But after watching it repeatedly many times and after visiting other sites about this problem, things finally became clear! But, this video then really helped.
TH-cam Subtitles : "My name is Too Sharp (Tushar)" 😅
at 0:02
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
It used to be Too Short, looks like TH-cam is improving :)
@@irynasherepot9882 yeah was just about to say that... lol
Now it says "Tar" @@irynasherepot9882
I think at 2:30 if the egg doesnt break we still have 1 floor and 2eggs to work with, not just 1 egg
Tushar,
There is a flaw in your video in the sense that the explanation you gave is for dynamic programming using a nxk matrix while your formula is based on recursion.
In the explanation you had used the following formula -
f[n][k] = min(1 + max( f[n-1][j-1] , f[n][j-x] ) where x ranges from 1 to j )
Here n = number of eggs and k = number of floors
you are a great teacher you have helped me a lot, i am very much thankful to you.
Good one! Truly you went through the problem in detail to explain it. No other video on youtube did that.
MISTAKE (always droop from the middle if you have more than one egg):
There is a fundamental logical MISTAKE and while it does not affect the result, it does simplify the solution when realized. See:
If you have more than one egg, you can start drooping the first egg from any of the N floors. So, you evaluate the cost of dropping from each floor and stay with the floor that yields the minimum cost (min).
But when you think better, that is completely unnecessary: you don't need to evaluate all the floors, because the middle floor will always yield the minimum drooping cost. Always!
Now, depending on N (even or odd), the middle floor might or might not have an equal number of floors above and below. When it does not, you stay with the worst case scenery: solve the problem with more floors (max).
Applying this logic, you eliminate the min operation that evaluates all possible floors (go always with the middle) and the solution to the problem cuts down as follows:
def eggs(N,e):
if e==1:
return N
if N==1:
return 1
mid=math.ceil(N/2)
if (N-mid)>(mid-1):
return eggs(N-mid,e)+1
else:
return eggs(mid-1,e-1)+1
Explanation of the middle selection: Suppose you have 100 floors and just 2 eggs. You droop the first egg from 99: in the best case it does not break and with the remaining egg you scan the only floor left, the floor 100 (the one above you). So the best case is 2 droops! But in the worst case (it did not break), you have to scan 98 floors below you one by one with the only remaining egg. This makes 98 droops for the worst case. Thus, you are risking a lot (too much difference between the best and the worst case, and you don’t know what the case will be). So:
99: 2 (best)-98(worst)
98: 3(best)-97(worst)
97: 4(best)-96(worst)
.
.
4: 4(best)-96(worst)
3: 3(best)-97(worst)
2: 2 (best)-98(worst)
Look! When you go downwards the risk reduces (the difference between best and worst case tends to zero) but, it happens like that also when you go upwards. So, in the middle point the risk will be near zero (depending of N being even or odd). But, in any case, the middle point (as Buddha said) will always be the most neutral or best option to droop any time you have more than one egg (the one with minimum cost).
It seems that you are proposing a binary search.
An example for why binary search might not be ideal:
Let N = 100
We have 2 eggs
Use first egg to perform Binary Search
50 (egg crack)
Now we need to iterate over 1 to 50 with the second egg.
Total number of iterations: 1 + 50 = 51
Alternative algorithm:
Use first egg and jump 10 steps each time, 0, 10, 20, 30, ..., 90, 100 (10 iterations)
In worst case scenario, crack at 100.
Second egg, iterate from 91 to 100.
Total number of iterations: 10 + 10 = 20.
Here we see that a binary search is not ideal.
The idea here is basically that a binary search only works well if it truly can narrow the search space. Each iteration shortens the bounds from 0 to n, 0 to n/2, 0 to n/4, etc.
However, if it fails early on, which this problem could cause it to, then it leaves us with half the remaining space to search.
my friend you are wrong. Just Check for 2 eggs and 9 floor. if you drop from mid answer will be 5. but if you try from every floor you will find answer is 4.
That's EXACTLY what I was thinking. 100 floors so from from 50 -> then halve again (either 25 or 75)-> then halve again(say 88)->halve again (say 94) ->then halve again(say 98)-> 99->then 100. So worst case is 7. This was until I realized ONE FUNDAMENTAL DIFFERENCE. These are floors.You do not run till 50th floor, then run till 75 then come down then go up.No! You proceed from either top to bottom or bottom to the top...one traversal. A main condition easily missed mentioning in many tutorials.
One thing I would recommend would be make the board visible to us viewers so we can make the connection to where you are grabbing the min value from.
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
I am lucky to have your channel on youtube Tushar. Else I might have gone crazy.
You explained the solution so well, it truly helped me understand the solution.
man...he is explaining this topic with such a grace and ease ...feels like he has invented this question.Perfect work!!!
Tushar Roy 5years later still the best solution to the problem. YOU ROCK!!!
For logarithmic complexity, A divide and conquer approach for this problem can be tried(similar to binary serach).
example:
drop an egg from the middle floor i.e number_of_floors/2
if it breaks, work with 1 to mid - 1 floor
else, work with mid to number
***** Yes Agreed. If there is a constraint on number Eggs, the minimum number of eggs needed to solve the problem in binary serach approach is log(n) to base 2.
Thanks for taking the time to break it down and explain it step by step!
actually this is first time i've seen someone posted a detailed solution for this problem instead just a stupid math equation without any explanation. good work. i m officially a fan
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
The first video which explains the problem with a logical explanation instead of moving to equation.Thanks a lot, Tushar for making video and putting ur effort on it.
@Tushar
Solution will always come when you drop first egg from floor/2 floor and when consider the cases.
For example for floor =6, we do 6/2 = 3, we drop from floor 3, there are two possibilities
1)Egg breaks in which case we have 2 floors and 1 egg
2)Egg doesn't break, in which case we have 3 floors and 2 eggs
so, solution will be 1+max(2,2) = 3
So, time complexity will reduce to n*k, rather than n*(k^2)
Please tell if I am missing something.
P.S., I think in case of even no. of floors, we will need to consider both n/2 and ((n/2)+1), but not the rest.
ooh, very nice!
Also,I think you do not need to consider both for the even floors because of symmetry, as they will have the same # of attempts
Hey Ankit, good thought experiment.
But, look how your simplification behaves at floor = 9
dp[2][9] = 1 + max(dp[1][4], dp[2][4])
dp[1][4] = 4
dp[2][4] = min(1 + max(dp[1][1], dp[2][2]), 1 + max(dp[1][2], dp[2][1]))
dp[1][1] = 1
dp[1][2] = 2
dp[2][1] = 1
dp[2][2] = min(1 + max(dp[1][1], dp[1][0]), 1 + max(dp[1][0], dp[1][1]))
= min(1 + max(1,0), 1 + max(0,1))
= 2
dp[2][4] = min(1 + max(1,2), 1 + max(2,1))
= 3
dp[2][9] = 1 + max(4,3)
= 5 (which is not the answer)
correct answer is 4
You can also think like this let floor be any odd number > 8 (2n + 1)
dp[2][2n + 1] = 1 + max(dp[1][n], dp[2][n])
= 1 + max(n, something);
= at least (1 + n);
you can observe similar behavior in the program for floor = 35 output = 18, floor = 16 output = 8
// code
#include
using namespace std;
int main(){
int n, k;
int dp[1001][1001];
cin >> n >> k;
for(int i=1;i
What if no of eggs =2 and no of foors=10.
According to you we will check for n=5 and n=6 but this gives answer 1+max(4,3)=5, but the answer is 4 if we consider the first egg drop from 4th floor. ie 1+max(3,3);
Binary search wouldn't be feasible for this problem. If you have less than log(N) eggs, narrowing down to the threshold floor is not always possible.
Eg: 100 floors and 2 eggs.
Throw the egg on floor 50. Breaks.
Throw the egg on floor 25. Breaks.
Uh oh...
Its always eazy for me to understand the logic with the help of your videos. Great job Tushar ...
Assuming , the egg will break on some floor .
The base case: 1 egg for 2 floors is 1
Example : Drop it on 1
if it breaks we know that the solution is 1
if it doesn't break , we know the only other floor it could break on is 2 .
The base case 1 egg on 1 floor = 0 . We don't need a drop to know that the only floor is the one it breaks on.
+Mark Schumacher I think this is the way to do when you dont know if a critical floor exists
Are we assuming that egg will break definitely on one of the floors?
@@karthiks846 The program does not guarantee that the egg will break if dropped from a particular floor. It just helps to find the optimal floor from where the egg should be dropped in such a way that even if it does not break in total number of floors, the answer is optimal.
Nice explanation and very much greatful to you, best video of this question
Sir, we can even find out using binary search, so if n is number of eggs, and f is number of floors, time complexity will be O(nlog(f)) and space complexity will be O(1).
It will only work if you have log(f) eggs
The formula (at ~11.08) in case of when number of eggs < number of floors is incorrect probably.
You are adding 1 to the minimum each and every time(in your formula), hence the value at T[i][j] does not retain the minimum (since it gets updated each and everytime, not considering whether the current value is < the previous value)
(possibly)
if(i>j)
T[i][j]=T[i-1][j]
else
{
prev=val
val=1+max(T[i-1][k-1],T[i][j-k])
if(val
***** yaa, got it now. :)
Anyways, you are doing a great job, keep it going :D
there is a mistake at 3:20, it should be "if it doesn't break, we have 2 floors and '2' eggs to work with"
Thank you very much!I've seen similar code in other places before, but I don't really understand what the third level loop does, which is K variables, and the formula for recursion, but I got it through your video!Thanks again!
for n floors and 2 eggs , the min number of attempts to find where eggs breaks is n formula being n(n+1)/2 = numberofsteps. For ex : take 10 floors and 2 eggs - start with 4 th floor - if it breaks then one could find with the other egg starting with 1st floor in (1 + 3 (1st floor ,then 2nd ...then 4th floor) ) , if it doesn't break try 7th floor , if it breaks then try with second egg from 5th - 7th floor - so number of attempts is 1+1+2( 4th,7th,5th,6th) ... similar logic for 9th floor and 10th floor ...
Logic is lets say egg is dropped at different floors x,y,z,,, abs( (0-x) + (x+1-y) + (y+1-z)...) should be equal to n . and they should be consecutive. so n*(n+1)/2 = numberofsteps
***** I agree Tushar..
Thanks for sharing these videos . I find these really helpful...
If we had 4 floors and 2 eggs and dropped first egg from second floor, wouldn't we need just 2 eggs ?
Great work! I saw your link from geekforgeek, and I think your explanation is much clearer!
Also I have a question that can most of the dynamic programming problems be solved by matrix like you made? cause I have watched some of your videos and you solved them all by making a matrix. And again, awesome work and TX a lot!!
If you want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
nice work tushar..
your short lectures are really helpful to me...
Sadly , the rationale is not clear.Not sure what you are trying to find as the number of attempts.
You should explain/write out the algorithm first before you start going through the matrix, it's not clear why your taking the min of the max's for example.
I actually have the same question. The minimum makes sense, since you want the minimum number of attempts. What's the max for? If you do know the answer, you mind explaining it? Thanks!
the max is for something like "worst case" scenario
its like taking min(worst case) ....
but yeah , doesnt mean i completely agree with this way of solving ... its not intuitive
I will try to add my 2 cents for why Maximum is needed here.
On each floor, you are trying to see what's the worst possible scenario you can encounter when you drop eggs. For Ex: on floor 2, 2 eggs, your worst possible number is 2 (since if you start with 1st floor, and egg doesn't break, you will have to do 1 more attempt at 2nd floor).
Now, out of all these possibilities , you are trying to get the minimum number.
Hope this helps !!
Please try to do the real time solving on the left side of the meta content you have already written. It would make it easier for the learners to get the full view. Thanks
This was a good explanation of this problem. I really liked it and learned a lot. Thank you. Some problem statements ask for the maximum number of floors which can be covered at each step. That is the inverse of the minim attempts I guess. So in case of six floors/2eggs, the maximum floors at each step is 2. Right?
If you want to see the superb acting of Don with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Thanks for great video. I have one doubt, at 2:31 when you are explaining 2 floor and 2 scenario.
When you are talking about to drop egg from 1st floor then you mentioned "1 egg and 1 floor is remaining" but actually it should be "2 eggs and 1 floor". You are pointing out matrix(1,1) block while explaining but it should be matrix(2,1).
Please make me correct if I misunderstood.
Thanks again for such a great video
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
When calculating the case for 2 floors 2 eggs I am kinda confused because he considered remaining egg as one when egg did not break from the first floor, and in the case of 3 floors and 2 eggs when dropping from 2 nd floor he considered 2 eggs and 1 floor.
guy looks like a mad scientist
8:35 it will be 1+ max(2,3) and hence the final answer for 2 eggs and 6 floors will be minimum 4 attempts not 3
Hi Tushar ..... if there are 2 floors and 1 egg then max attempt will be 1. How ? As follows - I drop the egg from 1st floor - if it breaks I know its the 1st floor, if it doesn't break then without dropping from 2nd floor , I know that it WILL break from 2nd floor I dont have to actually frop from 2nd floor. I am assuming that the egg WILL break from one of the floor
Instructions unclear, I broke all the eggs.
Tushar Roy is God of algorithms... He explains in a way no one else does
I just wanna know what kind of this sturdy egg is
Thanks a lotttt for making me understand DP....Can you please tell why we are taking MAX(attempts when egg broken, not broken) and MIN from all the cases of throwing from each floor (k from 1 to j). Thanks in advance
but why are taking max
Great explanation
Nice Explanation for egg breaking
this man is too good.
Great video! Correct me if I'm wrong, we are trying to find the min. number of attempts of all the worst case scenarios (egg breaking at floor k), hence we take min. of all maximums?
I found another variant of the problem where an egg can survive one fall from it's breaking height but not a second one.....Any idea on how to find the answer in that case??
Thank you very much!
I'm having a hard time interpreting the 1 +max and then taking the min of the results. Can this be said in the following way:
Add 1 to the worst case possible from each floor. Then take the minimum possible from the worst case and this is the min number of attempts.
+Tushar Roy Great videos man, I am obsessed watching them. I wish you existed 6 years ago.
East or west Tushar is the best!! Thank you
Did you check the auto generated sub-titles? It had me in splits!
i understood how table got filled but still couldn't understand how the formula was derived for i>j case why is that iteration of x required from 1 to j
great work but your solution doesn't pass all test cases in leetcode just fyi
Simply awesome!!
Hi Tushar,
Very well explained. Can you please explain space and time complexity for this problem ?
Refer geeks for time and space complexity
Hi,
Thanks a lot for your videos. I am a great fan of yours. I have a question regarding the tabulation in all the dynamic programming problems you solve. In each problem , the qay you start is different . I know that each problem has a different requirement but still, for some problems you start with 0th row and 0th column and for some with 1. For e.g in the rod cutting problem, you directly say, in the first row, we take the rod length from 0 to 5, but in the egg dropping puzzle, you start from one to number of floors and you started with an empty set in Travelling salesman. Also, how do you determine which is the row and which is column ?
Thanks
Girish
Thank you so much for your videos! Why can't we solve this problem here using binary search? it seems like you're searching for a number between a set of sorted number, floors (1, 2, 3, 4, 5, 6). The result is Ceil(log2(6)) = 3.
Thanks very much. Great video, great explanation.
explanation is good. but, you are covering the white board while explaining the concepts which is making difficult to follow immediately.
Very good videos !
great video.
thanks Tushar !!!
you need zero eggs to test this. eggs will break at any floor.
lol :D
The real question is, does the egg stay the same after surviving repeated drops? Hard to say....
Lolz
A bit confusing in the 1st watch but grab it in 2nd attempt.
Why isn't the eggs re-usable after each drop
They are reusable. That is how we are solving 6 floors with only 2 eggs with multiple attempts.
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
really well done man!
Shouldln't the formula for the scenario where the egg doesn't break be
T[i][N-j] instead of T[i][j-k] where N is number of floors
+Rao Venu Actually he's right, k is the iterator between 1 and j, where j is the current floor you're solving for, T(i, j).
Wow, This is awesome. Thanks man. Can you please tell the time complexity since we would be having 3 for loops? I am assuming its O(floors*Egg*floors) worst case
arun vyas yeah that's right . Since eggs are constant so time complexity would be O(n*n)ie n squared
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Well explained.
thank u so much..very well explained..gr8 job
You should try collaborating with Animesh Nayan ( mycodeschool).
He is dead
any underlying assumption too ?
In case of 2 eggs and 2 floors if you drop the first egg from second floor, then
shouldn't the noofattempts be 1 + max(0,1) too for if ? and if not, is the intent on finding the minimum floor for this too ?
can you tell how to print the intermediate floors that have been used to find the minimum trials efficiently by modifying the DP table ?
If you want to see the complete code with concept all the way to superb acting of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
What would be the time and space complexity of this algorithm. usually your github links have the complexity specified. Thanks for the the explanatory videos :)
Time complexity would be O(n*e*n), where 'n' is the total number of floors and 'e' is the total number of eggs
Thank you very much. Great video :)
Please pause the above video at 3:07 minutes and it should be observed that when three floors are taken into consideration and the egg is dropped from the first floor if the egg does not break then 2 eggs and 2 floors(3rd floor) must be left out
but in the video it is told that one egg and two floor will be left out.
Can anyone please explain this?
Just after that he has corrected it(At 3:37 min). Listen carefully!!
Can you please tell me how you decide if egg breaks or not. everyone is talking about egg breaks but the question is what condition we should put while coding to know if the egg breaks or not?
at 2:32 there is a problem. You said if it is not broken then I have 1 floor and 1 still egg it is true but you show the wrong index of array you show us 1,1 but you show us 2,1. It does not change the answer but it is a mistake.Thanks
suppose we are considering 6th floor if egg doesn't break then how come the value is 0 ?
Shouldn't the recurrence at else part be:
else
T[i][j] = min( 1 + max ( T[i-1][k-1], T[i][j-k] ))
?
Even I was initially assuming that way, but if you see closely even for the remaining floors ie j-k part, the attempt to drop from the current floor ie K is not counted, so in both case ie when the egg is broken or not broken, the 1 that is added to the result is drop attempt from current floor.
great job. i am grateful to u tushar
Brother it will be helpfull ,if you upload tutorial about bitmask dp
@2:33 i think the 1 comes from 1 floor and 2 eggs not from 1 floor and 1 egg, even though the value is same (1).
If any body want to see the superb acting with concept all the way to code of this egg drop problem, I ensure you, you'll love this video: th-cam.com/video/bLSbJV1hFbk/w-d-xo.html
Great video... thanks a lot Tushar
Wow :) Nice, & clear explanation, power of DP (Re-using the previously computed results) is well explained here :)
I am from NIT jalandhar and You>????
seems like answer has been in mind and trying to explain but in different way. why max,... what is the rational behind it is not clearly explained.
The real starting values for this problem:
DROPS[0][1] = 0
DROPS[0][2] = 1
DROPS[0][3] = 1
DROPS[0][4] = 2
...
DROPS[1][1] = 0
DROPS[1][2] = 1
DROPS[1][3] = 1
DROPS[1][4] = 2
...
According to your profile's pic. You're red!
What does it mean? =)
I recognized you from CF. You're RED! (if you are real mean you aren't fake) I was Specialist few days ago. After the recent contest now I'm green :(
Oh, understood.
That is my profile there: codeforces.com/profile/Pixar
Oh sorry. This is me codeforces.com/profile/Alvex
whats the runtime of this? i saw other videos where they start at like n(n-1)..
Guy he is wrong;
I tried it today it broke on first floor itself so only one egg is needed😐
Can anybody share a link to this problem on leetcode?
In 2.35 Why are you saying 1 egg and 1 floor...you should say 1 floor and 2 egg right ? somebody Explain me
~ @2:28 In the scenario where you have two floors and two eggs to work with
If you drop the egg from the first floor and it does't break, then you have two floors and one egg to work with instead of one floor and one egg. Correct?
Deborshi Saha Sorry but after specified operation, we will be left with 1 floor(2 - 1) and 2 eggs(2 - 0 as egg did not break).
Yeah, but that wouldn't matter as numEggs> numFloors
why we are adding 1 in max()
Thanks Tushar! Much Help :)
I am getting a TLE with this logic :(
Checkout -> leetcode.com/problems/super-egg-drop/discuss/158974/C%2B%2BJavaPython-2D-and-1D-DP-O(KlogN)
I think this problem can be solved much faster if you use this strategy: given n eggs, perform a binary search with the first n-1 eggs. Then when you reach the last egg, count up the number of spaces remaining in the largest interval that can be left from your binary search.
The answer is the number of steps in the binary search + the size of the largest interval.
I don’t see why we need dynamic programming for this problem since we already know an optimal strategy for dropping the eggs.
How to solve it with O(n*k) TC?
If you drop an egg how are you having two eggs to work with?
sir if egg dosent break it is still usable
Bro I have a doubt.. that Whether all the eggs to be dropped from the same floor?
awesome explanation, thanks a lot
Why are we adding 1+ with max..
1 is for the attempt of dropping
you give the solution but don't provide clear explanation.
Helpful Video.