NicePartition
SRM 781 · 2020-03-19 · by sinus_070
Problem Statement
Optimus Prime wants to build 2*N buildings.
You are given their heights in the
The buildings have to be partitioned into two rows: row A and row B. We will use A[i] to denote the height of the i-th building (0-based index) in row A, and B[i] for row B. The partition into A and B must satisfy the following constraints:
- Each row must contain N buildings.
- The rows must be aligned: for each i, the i-th building in row A will stand opposite to the i-th building in row B.
- The heights of buildings in row A must form a non-decreasing sequence: for each i, A[i] <= A[i+1].
- The heights of buildings in row B must form a non-increasing sequence: for each i, B[i] >= B[i+1].
The instability of a pair of buildings that stand opposite each other is the absolute difference between their heights: | A[i] - B[i] |.
The instability of the whole partition is the total instability over all N such pairs of buildings.
Optimus Prime wants the most optimistic partition: the one whose instability is minimal. Calculate and return the smallest possible instability of the partition of Optimus Prime's buildings.
Constraints
- Length of H will be an even integer between 2 and 400, inclusive.
- Each element of H will be between 0 and 500, inclusive.
{0,2}
Returns: 2
There are two possible partitions: either A = {2} and B = {0}, or A = {0} and B = {2}. In each case the instability is |2-0| = 2.
{3,5,1,5,7,9}
Returns: 12
Partition A = {3,7,9} B = {5,5,1} gives the minimum instability. Its instability is |3-5| + |7-5| + |9-1| = 2 + 2 + 8 = 12. There are other partitions which give the minimum instability as well. One of them is: A = {1,5,5} B = {9,7,3}
{31,52,11,52,73,19,54,124,21,1}
Returns: 272
One optimal partition: A = {19,21,31,54,73} B = {124,52,52,11,1} Instability = |19-124| + |21-52| + |31-52| + |54-11| + |73-1| = 272
{1,1,1,1,1,1}
Returns: 0
{427,251,203,280,227,393,497,191,247,99,242,147,353,330,500,16,232,370,100,294,391,123,440,55,309,402,324,179,256,103,245,35,316,173,192,241,376,102,336,61,74,286,156,320,185,293,388,252,226,2,407,13,85,217,275,219,488,306,301,22,82,18,23,164}
Returns: 6930
Submissions are judged against all 52 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NicePartition with a public method int minCost(vector<int> H) · 52 test cases · 2 s / 256 MB per case