Connection Status:
Competition Arena > PackingSquares

PackingSquares

TCO13 Championship Round · 2013-02-19 · by gojira_tc

TCO13 Championship Round · 2013-02-19 · by gojira_tc · Greedy
Class Name: PackingSquares
Return Type: long
Method Name: leastArea
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Manao is given a sequence of squares numbered from 0 to N-1. The i-th square has side length equal to 2^a[i].

In the beginning, there is only an empty plane. Manao will process the squares one after another, in the order in which they are given. He will pick a parent object for each of the squares and then move the square onto its parent object. The parent object can be either the plane or one of the already processed squares. Each square must lie entirely within (or exactly cover) its parent object. Also, two children of the same object must never have an intersection with a positive area. (I.e., siblings may share a common boundary but they must not overlap.)

Given an int[] a, return the minimum possible covered area of the plane at the end of the process described above.

Notes

  • The answer will always fit in a signed 64-bit integer.

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will be between 0 and 30, inclusive.
Examples
0)
{0, 1, 2}
Returns: 21

Manao has three squares with side lengths 1, 2 and 4. The parent for the first square can only be the plane. Since the second square does not fit into the first one, its parent should also be the plane. The same happens to the third square. Thus, the area used on the plane is equal to 1 + 4 + 16 = 21.

1)
{1, 0, 0, 0, 0, 0, 0, 0}
Returns: 4

The square 0 is put on the plane. For each i > 0, square i-1 can be the parent of square i.

2)
{2, 1, 0, 2, 1}
Returns: 20

Manao can use 20 units of the plane if he assigns parents as follows: Square 0: plane. Square 1: plane. Square 2: square 1. Square 3: square 0. Square 4: square 3.

3)
{30, 0, 1}
Returns: 1152921504606846976

The square of side 2^30 is placed on the plane. The square of side 1 can then be placed in the square of side 2^30. Finally the square of side 2 can not be placed in the square of side 1, but can be placed in the square of side 2^30 without intersecting its sibling square of side 1.

4)
{6, 5, 12, 15, 14, 5, 6, 5, 13, 15, 11, 11}
Returns: 1358958592

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

Coding Area

Language: C++17 · define a public class PackingSquares with a public method long long leastArea(vector<int> a) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous