PROBLEM LINK:
Author: Shivani Srivastava
Tester: Shivani Srivastava
Editorialist: Kaushambi Gujral
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Stacks
PROBLEM:
You are given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i) and depth d(i).
You want to create a stack of boxes which is as tall as possible(Jumbo Mystery Box), but you can only stack a box on top of another box
if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.
QUICK EXPLANATION:
The problem is similar to the Longest Increasing Sub-sequence. There are only 3 possibilities to place any box. We can
arrange this in the desired fashion and choose the boxes with the decreasing area.
EXPLANATION:
So we have n boxes. The first thing we will concentrate upon is the box rotations. Remember that each rotation will create more
possibilities for making the stack, and that we have unlimited number of boxes.
We are saying that we can rotate a box and it seems a little complicated, but if you look closely, then we have only 3 unique possibilities
which will have different base areas.
That can be obtained when you place the box in the following manners:
-
{ h, w, d }
-
{ w, h, d }
-
{ d, h, w }
For each given box, we will generate all the possibilities. Since we have unlimited boxes, we will use all the boxes to make the stack
of the maximum height.(Now this problem has been reduced to a variation of Longest Increasing Sub-sequence.)
To create the stack of maximum height, we need to place the box with max base area at the bottom, on top of that the box with 2nd max base
area and so on.
AUTHOR’S AND TESTER’S SOLUTION:
The solution can be found here.