I think a lot of people have the same problem as me. Why have we chosen length>=breadth and not all possible rotations. I came up with this logic- Suppose you have a box with the dimensions (4,2,1)- Consider two possible (l,w,h) rotations of this box- (4,2,1) and (2,4,1) - Note how height of both is same=1.(choosing either will give same height) If (4,2,1) is chosen-(2,4,1) cannot be added above it and vice versa. Therefore, the answer will contain atmost one of these two. Out of 2 possibilities-length>=breadth and breadth>=length, we can pick either and stick with it throughout.
Reason to sort by base area : A box with bigger base area can never come on top of box with smaller base area but smaller can or cannot come on top of larger base area. This thing actually converts it to LIS such that every number which is less and lies backward is considered .
A programmer's career in this world is not possible without tushar roy!- - - - - - (eq 1). .........Technology and its revolution is not possible without a programmer!- - - - - - -(eq2)- - - - - - - - -from eq1 & eq2 Technology and its revolution is not possible without tushar roy!!
After combination of boxes is found and sorted decreasing order of base area: if (arr[i].length < arr[j]. length & arr[i].width< arr[j].width]) T[i] = max{T[i], T[i]+T[j]}, for all j < i Result[i]=j, if condition is satisfied
The problem stating that boxes are unlimited doesn't make sense. If we started with 2 boxes, we should figure out if we can stack those 2 boxes with rotation instead of stacking 3 boxes.
Even after sorting wrt base area, we need to use O(n2) loop[for i=1 to n-1 andThen for j=0 to i-1]. What we need is an O(nlogn) approach in dp after sorting
Hii, I like your videos very much.... Its a pool of dynamic programming at a single place very nice.. Kindly add more stuff regarding algorithm section...And its good to know that you are from our college Motilal Nehru National Institute of Technology...ur heartiest welcome
Thanks for all the video...You are doing a great job...I am learning a lot from your videos...I would suggest you one thing that you should add links to some of the problems from SPOJ,Codechef,Hackerrank etc based on the algorithm which you have taught in the video.It would be easier for us to implement and that and we will get to know all the variations related to that algo. BTW thanks man...great job...:-)
+Tushar Roy You can crowdsource/ask viewers to upload the links. For example This is the link for this problem from geeks4geeks:www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/
Hi tushar, amazing explanation, i just had a question, what if we had only one instance of a box, how can we decide which rotation to chose such that it gives the maximum height? One solution can be finding the solution assuming multiple instances, then if the box has multiple rotations in the result, we delete the instance with minimum height. Can anyone suggest something better?
I am still struggling with this. We started with 2 boxes why are we stacking 3. I also happened to pick another set {(4,6,7), (4,2,3), (4,5,6), (10,12,32)} wherever I got it from they say the answer to the maximum height is 60 why is it not 48 ?
Wonderful video Sir. Great work! I request you to please upload videos related to interval trees, segment trees & graphs related problems. Also it wold be great if you could discuss snippets of code. Thanking you.
I'm not sure how u can use unlimited boxes when u can have only limited permutations of the dimensions of each box. Also, do we need to write the logic to perform various permutations of the dimensions of the boxes? or can we manually write the input array of boxes with all permutations of the dimensions?
isn't getting all rotations of the box same as all permutations of the dimensions? which in itself will take n! time, so how can the overall time complexity be n^2?
Why we need to sort on the basis of the base area?Can't we apply the modified LIS algorithm without sorting as we are anyway checking if l and w both are less than the that of previous box??I mean if we don't sort how answer would be effected?
If we don't sort,then we have to iterate all the boxes each time, if sorted, then we only need to iterate the boxes that are smaller than itself. So it will be more efficient.
for box, 6 orientations are possible but SIr has taken 3 only.Can someone explain?? for ex given l=3,b=2,h=5 six orientations are (2,3,5),(2,5,3),(5,3,2),(5,2,3),(3,,2,5),(3,5,2)? but sir has taken (3,2,5) (5,3,2) (5,2,3)...
It won't make a difference if you have two orientations where height is the same but only length and breadth are interchanged. You will not be able to stack one over the other, and can use only one at a time in any scenario. Hence it's redundant. Adding them won't make a difference though
explanation is too good , but I have one requested that can you give this all dynamic programming code in also c++. not me but so many students also do not know java so those student who do not know java but know c++ .plz look at my points . thanks sir.
I investigated O(nlogn) as well, but multidimensional values make O(nlogn) impossible. If we use single numbers and, for example, 7 > 1 and 3 > 1, we know that 3 is less and strictly better than 7 sequence [1,7,3,5] => 1 => 1,7 => 1,3 as 3 is strictly better than 7 => 1,3,5; But this doesn't work for (length, width) values sequence [(1,1), (7,2), (3,5), (8,3)] => (1,1) => (1,1),(7,2) => we can't choose between (1,1),(7,2) and (1,1),(3,5) as 7>3 but 2 we check both (1,1),(3,5),(8,3), doesn't work 5
At 6:15 Didn't understand why at i = 3 and j = 1,2 why the box at i cannot go on top of the boxes th jth location. As the areas are as follows [ j =1 ] 5x2x3 --> Area = 10 [ j =2 ] 4x2x1 --> Area = 8 [ i=3 ] 3x2x5 --> Area = 6 As 6 is less than both 8 and 10, this can go on top of both boxes. Is anyone else confused with the same??
According to the question asked,for a box A to be on the top of box B,its dimensions,which means its width and length both must be strictly less than that of Box B.
Dynamic programming means using memoization here. Please look at how 8:00 to 8:45. max[3] is used to compute max[5] and hence avoids extra computations.
Hi Tushar isnt 3,2,5 and 5,3,2 are different orientations of the same box ? shouldnt we should count only one of them for max height ?. I see you are saying we have unlimited supply thats why we can count ? but what if we dont have unlimited supply ?
You will get it. Think in this way- keep the box 1,2,4 on coordinate system at center . x=1, y=2,z=4. Now, rotate the box clockwise in 90 degrees keeping the z coordinate intact. thus, you get x=2,y=1,z=4.
Sorting is important as it allow us to check only with previous boxes ( with greater base area ) that if previous boxs' length and width are greater than current box. Without sorting you would have to check with every other box in the array and may then also it is tough to achieve correct solution without using more space.
Abhijeet Sachdev hello Abhijeet, i dont think we can achieve the result without sorting. for example just assume the array was in increasing order. Now can we achieve the max height ? no right , as no box can be placed above any box and maximum height in that case will be height of max box , which is 5 in above example set.
![Burst Balloon Dynamic Programming[Leetcode]](http://i.ytimg.com/vi/IFNibRVgFBo/mqdefault.jpg)
I think a lot of people have the same problem as me. Why have we chosen length>=breadth and not all possible rotations.
I came up with this logic-
Suppose you have a box with the dimensions (4,2,1)-
Consider two possible (l,w,h) rotations of this box-
(4,2,1) and (2,4,1) - Note how height of both is same=1.(choosing either will give same height)
If (4,2,1) is chosen-(2,4,1) cannot be added above it and vice versa. Therefore, the answer will contain atmost one of these two.
Out of 2 possibilities-length>=breadth and breadth>=length, we can pick either and stick with it throughout.
you are the reason i dared to learn dynamic programming so easily without anyone's help plz create more videos..........
Even after 5 yrs you're thanking him 😎
Reason to sort by base area : A box with bigger base area can never come on top of box with smaller base area but smaller can or cannot come on top of larger base area.
This thing actually converts it to LIS such that every number which is less and lies backward is considered .
Hi Tushar, thanks for your time in explaining these problem concepts, really helpful. I understood "LPS" & KMP only with your videos
A programmer's career in this world is not possible without tushar roy!- - - - - - (eq 1). .........Technology and its revolution is not possible without a programmer!- - - - - - -(eq2)- - - - - - - - -from eq1 & eq2 Technology and its revolution is not possible without tushar roy!!
i fell in love with dp and tushar helps me maintain this high profile relationship
After combination of boxes is found and sorted decreasing order of base area:
if (arr[i].length < arr[j]. length & arr[i].width< arr[j].width])
T[i] = max{T[i], T[i]+T[j]}, for all j < i
Result[i]=j, if condition is satisfied
this is the best explanation in 10 min...you are amazing
his hair reminds me of grasses in my college playground......
Simple and plain to understand. Good video quality.
Great work!
Thank you!
Thanks Tushar ,i am watching all your solutions ,keep making such videos
The problem stating that boxes are unlimited doesn't make sense. If we started with 2 boxes, we should figure out if we can stack those 2 boxes with rotation instead of stacking 3 boxes.
All your videos are awesome. Thank you for making these videos. Please keep making such videos for more problems
its very good way to provide the knowledge about the algorithms .
thank you
sir
You should also explain how you came up with this method
best way to know how is to do it
@tushar - can you please explain why length should be greater than width?
Thank you Tushar . Like always .
The one stop database for all your doubts !!👍👍👍👍
Even after sorting wrt base area, we need to use O(n2) loop[for i=1 to n-1 andThen for j=0 to i-1]. What we need is an O(nlogn) approach in dp after sorting
Thanks! It was really helpful, just like all other videos that you make.
thanks a lot.... i was stuck in a similar problem but could solve it after watching your video...seriously very helpful
Thank you for the explanation!
Hii, I like your videos very much.... Its a pool of dynamic programming at a single place very nice.. Kindly add more stuff regarding algorithm section...And its good to know that you are from our college Motilal Nehru National Institute of Technology...ur heartiest welcome
+Tushar Roy Thankq..... :)
Hi.. whats your profession? You have a great collection of videos for interesting problems from real world
He's Engineering Manager @Apple
Here is his linkedin profile -> www.linkedin.com/in/tushar-roy-4351091a/
Well very well explained... thanks Tushar....
Thanks for all the video...You are doing a great job...I am learning a lot from your videos...I would suggest you one thing that you should add links to some of the problems from SPOJ,Codechef,Hackerrank etc based on the algorithm which you have taught in the video.It would be easier for us to implement and that and we will get to know all the variations related to that algo.
BTW thanks man...great job...:-)
+Tushar Roy You can crowdsource/ask viewers to upload the links. For example This is the link for this problem from geeks4geeks:www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/
www.spoj.com/problems/BABTWR/
Usko kam dhandha bhi hai bhai...humara personal teacher nahi banke betha hai woh
1:40 I believe he's referring to the maximum sum increasing subsequence and not longest increasing subsequence.
No, he's referring to longest increasing subsequence only.
very well explained, thanks Tushar.
amazing explanation! keep going...
Hi tushar, amazing explanation, i just had a question, what if we had only one instance of a box, how can we decide which rotation to chose such that it gives the maximum height? One solution can be finding the solution assuming multiple instances, then if the box has multiple rotations in the result, we delete the instance with minimum height. Can anyone suggest something better?
Got answer ? 😂😂
Well done, Tushar
Great explaination
I am still struggling with this. We started with 2 boxes why are we stacking 3. I also happened to pick another set {(4,6,7), (4,2,3), (4,5,6), (10,12,32)} wherever I got it from they say the answer to the maximum height is 60 why is it not 48 ?
Superb! Thanks for sharing.
Wonderful video Sir. Great work!
I request you to please upload videos related to interval trees, segment trees & graphs related problems. Also it wold be great if you could discuss snippets of code.
Thanking you.
Okay sir.Thank you. Sir, will you please upload Graphs related videos?
You should also teach how to approach the problem...
I don't get the concept of using 'multiple' instances of the same box! Can anyone help me out with this?
thanks tushar
Vivekanand Khyade - Algorithm Every Day bruh you are legend too!!
i need to know why is needed to sort by area first ?
Great video sir. why don't you make video on good problem of Spoj (like QTREE6) it will be also helpful for us.Thank you
For the initial problem how is the height 7 if the max is literally 4+3 can someone please explain
I'm not sure how u can use unlimited boxes when u can have only limited permutations of the dimensions of each box. Also, do we need to write the logic to perform various permutations of the dimensions of the boxes? or can we manually write the input array of boxes with all permutations of the dimensions?
there are 2 boxes in input and 3 in output am i missing something?
you can interchange l,b,h in any format of same box and can make new box.so u can form 3 boxes from one given box and 2 boxes can form 6 boxes
Why does the length need to be greater than the width?
I guess that is the definition of length and width. In a rectangle, the longer side is always called length.
If you don't take into consideration length greater then width then you will be counting the same thing twice.
@@dhruvkumar6639 correct
감사합니다 사랑하고 축복합니다🙏😍👍🌹🎁
Thanks for great content
Sir could you tell What is the source for this problem explanation?
isn't getting all rotations of the box same as all permutations of the dimensions? which in itself will take n! time, so how can the overall time complexity be n^2?
Why we need to sort on the basis of the base area?Can't we apply the modified LIS algorithm without sorting as we are anyway checking if l and w both are less than the that of previous box??I mean if we don't sort how answer would be effected?
If we don't sort,then we have to iterate all the boxes each time, if sorted, then we only need to iterate the boxes that are smaller than itself. So it will be more efficient.
what if first box length 10, width -1 and second box length - 3, width - 3. By our code second box base is lower than first box(3*3 < 1*10)
for box, 6 orientations are possible but SIr has taken 3 only.Can someone explain??
for ex given l=3,b=2,h=5
six orientations are (2,3,5),(2,5,3),(5,3,2),(5,2,3),(3,,2,5),(3,5,2)?
but sir has taken (3,2,5) (5,3,2) (5,2,3)...
check Yukty khandelia's comment...it will help :)
It won't make a difference if you have two orientations where height is the same but only length and breadth are interchanged. You will not be able to stack one over the other, and can use only one at a time in any scenario. Hence it's redundant.
Adding them won't make a difference though
explanation is too good , but I have one requested that can you give this all dynamic programming code in also c++.
not me but so many students also do not know java so those student who do not know java but know c++ .plz look
at my points . thanks sir.
You are my hero brother..
hey Tushar I am doing it without sorting but its failing fr a few test cases can u tell me why?
If you are applying the same LIS formula without sorting then it will not work.
If you are applying any other approach then please tell.
Tushar Sir there is O(nlogn) way to solve longest increasing subsequence problem. Can we do this question in O(nlogn) complexity also?
I investigated O(nlogn) as well, but multidimensional values make O(nlogn) impossible.
If we use single numbers and, for example, 7 > 1 and 3 > 1, we know that 3 is less and strictly better than 7
sequence [1,7,3,5] => 1 => 1,7 => 1,3 as 3 is strictly better than 7 => 1,3,5;
But this doesn't work for (length, width) values
sequence [(1,1), (7,2), (3,5), (8,3)] => (1,1) => (1,1),(7,2) => we can't choose between (1,1),(7,2) and (1,1),(3,5) as 7>3 but 2 we check both (1,1),(3,5),(8,3), doesn't work 5
Is the sorting of the boxes on the basis of base area essential?
why do you have ascent ?
At 6:15 Didn't understand why at i = 3 and j = 1,2 why the box at i cannot go on top of the boxes th jth location. As the areas are as follows
[ j =1 ] 5x2x3 --> Area = 10
[ j =2 ] 4x2x1 --> Area = 8
[ i=3 ] 3x2x5 --> Area = 6
As 6 is less than both 8 and 10, this can go on top of both boxes. Is anyone else confused with the same??
According to the question asked,for a box A to be on the top of box B,its dimensions,which means its width and length both must be strictly less than that of Box B.
Condition is strictly less than (on dimensions, not area)
ie. If box2 on top of box1 => l2
Is it for optimization only?Shouldn't the solution work even without it??
Please explain why dynamic programming is needed here !!
Dynamic programming means using memoization here. Please look at how 8:00 to 8:45. max[3] is used to compute max[5] and hence avoids extra computations.
Hi Tushar isnt 3,2,5 and 5,3,2 are different orientations of the same box ? shouldnt we should count only one of them for max height ?. I see you are saying we have unlimited supply thats why we can count ? but what if we dont have unlimited supply ?
+Tushar Roy The solution counts only one box for given dimension (l*w*h) even if there is unlimited supply of boxes right?
I think the rotations of 1,2,4 shouldn't include 2,1,4 since there should only be 3 ways to rotate the box.
You will get it. Think in this way- keep the box 1,2,4 on coordinate system at center . x=1, y=2,z=4. Now, rotate the box clockwise in 90 degrees keeping the z coordinate intact. thus, you get x=2,y=1,z=4.
@@rkinamdar thank you
well explained sir!
Why do we need to sort in order of decreasing base area???
***** could u pls expand on that little more as to why it is necessary to sort??
Sorting is important as it allow us to check only with previous boxes ( with greater base area ) that if previous boxs' length and width are greater than current box. Without sorting you would have to check with every other box in the array and may then also it is tough to achieve correct solution without using more space.
Hello Tushar. . What is the need of sorting here ?
i think we dont need it .
Am I right ??
Please correct me If i am wrong?
By the way great video
Abhijeet Sachdev
hello Abhijeet, i dont think we can achieve the result without sorting. for example just assume the array was in increasing order. Now can we achieve the max height ? no right , as no box can be placed above any box and maximum height in that case will be height of max box , which is 5 in above example set.
why length can't be greater than width? is this written in constraints?
please upload videos of codes related to respective problem
Thank you sir
Plz give name of another practical example
After first sort, sort again l and w for each element if you know what i mean
legend
Boxes should have 12 combination of length ,breadth and height for 2 different boxes. How u have shown only 6 from 2 boxes???
same doubt bro
Hi Tushar, do you have actual code for this problem somewhere on your github ?
+Tushar Roy thanks
i am lost at rotating box in 3 different ways.
Thanks a lot,
thanks sir
good job :-)
Awesome :)
Ok I got it :)))))
😲
What am i watching¿
Box Stacking problem using Dynamic Programming