Table of Contents: Intro 0:00 - 0:24 The Problem Introduction 0:24 - 2:39 Base Case #1: 1 Egg 2:39 - 6:21 Base Case #2: 0 or 1 Floors 6:21 - 8:47 Summarizing Our Base Cases 8:47 - 10:18 The Simulation. 6 Floors, 3 Eggs 10:18 - 18:36 DP Table Walkthrough 18:36 - 22:06 Camera Dies. Finishing Explanation of The Simulation. 22:06 - 23:30 Time Complexity 23:30 - 24:12 Space Complexity 24:12 - 24:51 Wrap Up 24:51 - 25:19 Update 4/3/19: Both the Top Down & Bottom Up approaches shown in the video time out on Leetcode due to the test cases changing. The code for the problem is in the description (both bottom up and top down). Fully commented for understanding.
Bro, just, aaaaaaaaaaaaaaaaaaah, just, aaaaaaaaaaaaaaaaaa, just, I applause you, thank youuuuuuuuuuuuuuuuuuuuuuu, brooo, I just cant express my feelings, aaaaaaa its so coooooooooooooool, I understood it!
Yep, I got that but what's the recurrence relation for construction of the DP table? If we denote optimal solution by OPT(m,n) where we have m eggs and n floors then how will we write it in terms of recurrence ?
Respect for both, for the lack of good dynamic programming videos, Tushar pioneered it well imo. Ben is teaching it better with the intuition behind things, can’t deny that either :)
I have watched several videos but none of them was as good as this one. Awesome job dude. Thank U. All the videos talk about solution without explaining subproblems of dynamic programming. But you explained it really well my friend.
I can see the amount of effort you've been putting on your videos. This is what I had been looking for the last 2 years. I feel very lucky that you started making videos before I graduate.
Thank you, Lord. Finally found a video that can help. I wish I had this person teaching my algorithm class instead of my prof who looks at her notes and talks to the board.
I have been trying to understand this problem through many YoutTubers,but lemme tell you Sir, this is the best explanation I had. Keep the work up Sir.
It expresses the # of floors above where we dropped. Think on this. Example 1: 6 5 4 3 (drop here) 2 1 0 simFloor = 3 I drop at 3. No break. I go up. Do I have 6 - (3) = 3 floors above me? Or simfloor + 1 = (3) + 1 = 4 floors above me? Example 2: 6 (drop here) 5 4 3 2 1 0 simFloor = 6 I drop at 6. No break. I go up. Do I have 6 - (6) = 0 floors above me? Or simfloor + 1 = (6) + 1 = 7 floors above me? Check the code in the description. Really internalize it.
@@BackToBackSWE Yeah, I searched other videos or blogs, and I just saw 99% similar explanation to yours. I hope I can come back here later and I clearly understand this.
@@raymondyoo5461 Yeah, time helps as you see more dp problems. It is a specific way of thinking. When it does click it will be interesting. What is still unclear? If I may clarify it.
The diagram starting at 12:52 was a bit misguiding the first time I saw it, because the first 6 tree levels don't represent the same thing as the second pairs of "possibilities". In reality, the solution for just one of the subproblems (e.g. 5F, 3E in this list) needs to iterate again through simulations for all 5 floors (with both break/non-break possibilities). And then each of those smaller subproblems again needs to iterate through a bunch of floor-egg pairs. This is where the (F, E) pairs begin reappearing and the memoization (caching) of the subproblems leads to DP. One useful way of looking at it is to realize that the solution to (4F, 3F) is the same regardless of whether we are considering top 4 floors or bottom 4 floors - it doesn't matter and we will end up calculating them twice unless we cache them or use DP to get them ahead of time.
good video. I was with you until min 20:47. Why do you have drop (2,1) in addition to drop (2,2). I get the 2,2 one, but since 2 eggs,1 floor cell was a 1, why that one ?
I fudged making that part clear - I remember this vividly, I'd go in and explain but I'm rapid fire responding to 250 comments I got backed up after 2 weeks
In the case (2,1), you are on the Floor 1,just by using one egg, you would know which floor is the "won't break"(I will use F below) floor. If the egg breaks on Floor 1, then "F" floor will be Floor 0. Otherwise will be Floor 1. Only Floor 1 and Floor 0 are to be discussed in case(2,1). totalFloor = 1 is a base case, no matter how many eggs there are, the answer is always 1.
Hey great video, just a quick question, why is it that the minimum amount of egg drops for n floors is n? Wouldn't it be log(n) times since we can do sort of a binary search where we drop an egg from (n/2)th floor and if it breaks we know every egg dropped from above that floor will break and if it doesn't break we know that every egg dropped from below that floor won't break ?
We can do it logarithmically, that is the next best solution. I just presented the base solution that someone could practically come up with in an interview.
@@BackToBackSWE I see. Can I ask you just one more question? Why is it that we want the worst outcome of the drops, that is max(drop(eggs, totalFloor - currentFloor), drop(eggs - 1, currentFloor - 1)) ? This part still doesn't seem to click in my head.
@@ChainForLife Never limit questions. Always ask questions until you understand. Push the teacher as well as yourself because I don't know it all...or else we both learn nothing. So think about this....our goal is to tell the caller the SMALLEST amount of drops so that I can PROMISE that in those drops...I will find the pivotal floor. If I don't account for the worst outcome of drops...I could be lying...my promise could be broken. I have to take into account the WORST outcome and BOUND my drops to that because it promises that I find the pivotal floor in that amount of drops NO MATTER WHAT CASE happens. Does that make sense?
I know this would be a difficult one to make, but you should make a video going over techniques for identifying overlapping subproblems and optimal substructure in DP problems in general. Pulling from examples like this and longest non-decreasing subsequence (and your other vids). Basically, abstracting the problem specific examples and giving some practical tips for how to identify subproblems. Fingers crossed xD
Here's the code link: ruclips.net/user/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
Here is the code ruclips.net/user/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
I want to thank you sir for you really put in so much effort into these videos.I like the fact that you provide links to other channels too ( Like Tushar Roy etc).
At 20:59 When we want value for drop(2,2) , then, Why do we simulate sim(2,1) & sim(2,2) . we are solving for is 2 (which is 'totalFloors') floors and 2 (which is 'totalEggs') eggs. We are doing 2 simulations: sim(2, 1) (2 eggs, start from floor 1) and sim(2, 2) (2 eggs, start from floor 2). why not just sim(2,1) ? beacuse sim(2,2) is bad choice... right ?
"why not just sim(2,1)?" If we just do one of the simulations (and not all of them) we may miss a case that would've yielded a truer bound to the worst amount of eggs that would need to be dropped to ensure we find the pivotal floor. For the approach in the video (and it is not the most optimal approach), we have to run all simulations to ensure our upper limit is correct with such a guarantee.
why is it that we take the min of WORST CASE? what does WORST CASE represents here? The Maximum no of attempts that you can do at given floor without breaking the egg
at 20:50 You said that the answer is the one who do the worst but I think it minimum of "all the worst case possibilities at each floor" for a corresponding (eggs and floors)
I know you have your own plan, but I have a suggestion. Recently I started learning 'parametric search' and I find it tricky. -> what is the proper condition to be put in "while( )" ??? -> when do I put '=' on "if (K < mid)", and when do I put '=' on "if (mid < K)" ??? I don't wanna break your pace, just wanted to give you an idea. thx!
@@BackToBackSWE I heard it is highly relevant to binary search. I found some example questions, I'll add the links here. Question 1 ) hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf -- Question #2 (It starts with the sentence "Lumberjack Mirko needs to chop down M metres of wood....") Question 2 ) www.acmicpc.net/problem/3703 Question 3 ) poj.org/problem?id=3273 I think I can solve above questions applying binary search... Do you agree? Or any better method to solve them???
after watching several videos on this topic, this video proved out to be the best as always. explanations were very clear although the hiccup in the end disrupted the flow.
I don't where you are these days, when I was fresher I learnt from your videos. Now I have experience of 3 years and I am still learning from you. Am I in love with you ? 😜
Its my first time watching your video and I gotta tell it "MAN U HAVE EARNED MY RESPECT" seriously man can just emphazize on how much easy u did this to me . . Just a single problem ... ur code link redirects to a page not found ... look up for that
Thanks for the detailed explanation : // if egg breaks then egg-1 and floor -1 ==> dp[e - 1][k - 1] // else no change in egg count and remaining floors which is f-k ==> dp[e][f - k] // k means which floor we are in -- > first floor , second floor // 2 Eggs -> 3 Floors // • 2 Eggs -> lets try from 1st Floor-> 1,0 ,, 2,2 // • 2 Eggs -> lets try from 2nd Floor -> 1,1 ,, 2,1 // 2 Eggs -> lets try from 3rd Floor -> 1,2 ,, 2,0
Thanks for your perfect explanation!But for your code, I have one question. Why do you plus one here " int accountingForDroppingAtThisSubproblem = 1 + costOfWorstOutcome;" You mentioned that you were doing a test.Can you explain the test clearly?I'm feeling quite confused.
@@BackToBackSWE Can you cover more DP problems? Especially the ones in Tushar's playlist? Interview season is around the corner, please more DP, please. Thankyou for great content. Respect from India.
I’m definitely misunderstanding the question because with one egg, couldn’t you just start at floor 0 and go up until it breaks, therefore solving this in O(totalFloors) time? What is the advantage of having more than one egg? What am I missing?
If the total numbers of eggs are 1, then why are we returning total floors? It may be the case that we don't need to get to the top floor and before that we get the pivotal floor
@@BackToBackSWE so my idea is, let's say there are 100 floor. We first check at floor 50. If egg don't break we know answer is higher floor. If egg break, answer is lower floors. We repeatedly do same at the middle element of the range. So in log N time, we can derive answer.
Yes, This is the same thought going in my mind and I don't know why but no one is talking about it. Throughout the video, I'm thinking about binary search.
Your teaching are very clean and understandable ,I am glad to get a teacher like you in my journey of career.You deserve more subscribers.Good luck ,keep it up!🌈✨
Hi Benyam, I just want to say that can you make a video that explains the optimal version of this algorithm with takes O(totalEggs*totalFloors) time or any lesser time because this code showing TLE in interviewbit and leetcode as they both have large input constraints. I can't able to understand their solution and also there is no video that explains that optimized solution.
Table of Contents:
Intro 0:00 - 0:24
The Problem Introduction 0:24 - 2:39
Base Case #1: 1 Egg 2:39 - 6:21
Base Case #2: 0 or 1 Floors 6:21 - 8:47
Summarizing Our Base Cases 8:47 - 10:18
The Simulation. 6 Floors, 3 Eggs 10:18 - 18:36
DP Table Walkthrough 18:36 - 22:06
Camera Dies. Finishing Explanation of The Simulation. 22:06 - 23:30
Time Complexity 23:30 - 24:12
Space Complexity 24:12 - 24:51
Wrap Up 24:51 - 25:19
Update 4/3/19: Both the Top Down & Bottom Up approaches shown in the video time out on Leetcode due to the test cases changing.
The code for the problem is in the description (both bottom up and top down). Fully commented for understanding.
Bro, just, aaaaaaaaaaaaaaaaaaah, just, aaaaaaaaaaaaaaaaaa, just, I applause you, thank youuuuuuuuuuuuuuuuuuuuuuu, brooo, I just cant express my feelings, aaaaaaa its so coooooooooooooool, I understood it!
yeah
hahahaha nice
Yep, I got that but what's the recurrence relation for construction of the DP table?
If we denote optimal solution by OPT(m,n) where we have m eggs and n floors then how will we write it in terms of recurrence ?
@@monil1601 I don't remember
your channel is like a NETFLIX of DS & algorithms.
whenever i try to watch one of your videos i found 10 more intriguing ones
haha nice
Just wanted to say how much I appreciate these videos. You're really doing a great job of helping all of us out here and I can't thank you enough!
I have to feed the family. Everyone eats. Otherwise, I'm starving.
These are some strong ass eggs
agreed
LOL
Its nice to find a video explaining way of approach rather than repeating the dp tables from solutions.Thanks man.
sure
where is the link to your code?
One
(Back To Back SWE)
video per day keeps tushar roy away !🤣🤣🤣
hahaha CALM DOWN
Respect for both, for the lack of good dynamic programming videos, Tushar pioneered it well imo. Ben is teaching it better with the intuition behind things, can’t deny that either :)
@@abhimishra2276 what's wrong with them?
@@abhimishra2276 abdul bari is good
@@ritwik121 yes bro i was so wrong he is amazing
I have watched several videos but none of them was as good as this one. Awesome job dude. Thank U. All the videos talk about solution without explaining subproblems of dynamic programming. But you explained it really well my friend.
nice
You are the best mentor that I've ever seen in my life. You can even make a fool understand the complex concepts. (y) keep up the work bro :)
hahaha, u gonna be a genius
I Really like the way how you're explaining the problem thoroughly
thx
Replace egg with ball and this video becomes much more fun to watch
Haha! great idea
where is the link for the code it not in description.
The repository is deprecated - we only maintain backtobackswe.com now.
how easily i understood that tough problem signifies that level of teaching of ben...he has fabulous teaching skills.
thanks
I can see the amount of effort you've been putting on your videos. This is what I had been looking for the last 2 years. I feel very lucky that you started making videos before I graduate.
dang...that's a long search hahaha, and thanks haha...more are a comin'
@@BackToBackSWE looking forward to all of 'em!
@@krishnakrmahto97 nice
cant believe it took me this long to just realize that its just break and not break on every floor lol. this video helped me pull the pieces together
I couldn't believe this amazing channel only has 13K subs.
Aw, thanks. I work pretty hard on this. I hope it grows. I've put my life into this.
@@BackToBackSWE It is the greatest channel that I have found out...Thanks a lot...
Thank you, Lord. Finally found a video that can help. I wish I had this person teaching my algorithm class instead of my prof who looks at her notes and talks to the board.
Hahahahahaha. Yes.
One of the best explanations for this problem on the internet. ❤
Where is the code , please help me to find it...
where is the code in the description?
The repository is deprecated - we only maintain backtobackswe.com now.
The code never in the description 😁
I want to see you and Tushar in one frame 😂. Anyways amazing explanation as always .
ok
These videos are the best I've seen on algorithms/problem solving on RUclips. Not code walkthroughs or dry mathematical proofs just the facts!
thx!
Watched so many videos about this problem and got confused, this video made everything clear!
nice
By far the best explanation of the egg drop problem I have come across.
thx
Can't find the code in the description. Also, not available on the site. :(
I have been trying to understand this problem through many YoutTubers,but lemme tell you Sir, this is the best explanation I had. Keep the work up Sir.
thank you. stay around. we got a long road ahead
@@BackToBackSWE
Yes, sir I will.
@@UnseenVivekC haha ok
When the egg doesn’t break, why do we go for [ totalfloor - simfloor ] instead of [ simfloor + 1 ] ???
It expresses the # of floors above where we dropped. Think on this.
Example 1:
6
5
4
3 (drop here)
2
1
0
simFloor = 3
I drop at 3. No break. I go up. Do I have 6 - (3) = 3 floors above me?
Or simfloor + 1 = (3) + 1 = 4 floors above me?
Example 2:
6 (drop here)
5
4
3
2
1
0
simFloor = 6
I drop at 6. No break. I go up. Do I have 6 - (6) = 0 floors above me?
Or simfloor + 1 = (6) + 1 = 7 floors above me?
Check the code in the description. Really internalize it.
Hmm... interesting. Thank you very much for your explanation :)
@@raymondyoo5461 I think I could've done better with this, oh well. Just keep thinking on it if you still don't 100% understand it.
@@BackToBackSWE Yeah, I searched other videos or blogs, and I just saw 99% similar explanation to yours. I hope I can come back here later and I clearly understand this.
@@raymondyoo5461 Yeah, time helps as you see more dp problems. It is a specific way of thinking. When it does click it will be interesting.
What is still unclear? If I may clarify it.
Sir i cannot find the code!!!Help me out!!!!
The repository is deprecated - we only maintain backtobackswe.com now.
The diagram starting at 12:52 was a bit misguiding the first time I saw it, because the first 6 tree levels don't represent the same thing as the second pairs of "possibilities". In reality, the solution for just one of the subproblems (e.g. 5F, 3E in this list) needs to iterate again through simulations for all 5 floors (with both break/non-break possibilities). And then each of those smaller subproblems again needs to iterate through a bunch of floor-egg pairs. This is where the (F, E) pairs begin reappearing and the memoization (caching) of the subproblems leads to DP.
One useful way of looking at it is to realize that the solution to (4F, 3F) is the same regardless of whether we are considering top 4 floors or bottom 4 floors - it doesn't matter and we will end up calculating them twice unless we cache them or use DP to get them ahead of time.
Hey - I dont remember this problem enough to answer this, shot this a while back
good video. I was with you until min 20:47. Why do you have drop (2,1) in addition to drop (2,2). I get the 2,2 one, but since 2 eggs,1 floor cell was a 1, why that one ?
I fudged making that part clear - I remember this vividly, I'd go in and explain but I'm rapid fire responding to 250 comments I got backed up after 2 weeks
In the case (2,1), you are on the Floor 1,just by using one egg, you would know which floor is the "won't break"(I will use F below) floor. If the egg breaks on Floor 1, then "F" floor will be Floor 0. Otherwise will be Floor 1. Only Floor 1 and Floor 0 are to be discussed in case(2,1). totalFloor = 1 is a base case, no matter how many eggs there are, the answer is always 1.
Hey great video, just a quick question, why is it that the minimum amount of egg drops for n floors is n? Wouldn't it be log(n) times since we can do sort of a binary search where we drop an egg from (n/2)th floor and if it breaks we know every egg dropped from above that floor will break and if it doesn't break we know that every egg dropped from below that floor won't break ?
We can do it logarithmically, that is the next best solution. I just presented the base solution that someone could practically come up with in an interview.
@@BackToBackSWE I see. Can I ask you just one more question? Why is it that we want the worst outcome of the drops, that is max(drop(eggs, totalFloor - currentFloor), drop(eggs - 1, currentFloor - 1)) ? This part still doesn't seem to click in my head.
@@ChainForLife Never limit questions. Always ask questions until you understand. Push the teacher as well as yourself because I don't know it all...or else we both learn nothing.
So think about this....our goal is to tell the caller the SMALLEST amount of drops so that I can PROMISE that in those drops...I will find the pivotal floor. If I don't account for the worst outcome of drops...I could be lying...my promise could be broken.
I have to take into account the WORST outcome and BOUND my drops to that because it promises that I find the pivotal floor in that amount of drops NO MATTER WHAT CASE happens. Does that make sense?
@@BackToBackSWE Yes sir, that last sentence pretty much made it crystal clear for me.
@@ChainForLife Ok, cool, haha don't "sir" me...I'm just a dude...a normal guy.
where i can find the code ?
Sir, you're one of the best algorithm teachers I've ever seen! Your explanations are really fascinating!
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
I know this would be a difficult one to make, but you should make a video going over techniques for identifying overlapping subproblems and optimal substructure in DP problems in general. Pulling from examples like this and longest non-decreasing subsequence (and your other vids). Basically, abstracting the problem specific examples and giving some practical tips for how to identify subproblems.
Fingers crossed xD
ok
There is no link for the code in the description !!!!!!!!
Where are the codes dude, we really need them.
Ps: you’re a life saver, keep going ✌🏻💙
thanks and we only maintain code on backtobackswe.com
Here's the code link:
ruclips.net/user/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
Where is the code? Am I mistaking the place where the description is supposed to be?
I am almost in tears for how good this is explained
Dude where is the code? I couldn't find.
The repository is deprecated - we only maintain backtobackswe.com now.
Here is the code
ruclips.net/user/redirect?q=https%3A%2F%2Fgithub.com%2Fbephrem1%2Fbacktobackswe%2Ftree%2Fmaster%2FDynamic%2520Programming%252C%2520Recursion%252C%2520%2526%2520Backtracking%2FEggDrop&redir_token=QUFFLUhqbnQ3T2tXamxoVTh5c205TlJCYjZCYmZsOWNjZ3xBQ3Jtc0trODRCQlRicjVIbXh0dXk5VEhrel9QQkZUNXFRamMzSVdablYxLUE5aVk3RGxrRUFOMjNTQkRWSk1qeFlrcVk1cEVIUU51b3E5X3dtSXh2M0FGcmxPY0ZiUFU5eTU4YjhuMDZYckl3YXNDeTQ2UFJIQQ%3D%3D&event=comments&stzid=UgzKhQ0U7vTf35sZifd4AaABAg
Thank you so much for your effort. You can't even imagine how much these help.
nice
not sure if you will see this but the link for code is broken here.
I see every comment and I dont have time to fix it. I restructured the repo
i can't find the code for the problem!!! please help...
The repository is deprecated, we only maintain backtobackswe.com now.
These have to be some hard ass eggs man.. Thanks for the lucid explanation bro..
ye
code is gone -- can you please re upload it? :)
ok
Here's the code link:
github.com/bephrem1/backtobackswe/tree/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/EggDrop
Keep up the good work and keep making our life easier!!
ok
I want to thank you sir for you really put in so much effort into these videos.I like the fact that you provide links to other channels too ( Like Tushar Roy etc).
yeah haha, this is meant to be a resource of many
At 20:59
When we want value for drop(2,2) ,
then,
Why do we simulate sim(2,1) & sim(2,2) .
we are solving for is 2 (which is 'totalFloors') floors and 2 (which is 'totalEggs') eggs. We are doing 2 simulations: sim(2, 1) (2 eggs, start from floor 1) and sim(2, 2) (2 eggs, start from floor 2).
why not just sim(2,1) ?
beacuse sim(2,2) is bad choice... right ?
"why not just sim(2,1)?" If we just do one of the simulations (and not all of them) we may miss a case that would've yielded a truer bound to the worst amount of eggs that would need to be dropped to ensure we find the pivotal floor. For the approach in the video (and it is not the most optimal approach), we have to run all simulations to ensure our upper limit is correct with such a guarantee.
best explanation to this problem so far
thanks
Too good bro! Dead camera was a bummer but great explanation!
haha
why is it that we take the min of WORST CASE? what does WORST CASE represents here? The Maximum no of attempts that you can do at given floor without breaking the egg
The worst-case can happen so we must account for it. We want to know the best we can do given the worst case.
at 20:50 You said that the answer is the one who do the worst but I think it minimum of "all the worst case possibilities at each floor" for a corresponding (eggs and floors)
yes
I know you have your own plan, but I have a suggestion.
Recently I started learning 'parametric search' and I find it tricky.
-> what is the proper condition to be put in "while( )" ???
-> when do I put '=' on "if (K < mid)", and when do I put '=' on "if (mid < K)" ???
I don't wanna break your pace, just wanted to give you an idea. thx!
Not familiar with parametric search. Is it related to binary search?
@@BackToBackSWE I heard it is highly relevant to binary search. I found some example questions, I'll add the links here.
Question 1 ) hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf -- Question #2 (It starts with the sentence "Lumberjack Mirko needs to chop down M metres of wood....")
Question 2 ) www.acmicpc.net/problem/3703
Question 3 ) poj.org/problem?id=3273
I think I can solve above questions applying binary search... Do you agree? Or any better method to solve them???
Where is the code
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE then how to see the code
you have mentioned three to four times in the video that code is available in the description.It will more helpful if you provide code.
after watching several videos on this topic, this video proved out to be the best as always. explanations were very clear although the hiccup in the end disrupted the flow.
thx
Awesome explanation !! Thank you so so much!
sure
I am unable to find the implemented code in description .Where should i be looking?
I don't where you are these days, when I was fresher I learnt from your videos.
Now I have experience of 3 years and I am still learning from you.
Am I in love with you ?
😜
I never am able to find code in description.
The code link does not work anymore
ik
where is the code for this problem
The repsoitory is deprecated - we only maintain backtobackswe.com now.
Great clarification of the problem!! This was my 3rd vdeo for the egg problem and now i am satisfied!
great
Thanks for the explanation. But the github link is not working.
ik
Its my first time watching your video and I gotta tell it "MAN U HAVE EARNED MY RESPECT" seriously man can just emphazize on how much easy u did this to me . .
Just a single problem ... ur code link redirects to a page not found ... look up for that
Thanks and got it
Thanks for the detailed explanation :
// if egg breaks then egg-1 and floor -1 ==> dp[e - 1][k - 1]
// else no change in egg count and remaining floors which is f-k ==> dp[e][f - k]
// k means which floor we are in -- > first floor , second floor
// 2 Eggs -> 3 Floors
// • 2 Eggs -> lets try from 1st Floor-> 1,0 ,, 2,2
// • 2 Eggs -> lets try from 2nd Floor -> 1,1 ,, 2,1
// 2 Eggs -> lets try from 3rd Floor -> 1,2 ,, 2,0
My GUY!!! You are brilliant! I will invest my tuition to a service you provide. Take my money!
What would the complete dynamic programming table look like in the example?
it is filled out in the video?
Back To Back SWE your camera dies at 22:06 before you’re able to finish filling out the last 6 cells
It's very clear that you have put in a lot of effort to come up detailed explanation. Thank you keep up the good work.
thanks
One of the best explanation.
Thank you, sir!
thanks and sure
Thanks for your perfect explanation!But for your code, I have one question. Why do you plus one here " int accountingForDroppingAtThisSubproblem = 1 + costOfWorstOutcome;" You mentioned that you were doing a test.Can you explain the test clearly?I'm feeling quite confused.
The +1 denotes dropping an egg then solving the remaining subproblems passing the resulting state change to the next call
@@BackToBackSWE Thx!
@@jomosis9234 sure
Hey, can you make a video for O(K*log N) approach?
Right now cannot but would if I had the time
Where is the code(solution)? I can't find it in the description box
link is gone - repo is no longer maintained but it is on my github
@@BackToBackSWE Can you cover more DP problems? Especially the ones in Tushar's playlist? Interview season is around the corner, please more DP, please. Thankyou for great content. Respect from India.
I can't find link to code. :((
The repository is deprecated - we only maintain backtobackswe.com now.
I can't find the code in the description.
The repository is deprecated - we only maintain backtobackswe.com now.
Where is the link to the code?
You always say that the code is in the description but I never see it? Did this get moved to your subscription service? Either way thanks!
Hey, we had a public repository and we have deprecated it and only maintain backtobackswe.com from now on
unsubscribed
@@BackToBackSWE okay gotcha i found it and thanks again!
Watched it while on the treadmill, nicely explained, just wish your cam didn't die
lmao nice
Why can't one use binary search to find a floor that doesn't break, then check above and see if it does?
You can do that
sir where is the link for code
The repository is deprecated - we only maintain backtobackswe.com now.
I’m definitely misunderstanding the question because with one egg, couldn’t you just start at floor 0 and go up until it breaks, therefore solving this in O(totalFloors) time? What is the advantage of having more than one egg? What am I missing?
I dont remember this video nor the question
Anyone else have an answer?
Great explanation!!
Egg Drops, from floor’s and not breaking its unsettling though!! Going to think of it as Coconut Drop 😐
If the total numbers of eggs are 1, then why are we returning total floors? It may be the case that we don't need to get to the top floor and before that we get the pivotal floor
I dont remember this problem to be honest
@@BackToBackSWE lmao
Since this is a monotonic function, cannot we solve it using binary search?
im not sure
@@BackToBackSWE so my idea is, let's say there are 100 floor. We first check at floor 50. If egg don't break we know answer is higher floor. If egg break, answer is lower floors.
We repeatedly do same at the middle element of the range. So in log N time, we can derive answer.
So we need ceil of LogN eggs at max.
Yes, This is the same thought going in my mind and I don't know why but no one is talking about it. Throughout the video, I'm thinking about binary search.
in which order do i have to watch your dynamic programming series ?
not sure, any
@@BackToBackSWE it won't affect my understanding ?
@@alieltoney what
Best explanation ever!
Hi,
I am not able to understand how for 2 eggs and 10 floors the answer is 4.. Shouldn't it be 5?
im not sure - this video is very old hard to remember anything
Just input the value in the LC question to confirm your guess.
@@AnshumanKumar007 I know the answer is 4. But why it is 4?
I got my first job ( 18 lpa ) all coz of your videos.... Thanks a lot dude .. keep helping people ❤️
nice, best of luck internet friend
@@BackToBackSWE thank you so much 🤩🤩
@@waxylayer8353 Hey bro, Are you a Tamilian?
@@lokeshsenthilkumar4522 yes
Thank you very much
sure
Why drop(2, 1) when we already know the answer to that???
Your teaching are very clean and understandable ,I am glad to get a teacher like you in my journey of career.You deserve more subscribers.Good luck ,keep it up!🌈✨
thx!
Commendable explanation !
I have seen tons of your videos, and I never found the code in the description. Could you please tell me where is it exactly?
The repository is deprecated, we only maintain backtobackswe.com now.
You are really gr8, thanks sir! I hope you do Great things in life! Respect
sure thx
Hey, I cannot find the code in the description, can someone help?
Check it out on backtobackswe.com/
What will the final recurrence look like considering m eggs and n floors ?
not sure, I forgot everything I said in this video.
@@BackToBackSWE alright, I'll figure it out. Even the coin change video doesn't have the recurrence nevertheless you explained both of them very well.
@@monil1601 thx
code is not present :(
ik
very good and detailed explanation , thank you !
sure
finally I am beginning to understand the problem!!
Hi Benyam, I just want to say that can you make a video that explains the optimal version of this algorithm with takes O(totalEggs*totalFloors) time or any lesser time because this code showing TLE in interviewbit and leetcode as they both have large input constraints. I can't able to understand their solution and also there is no video that explains that optimized solution.
I currently cannot due to time constraints Im sorry
Where is the code ?
The repository is deprecated - we only maintain backtobackswe.com now.