E - Integers on Grid Editorial by en_translator


We denote the integer written on the square \((i, j)\) by \(A[i][j]\).

We solve this problem with Dynamic Programming (DP).
For \(i = 1, 2, \ldots, N\), let us define \(\mathrm{dp}[i]\) as follows.

\(\mathrm{dp}[i] := \) (the maximum number of move that Takahashi can make from now on if the piece is on the square \((r_i, c_i)\))

This problem asks to find \(\mathrm{dp}[i]\) for every \(i = 1, 2, \ldots, N\). We will describe how to find them.

When the piece is currently in the square \((r_i, c_i)\), he can move the piece to the square \((r_j, c_j)\) if and only if the following two conditions hold:

\(A[r_i][c_j] > A[r_i][c_i]\) the square \((r_i, c_i)\) and the square \((r_j, c_j)\) are in the same row, or, the square \((r_i, c_i)\) and the square \((r_j, c_j)\) or in the same column; in other words, \(r_j = r_i\) or \(c_j = c_i\).

If there are no such square \((r_j, c_j)\), then the piece cannot be moved from the square \((r_i, c_i)\), so \(\mathrm{dp}[i] = 0\).
If there exists such a square, then it is optimal to choose “such square that after moving it there, the number of moves that he can make afterwards is maximum” as the destination of the next move; that is,

\(\mathrm{dp}[i] = \max\lbrace \mathrm{dp}[j] + 1\) \( | \) He can make a move from the square \((r_i, c_i)\) to the square \((r_j,c_j)\) \(\rbrace\).

With the recurrence relations above, one can determine the value \(\mathrm{dp}[i]\) for every \(i = 1, 2, \ldots, N\).
Here, note that by the time we compute \(\mathrm{dp}[i]\), we need the values \(\mathrm{dp}[j]\) for all \((r_j, c_j)\) that can be moved from \((r_i, c_i)\) already computed. This can be achieved by computing \(\mathrm{dp}[i]\) in the decreasing order of \(A[r_i][c_i]\), since the piece can be moved from the square \((r_i, c_i)\) to the square \((r_j, c_j)\) only if \(A[r_i][c_i] < A[r_j][c_j]\).
Thus, we can find the values of \(\mathrm{dp}[i]\) for all \(i = 1, 2, \ldots, N\) with the following algorithm.

Do the following operation in the decreasing order of \(X\):

  • For every square \((r_i, c_i)\) such that \(A[r_i][c_i] = X\), let \(\mathrm{dp}[i] \leftarrow \max\lbrace \mathrm{dp}[j] + 1\) \( | \) he can make a move from the square \((r_i, c_i)\) to the square \((r_j,c_j)\) \(\rbrace\). If there are no such squares that can be moved from the square \((r_i, c_i)\), then let \(\mathrm{dp}[i] \leftarrow 0\).

However, the algorithm above costs \(\Theta(N^2)\) time at worst, in which case it is hopeless of finishing in time. So, we will try to speed it up.

Consider doing the following step for a fixed positive integer \(X\):

For every square \((r_i, c_i)\) such that \(A[r_i][c_i] = X\), let \(\mathrm{dp}[i] \leftarrow \max\lbrace \mathrm{dp}[j] + 1\) \( | \) he can make a move from the square \((r_i, c_i)\) to the square \((r_j,c_j)\) \(\rbrace\).

Since a square to which a piece can move from the square \((r_i, c_i)\) is in the same row or column to \((r_i, c_i)\), so if we know the following two values before computing \(\mathrm{dp}[i]\), then \(\mathrm{dp}[i]\) can be found as the maximum of the following two in an \(O(1)\) time.

  • The maximum value of \(\mathrm{dp}[j]+1\) over “all square \((r_j, c_j)\) in the \(r_i\)-th row which are movable from the square \((r_i, c_i)\),” that is, \(\max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, r_j = r_i \rbrace\)
  • The maximum value of \(\mathrm{dp}[j]+1\) over “all square \((r_j, c_j)\) in the \(c_i\)-th column which are movable from the square \((r_i, c_i)\),” that is, \(\max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, c_j = c_i \rbrace\)

Therefore, by preparing two arrays \(\mathrm{rmax}[\ast]\) and \(\mathrm{cmax}[\ast]\), and maintaining the state that satisfies

  • for every \(r = 1, 2, \ldots H\), \(\mathrm{rmax}[r] = \max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, r_j = r\rbrace\), and
  • for every \(c = 1, 2, \ldots W\), \(\mathrm{cmax}[c] = \max \lbrace \mathrm{dp}[j] + 1 \) | \(A[r_j][c_j] > X, c_j = c\rbrace\)

during computing the values \(\mathrm{dp}[\ast]\) in the decreasing order of \(X\), one can find \(\mathrm{dp}[i]\) as literally \(\mathrm{dp}[i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{cmax}[c_i])\) in an \(O(1)\) time.
Therefore, the following algorithm enables us to find the values of \(\mathrm{dp}[i]\) for all \(i = 1, 2, \ldots, N\) fast enough.

First, initialize the variables as follows.

  • For every \(r =1, 2, \ldots, H\), let \(\mathrm{rmax}[r] \leftarrow 0\).
  • For every \(c =1, 2, \ldots, W\), let \(\mathrm{cmax}[c] \leftarrow 0\).

do the following steps in the decreasing order of \(X\):

  1. First, for every \(i\) such that \(A[r_i][c_i] = X\), let \(\mathrm{dp}[i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{cmax}[c_i])\).
  2. Next, for every \(i\) such that \(A[r_i][c_i] = X\), let \(\mathrm{rmax}[r_i] \leftarrow \max(\mathrm{rmax}[r_i], \mathrm{dp}[i] + 1), \mathrm{cmax}[r_i] \leftarrow \max(\mathrm{cmax}[r_i], \mathrm{dp}[i] + 1)\).

Hence, the problem can be solved in a total of \(O(N\log N + H + W)\) time.
A sample code in C++ language follows.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int h, w, n;
int r[200005], c[200005], a[200005];
int rmax[200005], cmax[200005];
int dp[200005];
map<int, vector<int> > mp;

int main(void)
{
  cin >> h >> w >> n;
  for(int i = 1; i <= n; i++){
    cin >> r[i] >> c[i] >> a[i];
    mp[a[i]].push_back(i);
  }

  for(auto it = mp.rbegin(); it != mp.rend(); it++){
    for(auto i : it->second) dp[i] = max(rmax[r[i]], cmax[c[i]]);
    for(auto i : it->second){
      rmax[r[i]] = max(rmax[r[i]], dp[i] + 1);
      cmax[c[i]] = max(cmax[c[i]], dp[i] + 1);
    }
  }

  for(int i = 1; i <= n; i++) cout << dp[i] << endl;

  return 0;
}

posted:
last update: