Egg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem Decomposition 

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

agreed

LOL

haha nice

I have to feed the family. Everyone eats. Otherwise, I'm starving.

nice

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

sure

hahaha, u gonna be a genius

thx

thx!

Say no words, let it be :) As a wise man once said: "Let it be, let it be, let it be, let it be There will be an answer, let it be" - Wayne Gretzky

nice

sure

sure thx

thanks

dang...that's a long search hahaha, and thanks haha...more are a comin'

@@BackToBackSWE looking forward to all of 'em!

@@krishnakrmahto97 nice

Hahahahahaha. Yes.

nice

great

sure

thanks

thanks and sure

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...

thx!

haha

ok

thank you. stay around. we got a long road ahead

@@BackToBackSWE Yes, sir I will.

@@UnseenVivekC haha ok

thx

ok

thx

thx

thanks and we only maintain code on backtobackswe.com

Here's the code link: ru-vid.com?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

sure

yeah haha, this is meant to be a resource of many

haha thanks

Yes. I will address this in a video similar to this: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Zq4upTEaQyM.html one day. Don't worry, as long as this project stays active I will cover what people want to see.

ye

sure!

Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

Thanks and got it

thx

A few more eggs would allow us to not have to drop every floor up to the breaking floor

ok

thanks

thanks and not sure, I've never heard of Jump Search

www.google.com/amp/s/www.geeksforgeeks.org/jump-search/amp/

sure

sure

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.

sure

that's what I do

thanks

thanks

lmao nice

thanks

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???

yeah it did

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.

I currently cannot due to time constraints Im sorry

Right now cannot but would if I had the time

sure

We do. To solve the subproblem you just stated: drop(3, 6) -> we need to imagine, just imagine...that we start dropping from floor 1 with 3 eggs, floor 2 with 3 eggs, floor 3 with 3 eggs, floor 4 with 3 eggs, etc. At each simulation, we want to know the 2 possibilities. What do they yield in terms of worst drops. This is how we converge to base cases. Now, to your question. Why simulate? Well...what was the original question: "You are given n eggs and specified a number of k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break." How can I know FOR SURE...for sure...the MINIMUM # of drops to find the pivotal floor? Well for the solution presented (and there are others) we do a test from each floor and find the WORST performer. This worst performance is a possible reality. We must account for it. And thus, we take this worst reality/outcome AFTER DROPPING. After dropping. If we miss out on any simulation we will miss a possible outcome that may worsen our worst case. This brings me to why we add 1. The +1 is because we want to say that "The answer where I stand is the action I take, plus the result of the worst outcome that follows." the action. A drop. +1 to the worst case drops. the result. That is the worst subproblem result that happens after our action. I could keep going but check the code in the description. Keep asking questions. I have answers...most of the time.

Here's another way to look at it: think about every call to drop(eggs, floor) as literally throwing one of your eggs down from the chosen floor. So if you computed drop(3, 6) by only considering the 6th floor (instead of testing all the floors), what you are saying is - what is the minimum number of times I need to throw eggs off of floors to find the first floor it breaks... *given that you threw your FIRST egg off the 6th floor?* As you can imagine, we might be able to reduce the number of drops in the worst case by dropping the FIRST egg off, say, the third floor - (drop(3, 3)) - if it breaks, you've eliminated the top half of floors, and if it doesn't, you've eliminated the bottom half (had we just thrown it off the highest floor each time, if the egg breaks, we would have only eliminated one floor; if the egg broke from that floor, only one more floor, and so on). Of course, we don't really know which floor to drop off first to minimize the number of drops, so we try each floor. This reflects the floor we should throw our egg off first!

@@Maholain Thank you, and thank you both. :)

@@FloShaban I still feel like I could've made it clearer...oh well. There are better solutions but I just covered the most basic solution one would realistically get with previous dp experience.

Haha! great idea

The repository is deprecated, we only maintain backtobackswe.com now.

noted, I'm not sure

"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.

The repository is deprecated - we only maintain backtobackswe.com now.

yes

nice, best of luck internet friend

@@BackToBackSWE thank you so much 🤩🤩

@@waxylayer8353 Hey bro, Are you a Tamilian?

@@lokeshsenthilkumar4522 yes

sure

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.

I see every comment and I dont have time to fix it. I restructured the repo

yes