Given some number of floors and some number of eggs, what is the minimum number of attempts it will take to find out from which floor egg will break. github.com/mis... github.com/mis...
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.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.
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.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
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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.
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.
@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...
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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!
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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).
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.
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.
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 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
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?
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??
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 ?
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?
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
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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
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
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.
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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
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?
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 !!
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.
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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.
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 :)
~ @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?
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-bLSbJV1hFbk.html
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
Example: 10 eggs 6 floors. You wouldn't even need 10 eggs, had you dropped the eggs on each floor one after the other and had they broke each time, 6 eggs would have been enough. But even 6 is overkill, Tushar calculated for us that for 6 floors actually 3 eggs is enough. So in case of 10 eggs 6 floors, you can say: yeah, it's actually the same as 9 eggs and 6 floors. For the 9 egg 6 floors case you still go backwards to 8 eggs 6 floors using the same reasoning and so forth until the point, where the number of eggs are the same, 6 eggs and 6 floors. In this case you can now use the mini-max recursive approach, which is: complete search each possible drop location choosing the worst possible outcome at each drop location, as if you had an adversary always deciding about the breaking/non-breaking of your egg by giving you the worst possible outcome at each drop, but then you have the power to choose among all these drop locations and obviously you will choose the one with the minimum number of drop count, hence the mini-max.
you are dropping egg from k-th floor .. that is 1 attempt ... if it breaks then try k-1 floors below it with 1 less egg , if it doens't break try upper j-k floors with all eggs .. so worst case will be max of these two cases
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.
