NicePartition | Topcoder Archive

Problem Statement

Optimus Prime wants to build 2*N buildings. You are given their heights in the int[] H.

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.

Definition

Class:: NicePartition
Method:: minCost
Parameters:: int[]
Returns:: int
Method signature:: int minCost(int[] H)
(be sure your method is public)

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.

Examples

```
{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
```

{463,210,438,95,300,192,114,72,330,226,125,193,384,326,338,6}

Returns: 1798

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.