BuildingReorganization | Topcoder Archive

Problem Statement

The greatest king of all times, Michael IV, is going to make big changes in the capital of his kingdom.

There are N buildings in the capital. They are located in a row and numbered 0, 1, ..., N-1 from left to right. The height of building i is heights[i] floors. Each floor of each building has the shape of a unit cube.

The current state of the capital is miserable: there are just buildings and no infrastructure, so people are unhappy. Michael decided to deconstruct two buildings and to build a mall and an entertainment center in their locations. The buildings that Michael wants to deconstruct have numbers A and B.

Deconstruction of buildings is a non-trivial process. It is organized as a sequence of operations. Each operation consists of exactly 4 steps:

Choose one of two deconstructed buildings (A or B). Let X be the chosen building.
Lower the topmost floor in X to the ground in front of building X. Lowering the floor by a unit of distance costs 1 coin. I.e., if the building now has H floors, the total cost of lowering the topmost floor is H-1 coins. Note that once we lower the topmost floor, the new height of the building becomes H-1.
Choose a building Y different from A and B. Move the floor from the ground in front of building X to the ground in front of building Y. This operation costs cost * |X - Y| coins.
Lift the floor onto the top of building Y. Lifting the floor by a unit of distance has the same cost as lowering it. I.e., it costs H coins to lift the currently processed floor on the top of a building that currently has H floors. Note that once we are done, the new height of building Y will be H+1.

The deconstruction process is finished once both buildings A and B have no floors anymore.

Return the minimum possible total cost of the whole process, in coins.

Definition

Class:: BuildingReorganization
Method:: theMin
Parameters:: int[], int, int, int
Returns:: long
Method signature:: long theMin(int[] heights, int A, int B, int cost)
(be sure your method is public)

Constraints

heights will contain exactly N elements, where N is between 3 and 50, inclusive.
Each element of heights will be between 1 and 500,000,000, inclusive.
A will be between 0 and N - 2, inclusive.
B will be between A + 1 and N - 1, inclusive.
cost will be between 1 and 10,000,000, inclusive.

Examples

```
{5, 5, 5}
```
```
0
```
```
2
```
```
10
```
```
Returns: 215
```
There is not much choice here. All floors must be placed onto the top of building 1. The order in which individual floors of buildings 0 and 2 are deconstructed does not matter.
```
{5, 5, 5, 5}
```
```
0
```
```
3
```
```
10
```
```
Returns: 190
```
All floors of building 0 should be placed onto the top of building 1. All floors of building 3 should be placed onto the top of building 2.
```
{5, 50, 1, 50, 5}
```
```
0
```
```
4
```
```
10
```
```
Returns: 275
```
Buildings 1 and 3 are very tall, so it's expensive to extend them. All floors of buildings 0 and 4 should go onto the top of building 2, in any order.
```
{5, 50, 1, 50, 5}
```
```
0
```
```
4
```
```
1000
```
```
Returns: 10540
```
The same case as above, but horizontal movement is much more expensive. Now it's cheaper to extend buildings 1 and 3.
```
{5, 50, 1, 50, 5}
```
```
1
```
```
3
```
```
1000
```
```
Returns: 104428
```
```
{4,1,1,1000,1,1}
```
```
0
```
```
4
```
```
1
```
```
Returns: 20
```

{157,10,157,979797,152152152,156,4,77,157,79}

Returns: 13041277280686205

{346455317,453638062,491871419,297060164,426458223,53746370,422461742,231053793,309679268,297959075,
 76653026,277375296,411684823,427164497,257399925,224643292,114988354,457289888,51199847,199807287,
 110648220,303379857,435712111,245040291,401790144,260999362,6953083,385721020,438059362,434000869,
 481788278,70215282,135651128,68577856,448298562,11191117,408997160,407134756,10781024,267655550,
 183460325,284786399,222774818,193425138,51658225,117130718,352764522,342521474,147243649,265160879}

Returns: 234928185619577559

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.