Connection Status:
Competition Arena > RearrangingBoxes

RearrangingBoxes

2018 TCO Semi 2 · 2018-11-14 · by monsoon

2018 TCO Semi 2 · 2018-11-14 · by monsoon · Greedy
Class Name: RearrangingBoxes
Return Type: int[]
Method Name: rearrange
Arg Types: (int, int, int, long long)
Problem Statement

Problem Statement

The floor of a big warehouse consists of A*B unit square tiles. On each tile there is a tower of H unit cube boxes. All the A*B*H boxes currently form one big cuboid that exactly fills the warehouse.

The manager of the warehouse likes order, so he is pretty happy that the boxes fill the warehouse. Unfortunately for him, K boxes have to be delivered somewhere else, thus only A*B*H - K boxes will remain in the warehouse. The manager wants to have something that will remind him of how nice it was having the full cuboid, so he wonders whether he will be able to rearrange the remaining boxes in such a way that the surface area of the resulted solid will be exactly the same as the surface area of the original cuboid, i.e., 2*(A*B + A*H + B*H).

The boxes must be stacked in such a way that on each tile there is a tower consisting of at most H boxes. (Boxes cannot levitate in the air. Towers of height zero are allowed.) Moreover, the resulting solid must be connected. (Two boxes are directly connected if they share a face; a solid is connected if all pairs of boxes are connected, directly or indirectly.)

If the manager cannot rearrange the boxes according to his wishes, return an empty int[]. Otherwise, imagine the floor of the warehouse as a rectangle with A rows and B columns. Return a int[] of size A*B which contains the heights of towers in the rearranged warehouse, in row major order. If there are multiple solutions, you may return any of them.

Constraints

  • A and B will be between 1 and 30, inclusive.
  • H will be between 1 and 10^9, inclusive.
  • K will be between 1 and A*B*H-1, inclusive.
Examples
0)
3
2
2
2
Returns: {2, 2, 2, 1, 2, 1 }

A cuboid of size 3 × 2 × 2 has surface area of 32. Removing two boxes in the way shown below does not change the surface area. 2 2 2 2 2 2 --> 2 1 2 2 2 1

1)
1
1
3
1
Returns: { }

Removing one box from a cuboid of size 1 × 1 × 3 can only result in a cuboid of size 1 × 1 × 2 which clearly has a smaller surface area.

2)
3
2
3
9
Returns: { }

Another impossible situation. Note that the figure below doesn't show a valid solution, since the solid is not connected: 3 0 0 3 3 0

3)
3
3
10
42
Returns: {0, 10, 0, 10, 8, 10, 0, 10, 0 }

10 10 10 0 10 0 10 10 10 --> 10 8 10 10 10 10 0 10 0

4)
1
2
1
1
Returns: { }

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

Coding Area

Language: C++17 · define a public class RearrangingBoxes with a public method vector<int> rearrange(int A, int B, int H, long long K) · 345 test cases · 2 s / 256 MB per case

Submitting as anonymous