PascalsBrokenTriangle | Topcoder Archive

Problem Statement

In a standard Pascal's triangle, the n-th row contains exactly n values. (Here and below all indices are 1-based.) The first row contains a single value: 1. The i-th value of n-th row for n >= 2 is defined as follows: the first and the last values equal the first and the last values of the previous row, respectively, and for all 1 < i < n, i-th value is the sum of the i-th and (i-1)-th values of the previous row.
The first five rows of the standard Pascal's triangle look like this:

       1                                1
      1 1                              1 1
    1 1+1 1            =&gt;             1 2 1
  1 1+2 2+1 1          =&gt;            1 3 3 1
1 1+3 3+3 3+1 1        =&gt;           1 4 6 4 1
      ...                              ...

Our broken Pascal's triangle has some values which are replaced by zeros during the calculation. The position of j-th of these values is given by (rows[j], cols[j]).

Given the list of the cells to be replaced by zeros in rows and cols, return the values in row number rowNum of the broken Pascal's triangle.

Definition

Class:: PascalsBrokenTriangle
Method:: getRow
Parameters:: int[], int[], int
Returns:: int[]
Method signature:: int[] getRow(int[] rows, int[] cols, int rowNum)
(be sure your method is public)

Constraints

rows and cols contain between 0 and 50 elements, inclusive.
rows and cols contain the same number of elements.
Each element of rows will be between 1 and 32, inclusive.
Element j of cols will be between 1 and rows[j], inclusive.
rowNum will be between 1 and 32, inclusive.

Examples

```
{}
```
```
{}
```
```
5
```
```
Returns: {1, 4, 6, 4, 1 }
```
This is a standard Pascal's triangle, as depicted in the problem statement.
```
{3}
```
```
{2}
```
```
6
```
```
Returns: {1, 3, 4, 4, 3, 1 }
```
The triangle ends up looking like this: 1 1 1 1 0 1 1 1 1 1 1 2 2 2 1 1 3 4 4 3 1
```
{2, 2}
```
```
{1, 1}
```
```
3
```
```
Returns: {0, 1, 1 }
```
The list of zeroed out cells can have duplicate entries.

{3, 6}

{2, 4}

Returns: {1, 5, 11, 11, 7, 7, 5, 1 }

```
{5, 6}
```
```
{3, 2}
```
```
4
```
```
Returns: {1, 3, 3, 1 }
```
The zeroed out values are all below the row we care about.

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.