Monotonic Grid

Description: A case study of atcoder abc224_e using grid DP.
Publish Date: Calculating Date
Tags: [[cpp], [monotonic], [dynamic programming], [competitive programming]]

This is a question in a beginner contest, but the difficulty of it mustn't be underestimated. A simple description of it is that given a grid $M[i][j]$ with every element being non-negative, query the maximum steps we can take to traverse from each element if we only move from row-to-row or col-to-col and the next element must be greater than the current one.

A question like this has a few characteristics that enable us to use grid dynamic programming on it, which are

Given $M[i][j]=n$ , assuming $n$ is the current minimum of $M$ , then the max steps from $n$ to arbitrary points is $\max(R[i], C[j])$ , where $R[i]$ and $C[j]$ are max values of the max steps of all elements in row- $i$ and column- $j$ respectively.
By 1. and since $n$ is on row- $i$ and column- $j$ , then it is expected both $R[i]$ and $C[j]$ should account for $n$ 's existence, but we must also discuss when $n_1=n_2=\ldots=n_k$ .
The prerequisite of 1. and 2. is a partially-updated state space that assumes no element smaller than $n$ has been discussed yet; hence, constructing the arrays from the largest element is apt. Best of all, this reduces the problem into a monotonic sequence that can be solved in linear time (The double for-loops account for one $n$ .)

Here is the implementation.

#include <bits/stdc++.h>
#define DEBUG
using namespace std;
 
#define MAXVAL 200000
 
int h, w, n;
 
struct tup
{
    int i, j, p;
};
map<int, vector<tup>, greater<int>> inc_points;
 
// build the max value from biggest to smallest point
// every new inc_point is the current minimum
// iterate through with dynamic programming, updating row and col
int row_max[MAXVAL] = {}, col_max[MAXVAL] = {}, p_max[MAXVAL] = {};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> h >> w >> n;
 
    for (int p = 0; p < n; p++)
    {
        int i, j, a;
        cin >> i >> j >> a;
        inc_points[a].emplace_back(tup{i, j, p});
    }
 
    //
    for (auto const &p : inc_points)
    {
        for (auto const &coord : p.second)
        {
            // if i do this in the next for-loop, this will interfere with
            // other points with the same p. This is point 1.
            p_max[coord.p] = max(row_max[coord.i], col_max[coord.j]);
        }
        for (auto const &coord : p.second)
        {
            int nval = p_max[coord.p] + 1;
            // keep finding maximum among all the points with weight a.
            // Point 2.
            if (row_max[coord.i] < nval)
            {
                row_max[coord.i] = nval;
            }
            if (col_max[coord.j] < nval)
            {
                col_max[coord.j] = nval;
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        cout << p_max[i] << '\n';
    }
 
    return 0;
}

It's not quite intuitive, is it?