B - Mongeness Editorial by en_translator


The problem can be solved by actually checking if the given grid satisfies the conditions given in the problem statement. In other words, we literally check for every tuples of integers \((i_1, i_2, j_1, j_2)\) such that \(1 \leq i_1 < i_2 \leq H\) and \(1 \leq j_1 < j_2 \leq W\) if \(A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2}\).

In order to check if a tuple of integers \((i_1, i_2, j_1, j_2)\) satisfies \(A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2}\), we can use the feature of conditional branch in a programming language (for instance, in C++, if statement will do). Also, executing this check for every tuples of integers we want is achieved by the loop feature in a programming language (e.g. in C++, for statement will do.)

The time complexity of this solution is \(\mathrm{O}(N^4)\).

A sample code in C++ follows.

#include <iostream>
using namespace std;

int main(void)
{
  int h, w;
  int a[51][51];

  cin >> h >> w;
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      cin >> a[i][j];
    }
  }

  for(int i_1 = 1; i_1 <= h; i_1++){
    for(int i_2 = i_1+1; i_2 <= h; i_2++){
      for(int j_1 = 1; j_1 <= w; j_1++){
        for(int j_2 = j_1+1; j_2 <= w; j_2++){
          if(a[i_1][j_1] + a[i_2][j_2] > a[i_2][j_1] + a[i_1][j_2]){
            cout << "No" << endl;
            return 0;
          }
        }
      }
    }
  }

  cout << "Yes" << endl;

  return 0;
}

Such matrix \(A\) that satisfies the conditions in the problem statement (those with the answer Yes) is called a Monge array or a Monge matrix. It is known that \(A\) is a Monge matrix if and only if:

For all pairs of integers \((i, j)\) such that \(1 \leq i \leq H-1\) and \(1 \leq j \leq W-1\), \(A_{i, j} + A_{i+1, j+1} \leq A_{i+1, j} + A_{i, j+1}\).

Therefore, we can also solve this problem in a total of \(\mathrm{O}(N^2)\) time by checking if the given grid satisfies the condition above.

posted:
last update: