Solving “Appleby Contest '19 P5 - Matrix Operation” on DMOJ

Problem

Problem link: https://dmoj.ca/problem/ac19p5

Problem type: Dynamic programming

This problem asks us to implement a program that outputs the longest strictly (i.e. can’t be equal) increasing path in an N x N matrix consisting of integers.

Solution

This problem can be solved by using top-down dynamic programming. The idea is to use recursion (dividing a problem into sub-problems) with memoization (storing, then re-using calculated value for the sub-problems).

Note that DP stands for dynamic programming.

the array a represents the matrix (input) values and dp represents the DP table values

We then have to define a DP state (DP array/table representation) and a DP transition (how a problem relates to its sub-problems).

In this problem, the DP state is as follows.

Let dp[i][j] represent the longest strictly increasing path in the matrix that begins at a[i][j]. In this situation, dp is a two-dimensional array.

a[i][j] represents the value at row i and column j in the matrix given in the input.

A base case in dynamic programming represents specific DP states that can be pre-calculated without the input or any sub-problems having an impact.

In this case, the base case is as follows.

dp[i][j] = 0 if a[i][j] has no neighbours that are strictly greater than itself.

There are four neighbours to any value a[i][j] that is not in the corner, which are a[i + 1][j], a[i - 1][j], a[i][j + 1], and a[i][j - 1].

Now, let’s think of how we can relate the DP state to other sub-problems. We know that a path must be strictly increasing, so we can only consider neighbours of a[i][j] if they are greater than a[i][j].

Once we determine which neighbours are valid, we have to determine which neighbour to choose as part of the longest path. This is where we can use recursion. Our DP transition is as follows.

dp[i][j] = maximum dp value of all valid neighbours + 1

There is also one more case we have to handle, which is if dp[i][j] does not have four neighbours that we can fix by one-indexing the matrix and dp arrays and checking whether the neighbours have a value that is not equal to 0.

We will also need to run our recursive function once from every element of the matrix.

Now that we have determined our DP state, base case, and transition, we can test our strategy on the sample case.

Sample Case

Input

1
2
3
4

3
9 8 4
7 2 3
6 1 5

Output

1

5

We can test our strategy on this case.

Our matrix is as follows.

The bolded numbers on the top row and leftmost column represent the i and j values

We start by initializing our dp array to -1. (memset in C++)

f(i, j) represents the recursive function with start value i and j.

We start by calling f(1, 1)

Call: f(1, 1), value = 9

Since this value has no strictly greater neighbours (its neighbours are 8 and 7), we return 0. The dp array does not change.

Returned 0.

Call: f(1, 2), value = 8

There is one neighbour that is strictly greater than the current value, which is i = 1, j = 1 with a value of 9. Since the value at i = 1, j = 1 has already been computed, we return dp[1][1] + 1, which is 1.

Returned 1.

f(i, j) is then called for each value for i and j from 1 to N (matrix size), and the largest value is outputted. At the end of all the calls, the dp array is as follows.

We can now see that the longest strictly increasing path in the matrix has a length of 5 and begins at i = 3, j = 2

Now that we have created a strategy for solving the problem and verified the strategy with our sample case, we can write the code for this problem.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <bits/stdc++.h>

#define el "\n"
#define ll long long

using namespace std;

const int MM = 1502;

int dp[MM][MM], n;
ll a[MM][MM];


int f(int r, int c) {
    if (dp[r][c] != -1) return dp[r][c]; // If dp value has already been calculated, return it (memoization)

    int re = 0;
    if (a[r - 1][c] != 0 && a[r - 1][c] > a[r][c]) re = max(re, 1 + f(r - 1, c));
    if (a[r + 1][c] != 0 && a[r + 1][c] > a[r][c]) re = max(re, 1 + f(r + 1, c));
    if (a[r][c - 1] != 0 && a[r][c - 1] > a[r][c]) re = max(re, 1 + f(r, c - 1));
    if (a[r][c + 1] != 0 && a[r][c + 1] > a[r][c]) re = max(re, 1 + f(r, c + 1));

    return dp[r][c] = re;
}


int main() {
    cin.tie(0); ios::sync_with_stdio(0); // Fast input/output
    
    cin >> n;

    int ans = 0;

    memset(dp, -1, sizeof(dp)); // Initialize dp array to -1

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max(ans, f(i, j));
        }
    }

    cout << ans << el;
}