CO92MATR - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes ## Problem Link
Practice

Contest

Difficulty

Easy

PREREQUISITES:

Implrementation

Problem

A matrix is non-decreasing if every row and column is non decreasing. Given a matrix with some unknowns, complete the unknowns to get a non-decreasing matrix.

Explanation

Let A[i][j] denote the element at row i and column j of matrix A. Since the matrix is non-decreasing, the following two conditions should be held:

  • A[i][j] ≥ A[i][j-1], in row i elements are non-decreasing.
  • A[i][j] ≥ A[i-1][j], in column j elements are non-decreasing.
This implies that A[i][j] ≥ A[r][c] for every 1 ≤ r ≤ i, 1 ≤ c ≤ j (one element is greater than all the elements that are up to the left).

Let i be the first row of A that contains a -1 and in this row let j be the column of the leftmost -1. It is always convenient to replace A[i][j] with the minimum possible value, otherwise it may be impossible to find a valid value for another -1 that is down to the right. So one possible solution (and the lexicographically smallest) is to set A[i][j] = max { A[i][j-1], A[i-1][j] }.

After filling some of the unknown positions in A, it may turn out that one of the values of A is smaller than some of the elements that are up to the left. In this case there is no solution.

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

3 Likes