Connection Status:
Competition Arena > TheMountain

TheMountain

TCO13 Round 2C · 2013-02-19 · by ir5

TCO13 Round 2C · 2013-02-19 · by ir5 · Brute Force, Math, Simple Math, Simulation
Class Name: TheMountain
Return Type: int
Method Name: minSum
Arg Types: (int, int, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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.)

Submissions are judged against all 125 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheMountain with a public method int minSum(int n, int m, vector<int> rowIndex, vector<int> columnIndex, vector<int> element) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous