TheMountain | Topcoder Archive

Problem Statement

You are given ints n and m: the dimensions of a matrix. A matrix M with n rows and m columns is called a mountain if it satisfies the following conditions:

All elements of M are positive integers.
There are integers a and b with the following properties:
- 0 <= a <= n-1 and 0 <= b <= m-1.
- For each row i, M[i][0] < M[i][1] < ... < M[i][b-1] < M[i][b] > M[i][b+1] > ... > M[i][m-1].
- For each column j, M[0][j] < M[1][j] < ... < M[a-1][j] < M[a][j] > M[a+1][j] > ... > M[n-1][j].

In addition to n and m, you are given some elements of M. More precisely, you are given the int[]s rowIndex, columnIndex and element. For each valid k, M[rowIndex[k]][columnIndex[k]] has to be element[k]. Your task is to fill in the missing values so that M becomes a mountain. Find and return the smallest possible sum of all elements in a mountain M that matches the given constraints. If there is no mountain that matches the given constraints, return -1 instead.

Definition

Class:: TheMountain
Method:: minSum
Parameters:: int, int, int[], int[], int[]
Returns:: int
Method signature:: int minSum(int n, int m, int[] rowIndex, int[] columnIndex, int[] element)
(be sure your method is public)

Constraints

n and m will each be between 1 and 200, inclusive.
rowIndex will contain between 1 and min(n*m, 50) elements, inclusive.
columnIndex and element will contain the same number of elements as rowIndex.
Each element of rowIndex will be between 0 and n-1, inclusive.
Each element of columnIndex will be between 0 and m-1, inclusive.
Each element of element will be between 1 and 1,000, inclusive.
No two indices represented by rowIndex and columnIndex will be the same.

Examples

```
2
```
```
3
```
```
{0, 0, 0, 1, 1, 1}
```
```
{0, 1, 2, 0, 1, 2}
```
```
{4, 6, 9, 1, 3, 6}
```
```
Returns: 29
```
We are already given all elements of this matrix. It looks as follows: [4 6 9] [1 3 6] We can easily verify that this is a mountain for a=0 and b=2. The sum of all elements is 4+6+9+1+3+6=29.
```
2
```
```
3
```
```
{1, 0, 1}
```
```
{2, 2, 0}
```
```
{5, 7, 6}
```
```
Returns: 40
```
The matrix looks as follows. [? ? 7] [6 ? 5] The optimal solution is as follows. The sum is 7+8+7+6+7+5=40. [7 8 7] [6 7 5]
```
3
```
```
3
```
```
{0, 0, 2, 2}
```
```
{0, 2, 2, 0}
```
```
{1, 1, 1, 1}
```
```
Returns: 15
```
The matrix looks as follows: [1 ? 1] [? ? ?] [1 ? 1] The optimal solution is as follows. [1 2 1] [2 3 2] [1 2 1]

{0, 0, 1, 1}

{0, 1, 1, 0}

{5, 8, 5, 8}

Returns: -1

The given matrix is not a mountain. [5 8] [8 5]

```
1
```
```
3
```
```
{0}
```
```
{1}
```
```
{1}
```
```
Returns: -1
```
This matrix looks as follows: [? 1 ?] It is not possible to make a mountain out of it, because in a mountain all elements have to be positive. (Note that 0 is not positive.)

{2, 3, 5, 7, 11}

{13, 17, 19, 23, 29}

{100, 200, 300, 400, 500}

Returns: 367047

```
200
```
```
200
```
```
{5}
```
```
{8}
```
```
{666}
```
```
Returns: 5737554
```

{0, 8, 7}

{3, 1, 9}

{5, 4, 7}

Returns: 593

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.