USACO 2021 February Contest Silver Division - Just Green Enough

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main observation in order to solve this problem is that instead of checking how many subgrids have a minimum value equal to \(X\), it is actually much easier to check how many subgrids have a minimum value which is greater or equal than \(X\), by considering values greater or equal than \(X\) as ones and the other ones as zeroes. Using this simplification, this subproblem reduces to counting how many subgrids are full of \(1\), which can be done in \(O(n^3)\) by fixing two rows and then using two pointers.

Based on this, all we have to do is to subtract from the number of grids which have a minimum of at least \(100\) those which have a minimum of at least \(101\).

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, mat[502][502], tv[502][502], sp[502][502];

ll solve(int nr)  // how many submatrices have min value at least equal to nr
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (mat[i][j] >= nr)
                tv[i][j] = 1;
            else
                tv[i][j] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (tv[i][j] == 1)
                sp[i][j] = sp[i - 1][j] + 1;  // number of consecutive ones on a column
            else
                sp[i][j] = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)  // fix two lines and do two pointers on each pair
        {
            int L = 1;
            int R = 1;
            while (L <= n) {
                if (L > R) R = L;
                while (R <= n && sp[j][R] >= (j - i + 1)) ++R;
                ans += (R - L);
                ++L;
            }
        }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    cout << solve(100) - solve(101) << '\n';  // how many submatrices have min value >= 100 - how many submatrices have min value >= 101
    return 0;
}