JOIN
Get Time

   Problem Statement  

 Problem Statement for TheMountain

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

0)
    
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.
1)
    
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]
2)
    
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]
3)
    
2
2
{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]
4)
    
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.)
5)
    
123
45
{2, 3, 5, 7, 11}
{13, 17, 19, 23, 29}
{100, 200, 300, 400, 500}
Returns: 367047
6)
    
200
200
{5}
{8}
{666}
Returns: 5737554
7)
    
10
10
{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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2013 TCO Algorithm Round 2C - Division I, Level Two
       2013 TCO Algorithm Parallel Round 2C - Division I, Level Two