StairsFromBlocks | Topcoder Archive

Problem Statement

A perfect staircase made of unit cubes looks as follows: It goes from the left to the right. The first step is just a single cube, and each following step is 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.)

We can also use larger blocks when building such staircases. Each of these blocks will be a cuboid with two parameters: width (measured left to right) and height (measured bottom to top).

These blocks are too heavy to lift, we can only push them around. Thus, all blocks must always stand on the ground, they cannot be placed on top of other blocks and/or unit cubes.

Below is another example staircase. This one is built out of a 1x3 block (width 1, height 3, denoted '0'), a 3x2 block (denoted '1') and some unit cubes (denoted '#').


      #
     ##
    ###
   0###
  #0111
 ##0111

You are given a collection of blocks: for each valid i you have a block that's W[i] units wide and H[i] units tall.

Calculate and return the minimum number of additional unit size cubes we need in order to build a perfect staircase that contains all of the given blocks.

(The staircase must go left to right. The blocks may appear inside the staircase in any order, and they don't have to be next to each other - see examples.)

Definition

Class:: StairsFromBlocks
Method:: build
Parameters:: int[], int[]
Returns:: long
Method signature:: long build(int[] W, int[] H)
(be sure your method is public)

Notes

The blocks are also too heavy to tilt, so we cannot rotate them. E.g., a 3x2 block cannot be flipped and used as a 2x3 block.

Constraints

W will have between 1 and 100 elements, inclusive.
H will have the same number of elements as W.
All elements of W and H will be positive integers.
For each i, W[i] * H[i] will be greater than 1.
The sum of W will not exceed 10^9.
The sum of H will not exceed 10^9.

Examples

```
{3}
```
```
{3}
```
```
Returns: 6
```
We have a single 3x3 block. The best way to convert it into a complete valid staircase is shown below ('0's denote the block, '#'s are added unit cubes). # ## 000 #000 ##000
```
{1, 1, 1}
```
```
{3, 3, 4}
```
```
Returns: 5
```
A similar input to Example 0. Instead of a single block of width 3 we have three blocks of width 1 each that can be arranged into a similar shape. One optimal solution is shown below (using '0', '1' and '2' for the three blocks in the order in which they were given): # 2# 021 #021 ##021 (Note that we can put the blocks in any order we like, we don't have to preserve their original order.
```
{2, 2}
```
```
{2, 5}
```
```
Returns: 7
```
One optimal solution is shown below. Note that there may be gaps between the blocks. # 11 #11 ##11 00#11 #00#11
```
{6}
```
```
{1}
```
```
Returns: 15
```
Here it's optimal to build the entire staircase on top of the given block. The block will be the only thing touching the ground.
```
{2, 2, 2}
```
```
{1, 1, 1}
```
```
Returns: 15
```
We put the three blocks next to each other and we get the situation from the previous example.

{1234567}

{2345678}

Returns: 3513178688464

Watch out for integer overflow.

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.