ReconstructStairs | Topcoder Archive

Problem Statement

There once was a perfect staircase made of unit cubes. The staircase went from the left to the right. The first step was just a single cube, and each following step was built using one more cube than the previous one.

An example of such a staircase is shown below:


      #
     ##
    ###
   ####
  #####
 ######

(This is a 6-step staircase. It is built using 1+2+3+4+5+6 unit cubes.)

The perfect staircase that once existed has been damaged over time: from some columns some cubes disappeared. Of course, gravity still works, so in each column the remaining cubes are still on the bottom.

You are given the heights of all the remaining columns, from the left to the right, in the int[] columns. For example, columns = { 3, 1, 0, 4, 0, 0, 2 } represents the following configuration of cubes:


     #
  #  #
  #  #  #
  ## #  #
  3104002

You were given the task to repair the staircase: add some (possibly zero) new cubes so that the result will be a perfect staircase that goes to the right.

The staircase must contain all the existing cubes. The existing cubes cannot be moved from their current locations.

You can choose the size and the exact position of your staircase. While building it, you are allowed to add completely new columns of cubes (see Example #3).

Return the minimum number of additional cubes needed to repair the given staircase.

Definition

Class:: ReconstructStairs
Method:: reconstruct
Parameters:: int[]
Returns:: int
Method signature:: int reconstruct(int[] columns)
(be sure your method is public)

Constraints

columns will contain between 1 and 50 elements, inclusive.
Each element of columns will be between 0 and 50, inclusive.
Sum of columns will not be zero.

Examples

```
{1, 2, 3, 4}
```
```
Returns: 0
```
This is a correct 4-step staircase. There is no need to add any new cubes.
```
{0, 0, 1, 2, 3, 4, 0, 0}
```
```
Returns: 0
```
This is the same staircase, only now the input also contains some empty columns. We can just ignore those, it is not required to fill them with cubes.
```
{1, 2, 1, 4}
```
```
Returns: 2
```
The input looks as follows: # # # # #### 1214 We can fix it to make a valid staircase by adding two new cubes (denoted 'O' below) into the column that's currently too short: # O# #O# ####
```
{3, 2, 1}
```
```
Returns: 9
```
The input looks as follows: # ## ### 321 This is not a valid staircase, because a valid staircase must go from the left to the right. The optimal way of changing this input into a valid staircase is shown below. O OO #OO O##O OO### (We added a total of 9 new cubes. Note that we added two new columns of cubes to the left of the leftmost given column.)
```
{0, 1, 0, 0, 0, 0, 1, 0}
```
```
Returns: 19
```
The optimal solution here is to build a staircase of size 6 that starts with the leftmost given cube as its first step.
```
{1}
```
```
Returns: 0
```
A single cube is a valid staircase of size 1, i.e., a staircase that consists of just a single step.
```
{3, 1, 0, 4, 0, 0, 2}
```
```
Returns: 35
```
This is the example structure from the problem statement.

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.