EllysPyramid | Topcoder Archive

Problem Statement

Elly plays a computer game where she must build Aztec-like pyramid. The game is two-dimensional and the ground is represented as the X-axis.

Large stones of height 1 pixel and various widths fall from the sky at different locations (measured from the left side of the screen). The stones fall one after another and the girl can decide for each of them to either destroy it or leave it fall. The first stone block the girl decides to leave falls on the ground - that is the base of the pyramid. After that whenever she decides to leave a block fall, it must fall completely within the interval of the last fallen block. For example, if the last fallen block started at pixel L and ended at pixel R (both inclusive), the next non-destroyed block should have start and end within the interval [L, R].

By leaving stone blocks fall on top of previously fallen blocks a pyramid is build. The goal of the game is to build the highest possible pyramid.

You are given two int[]s L and R. The i-th element of these describes the left and right inclusive boundaries of the i-th stone block. Return an int giving the maximal height of a pyramid the girl can build.

Definition

Class:: EllysPyramid
Method:: getHeight
Parameters:: int[], int[]
Returns:: int
Method signature:: int getHeight(int[] L, int[] R)
(be sure your method is public)

Notes

Please note that the girl cannot move the blocks - she can only decide whether to destroy them or let them fall.
Note that only one block can touch the ground and each non-destroyed block after that must fall within the boundaries of the top block of the pyramid.
It is possible that a stone starting at L and ending at R falls on a stone that also starts at L and ends at R (i.e. covers it exactly).

Constraints

L and R will contain between 1 and 50 elements, inclusive.
L and R will contain the same number of elements.
Each element of L and R will be between 1 and 1000, inclusive.
For each valid index i, L[i] will be less than or equal to R[i].

Examples

```
{3, 2, 3, 4, 2, 3, 5, 5}
```
```
{4, 7, 7, 6, 7, 9, 5, 5}
```
```
Returns: 5
```
It is better to destroy the first block (since it is rather small) and let the base of the pyramid be the second one - from 2 to 7. The third one we can also leave fall - [3, 7] is fully within [2, 7]. We also take [4, 6]. The next block (from 2 to 7) cannot be taken if the last one is [4, 6] (it is outside its boundaries). Please note that if we've discarded [3, 7] and [4, 6] we could have taken [2, 7] (on top of the other [2, 7]). However, this would lead to a sub-optimal answer. We cannot take [3, 9] either, since it is also outside the interval [4, 6]. Finally, we take both [5, 5] blocks, for a total height of 5: ([2, 7], [3, 7], [4, 6], [5, 5], [5, 5]).
```
{13, 42, 123}
```
```
{17, 42, 666}
```
```
Returns: 1
```
In this test we can only lay the base of a pyramid in three different locations. No matter which one we chose, the answer is one.
```
{5, 4, 3, 2, 1}
```
```
{6, 7, 8, 9, 10}
```
```
Returns: 1
```
Please note that the order in which the blocks fall matters.
```
{100, 100, 100}
```
```
{200, 200, 200}
```
```
Returns: 3
```
It is possible that a block is placed on top of a block of the same size.

{60, 124, 77, 16, 334, 241, 118, 419, 448, 224, 247, 202, 396, 192, 65, 120, 82, 529, 224, 88, 428, 674, 97, 762, 670, 538, 45, 381, 589, 231, 111, 373, 817, 105, 720, 857, 225, 801, 569, 793, 776, 20}

{1000, 941, 873, 689, 974, 793, 632, 928, 916, 691, 629, 566, 752, 526, 387, 426, 377, 823, 494, 352, 686, 931, 349, 997, 900, 768, 274, 595, 797, 430, 303, 563, 981, 256, 870, 985, 318, 893, 634, 833, 805, 23}

Returns: 7

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.