Connection Status:
Competition Arena > BoxTower

BoxTower

SRM 310 · 2006-07-06 · by misof

SRM 310 · 2006-07-06 · by misof · Brute Force, Dynamic Programming, Sorting
Class Name: BoxTower
Return Type: int
Method Name: tallestTower
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You have N boxes of various sizes. You would like to stack some of them upon each other to create a tower that's as tall as possible.

When building the tower, you are allowed to reorder and rotate the boxes. However, the tower must obey the following rules:

  • The tower must be constructed by repeatedly taking an unused box and placing it on top of the current tower.
  • Each box must have sides parallel to the sides of the bottommost box.
  • If a box A is placed on box B, then the entire bottom side of A must be placed on the top side of B. In other words, no part of the bottom side of A may overhang the top side of B.

You are given the dimensions of the boxes as three int[]s x, y, and z. The i-th elements in x, y, and z specify the dimensions of the i-th box. Return an int giving the height of the tallest tower that can be constructed using the above rules.

Notes

  • If the bottom side of one box is equal to the top side of another box, they may be placed atop each other.

Constraints

  • x will contain between 1 and 15 elements, inclusive.
  • x, y, and z will contain the same number of elements.
  • Each element in x, y, and z will be between 1 and 10,000,000, inclusive.
Examples
0)
{10, 50, 40, 20, 30}
{10, 50, 40, 20, 30}
{10, 50, 40, 20, 30}
Returns: 150

All five boxes are cubes of different sizes. They can all be used to build a tower.

1)
{20, 30}
{20, 30}
{20, 10}
Returns: 30

This time we have two boxes: a 20x20x20 cube, and a 30x30x10 slab. The best solution is to place the slab on its largest side, and then to put the cube on the top of it.

2)
{20, 30}
{20, 33}
{20, 10}
Returns: 33

Now the slab is a bit longer, and the best solution is to use only the slab, standing on its 10x30 side.

3)
{100, 100}
{10, 12}
{10, 8}
Returns: 110

Note that if both boxes are rotated so that their height is 100, neither can be placed on top of the other.

4)
{100, 90, 15}
{100, 88, 15}
{100, 12, 89}
Returns: 205

Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BoxTower with a public method int tallestTower(vector<int> x, vector<int> y, vector<int> z) · 83 test cases · 2 s / 256 MB per case

Submitting as anonymous