Connection Status:
Competition Arena > TwoTowers

TwoTowers

2022 TCO Parallel 1B · 2022-04-14 · by misof

2022 TCO Parallel 1B · 2022-04-14 · by misof · Greedy, Simple Math, Sorting
Class Name: TwoTowers
Return Type: int
Method Name: maxDifference
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

The figure below shows a tower of rectangles that consists of three rectangles: a 5x3 rectangle A, a 4x4 rectangle B, and a 1x9 rectangle C. 


    AAA
    AAA
    AAA
    AAA
    AAA
    BBBB
    BBBB
    BBBB
    BBBB
   CCCCCCCCC

In such a tower there are only two rules:

  1. The rectangles must form a single sequence from top to bottom, each rectangle standing on the next one (except for the bottom one that stands on the ground).
  2. The bottom side of each rectangle must completely stand on the top side of the rectangle immediately below it. (The touching sides may be exactly equal.)

Note that the second rule implies that as we go from the top to the bottom, the width of the tower never decreases.


Alice and Bob have a collection of N rectangles. You are given their description: the int[]s A and B, each containing N elements. For each valid index i, one of their rectangles has the dimensions A[i] times B[i].

When building the tower, the rectangles can be rotated by multiples of 90 degrees. E.g., a 5x3 rectangle can be also used as a 3x5 rectangle. The rectangles can be used in any order.


Alice used all N rectangles to build the tallest possible tower. Then, Bob took apart Alice's tower and instead he used all N rectangles to build the shortest possible tower. Return the difference between the heights of those two towers.

Notes

  • For any collection of rectangles there is always at least one way to rotate them and reorder them into a valid tower, so the return value is always well-defined.

Constraints

  • A will have between 1 and 50 elements, inclusive.
  • Each element of A will be between 1 and 10^6, inclusive.
  • B will have the same number of elements as A.
  • Each element of B will be between 1 and 10^6, inclusive.
Examples
0)
{3}
{5}
Returns: 2

A single 3x5 rectangle. Alice will place it as follows: AAA AAA AAA AAA AAA while Bob will place it as follows: AAAAA AAAAA AAAAA Thus, Alice's tower has height 5, Bob's tower has height 3, and the difference is 5-3 = 2.

1)
{5, 4, 1}
{3, 4, 9}
Returns: 10

These are the three rectangles from the first figure in the problem statement. That particular tower (of height 10) is neither the tallest nor the shortest tower possible: Alice can build a tower of height 18 and Bob can build a tower of height 8.(Note that each of them needs to rotate and reorder the rectangles in a different way. For example, Bob's tower must have the 4x4 square on the top.)

2)
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: 0

Here the rotations do not matter (all rectangles are actually squares) and their order is forced: both Alice and Bob must place them from the smallest one on the top to the largest one on the bottom. Thus, they will both build the same tower and the height difference is zero.

3)
{1}
{1}
Returns: 0
4)
{1, 2, 3}
{3, 2, 1}
Returns: 4
101)
{2, 2, 2, 2, 2}
{2, 2, 2, 2, 2}
Returns: 0

Here we have five identical 2x2 squares. They can be rotated and reordered arbitrarily, but it will still be a collection of five identical squares. So even though there are 2^5 ways to rotate them and then 5! possible orders, each time you will end up with exactly the same tower: a rectangle of width 2 and height 10.Thus, Alice will build a tower of height 10, Bob will build a tower of height 10, and the difference is 10-10 = 0.

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

Coding Area

Language: C++17 · define a public class TwoTowers with a public method int maxDifference(vector<int> A, vector<int> B) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous