Box Stacking
You are given a set of ‘n’ types of rectangular 3-D boxes. The height, width, and length of each type of box are given by arrays, ‘height’, ‘width’, and ‘length’ respectively, each consisting of ‘n’ positive integers. The height, width, length of the i^th type box is given by ‘height[i]’, ‘width[i]’ and ‘length[i]’ respectively.

You need to create a stack of boxes that is as tall as possible using the given set of boxes.

Below are a few allowances:

You can only stack a box on top of another box if the dimensions of the 2-D base of the lower box ( both length and width ) are strictly larger than those of the 2-D base of the higher box. You can rotate a box so that any side functions as its base. It is also allowed to use multiple instances of the same type of box. This means, a single type of box when rotated, will generate multiple boxes with different dimensions, which may also be included in stack building.

Return the height of the highest possible stack so formed.

Note:

The height, Width, Length of the type of box will interchange after rotation. No two boxes will have all three dimensions the same. Don’t print anything, just return the height of the highest possible stack that can be formed.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘4*T’ lines represent the ‘T’ test cases. The first line of each test case contains an integer ‘n’, representing the number of types of boxes. The second line of the test case contains ‘n’ space-separated integers representing elements of the array ‘height’. The third line of the test case contains ‘n’ space-separated integers representing elements of the array ‘width’. The fourth line of the test case contains ‘n’ space-separated integers representing elements of the array ‘length’.

Output format :

Return a single integer representing the height of the highest possible stack that can be formed.

Constraints:

1

Question

Box Stacking

You are given a set of ‘n’ types of rectangular 3-D boxes. The height, width, and length of each type of box are given by arrays, ‘height’, ‘width’, and ‘length’ respectively, each consisting of ‘n’ positive integers. The height, width, length of the i^th type box is given by ‘height[i]’, ‘width[i]’ and ‘length[i]’ respectively.

You need to create a stack of boxes that is as tall as possible using the given set of boxes.

Below are a few allowances:

You can only stack a box on top of another box if the dimensions of the 2-D base of the lower box ( both length and width ) are strictly larger than those of the 2-D base of the higher box. 

You can rotate a box so that any side functions as its base. It is also allowed to use multiple instances of the same type of box. This means, a single type of box when rotated, will generate multiple boxes with different dimensions, which may also be included in stack building.

Return the height of the highest possible stack so formed.

alt text

Note:

The height, Width, Length of the type of box will interchange after rotation.

No two boxes will have all three dimensions the same.

Don’t print anything, just return the height of the highest possible stack that can be formed.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘4*T’ lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘n’, representing the number of types of boxes.

The second line of the test case contains ‘n’ space-separated integers representing elements of the array ‘height’.

The third line of the test case contains ‘n’ space-separated integers representing elements of the array ‘width’.

The fourth line of the test case contains ‘n’ space-separated integers representing elements of the array ‘length’.

Output format :

Return a single integer representing the height of the highest possible stack that can be formed.

Constraints:

1 <= T <= 50
1 <= n <= 10^2
1 <= height[i] <= 10^2
1 <= width[i] <= 10^2
1 <= length[i] <= 10^2

Time limit: 1 second

Accepted Answer

Brute Force

This is a recursive approach.
Make an integer matrix ‘boxes’ of dimension (3*n, 3), we will store all three rotations of each type of boxes in it.
Generate all 3 rotations for all ‘n’ types of boxes, for simplicity we will consider ‘width’ always smaller than or equal to ‘length’. Store them in matrix ‘boxes’ such that boxes[i][0], boxes[i][1], boxes[i][2] give height, width, length of ‘i’th box respectively.
Initialize three integer variables ‘topWidth’:= INF, ‘topLength’ := INF, where INF denotes infinity. These variables will keep the length and width of the top of the stack of boxes in each recursive call.
Recursively try out all possible ways of placing these 3*n boxes and find out the maximum possible height of the stack of boxes. This can be done by performing the following step in each recursive call -:
- Initialize variable ‘maxHeight’ := 0
- Iterate over all 3*n boxes in each recursive call and if the width of the box is strictly less than ‘topWidth’ and the length of the box is strictly less than ‘topLength’ then try to place this box at the top of the stack by making a recursive call with ‘topWidth’ and ‘topLength’ as width and height of current box respectively. Update value of ‘maxHeight’ with a maximum of its current value and sum of the height of that box with the value obtained in that recursive call.
- Return ‘maxHeight’.

Return the value obtained by recursive function, this will represent the height of the highest possible stack.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of types of boxes.

The size of the matrix ‘boxes’ and the size of the implicit stack involved in recursion both will be of the order of ‘N’.

Time Complexity: O(n!)Explanation:

O((3 * N)!), where ‘N’ is the number of types of boxes.

In the worst case, the first call to recursive function can make 3 * N successive recursive calls, Each of which can further make 3 * (N - 1) recursive calls and so on.

Accepted Answer

Dynamic Programming

For any two boxes, ‘b1’ and ‘b2’ we can observe that box ‘b2’ can be placed above box ‘b1’ only if its base area is strictly less than the base area of box ‘b1’. This implies that boxes must be placed in decreasing order of base area from top to bottom in the stack. Thus if we sort all the types of boxes and their rotation in decreasing order, then the problem reduces to selecting a subsequence of boxes that forms a stack of maximum height and base dimensions of each box are strictly less than the base dimension of the box just below it. This problem is similar to Longest Increasing Subsequence using dynamic programming.

Make an integer matrix ‘boxes’ of dimension (3*n, 3), we will store all three rotations of each type of boxes in it.
Generate all 3 rotations for all ‘n’ types of boxes, for simplicity we will consider ‘width’ always smaller than or equal to ‘length’. Store them in matrix ‘boxes’ such that ‘boxes[i][0]’, ‘boxes[i][1]’, ‘boxes[i][2]’ give height, width, length of ‘i’th box respectively.
Sort the matrix ‘boxes’ in decreasing order of base area. Base area of i^th box is given by ‘boxes[i][1] * boxes[i][2]’.
Make an integer array ‘maxHeight’ of size 3*n, where maxHeight[i] will give the maximum height of the stack if the ‘i^th’ box after sorting is the topmost box of the stack.
Initialize an integer variable ‘result’:= 0, it will keep track of the maximum possible height of stack so far.
Run a loop where ‘i’ ranges from 0 to 3*n-1 and for each ‘i’ perform the following steps-:
- Assign ‘maxHeight[i]’ := ‘boxes[i][0]’.
- Run a loop where j ranges from 0 to i-1. If ‘boxes[j][1]’ and ‘boxes[j][2]’ is strictly greater than ‘boxes[i][1]’ and ‘boxes[i][2]’ respectively, then update ‘maxHeight[i]’ with maximum of its current value and sum of of ‘maxHeight[j]’ + ‘boxes[i][0]’.
- Update ‘result’ with the maximum of its current value and ‘maxHeight[i]’.
Return ‘result’

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of types of boxes.

The size of the matrix ‘boxes’ and the size of the array ‘maxHeight’ both will be of the order of ‘N’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the number of types of boxes.

Here, we have two nested loops and in the worst case, the outer and inner loop both will runs ‘N’ times.