# Just Green Enough USACO 2021 February Contest

Page Contents

## Just Green Enough USACO Solution

Farmer John’s pasture can be regarded as an N×NN×N grid (1≤N≤5001≤N≤500) of square “cells” of grass (picture a huge chessboard). Due to soil variability, the grass in some cells is greener than in others. Each cell (i,j)(i,j) is described by an integer level of green-ness G(i,j)G(i,j), ranging from 1…2001…200.

Farmer John wants to take a photograph of a rectangular sub-grid of his pasture. He wants to be sure the sub-grid looks sufficiently green, but not ridiculously green, so he decides to photograph a sub-grid for which the minimum value of GG is exactly 100. Please help him determine how many different photographs he could possibly take. A sub-grid can be as large as the entire pasture or as small as a single grid cell (there are N2(N+1)2/4N2(N+1)2/4 different sub-grids in total — note that this number might be too large to store in a standard 32-bit integer, so you might need to use 64-bit integer data types like a “long long” in C++).

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN. The next NN lines each contain NN integers and collectively describe the G(i,j)G(i,j) values for the N×NN×N pasture.

#### OUTPUT FORMAT (print output to the terminal / stdout):

Please print the number of distinct photos Farmer John can take — that is, the number of rectangular sub-grids for which the minimum level of green-ness is exactly 100.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).

```3
57 120 87
200 100 150
2 141 135
```

```8
```

#### SCORING:

• Test cases 1-5 satisfy N≤200N≤200.
• Test cases 6-10 satisfy no additional constraints.

Problem credits: Brian Dean

The first step is to use complementary counting. The number of rectangular sub-grids with minimum equal to 100100 is equal to the number of rectangular sub-grids with minimum at least 100100 minus the number of rectangular sub-grids with minimum at least 101101.

To count the number of rectangular sub-grids with minimum at least mm, create an N×NN×N boolean array okok such that ok[i][j]=1ok[i][j]=1 if G[i][j]≥mG[i][j]≥m. We want to count the number of rectangular sub-grids in okok that consist solely of ones.

If okok was an N×1N×1 rectangle rather than an N×NN×N rectangle, the following loop would suffice to compute the answer:

```int run = 0;
for (int i = 0; i < N; ++i) {
if (ok[i]) ans += ++run;
else run = 0;
}
```

Each run of ll consecutive ones contributes l(l+1)2l(l+1)2 to the answer.

Define all_onesi,j[k]all_onesi,j[k] to be true if all of the cells from (i,k)(i,k) to (j,k)(j,k) contain ones, and false otherwise. It suffices to iterate over (i,j)(i,j), compute all_onesi,j[k]all_onesi,j[k] for all 0≤k<N0≤k<N, and then apply the 1D solution to all_onesall_ones. This takes O(N4)O(N4) time since there are O(N3)O(N3) triples (i,j,k)(i,j,k) and for each one, we do O(N)O(N) work to compute all_onesi,j[k]all_onesi,j[k].

To speed this up to O(N3)O(N3) time, we can use 1D prefix sums to compute all_onesi,j[k]all_onesi,j[k] in O(1)O(1) time.

Danny Mittal’s code:

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class JustGreenEnough2 {

public static void main(String[] args) throws IOException {
int[][] pasture = new int[n][n];
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
pasture[y][x] = Integer.parseInt(tokenizer.nextToken());
}
}
int[][] sumsBelow = new int[n][n + 1];
int[][] sumsAtMost = new int[n][n + 1];
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
sumsBelow[y][x + 1] = sumsBelow[y][x] + (pasture[y][x] < 100 ? 1 : 0);
sumsAtMost[y][x + 1] = sumsAtMost[y][x] + (pasture[y][x] <= 100 ? 1 : 0);
}
}
for (int x1 = 0; x1 < n; x1++) {
for (int x2 = x1 + 1; x2 <= n; x2++) {
int y1 = -1;
int y2 = -1;
for (int y0 = 0; y0 < n; y0++) {
while (y1 < n && (y1 < y0 || sumsAtMost[y1][x2] - sumsAtMost[y1][x1] == 0)) {
y1++;
}
while (y2 < n && (y2 < y0 || sumsBelow[y2][x2] - sumsBelow[y2][x1] == 0)) {
y2++;
}
}
}
}
}
}
```

Alternatively, note that all_onesi,j[k]=all_onesi,j−1[k]&ok[j][k]all_onesi,j[k]=all_onesi,j−1[k]&ok[j][k]. So let’s fix ii and computeall_onesi,i,all_onesi,i+1,…,all_onesi,N−1all_onesi,i,all_onesi,i+1,…,all_onesi,N−1in order.

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

using ll = long long;

int N;
bool ok;

ll solve() {
ll ans = 0;
for (int i = 0; i < N; ++i) {
vector<bool> all_ones(N,true);
for (int j = i; j < N; ++j) {
// add rectangles with upper row i and lower row j
int run = 0;
for (int k = 0; k < N; ++k) {
// all_ones_{i,j-1}[k] -> all_ones_{i,j}[k]
all_ones[k] = all_ones[k]&ok[j][k];
if (all_ones[k]) ans += ++run; // update answer
else run = 0;
}
}
}
return ans;
}

int main() {
cin >> N;
vector<vector<int>> pasture(N,vector<int>(N));
for (vector<int>& a: pasture)
for (int& b: a) cin >> b;

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
ok[i][j] = pasture[i][j] >= 100;
ll ans = solve();

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
ok[i][j] = pasture[i][j] > 100;
ans -= solve();

cout << ans << "\n";
}
```

It was possible (but not necessary) to solve this problem in O(N2)O(N2) time. In the code below, for a fixed ii, I iterate over all jj in decreasing (rather than increasing order as the solution above does) and maintain the sum of the contributions of all runs in all_onesi,jall_onesi,j in sum_combsum_comb. When jj decreases by one, I update sum_combsum_comb accordingly for each kk such that all_onesi,j+1[k]=0all_onesi,j+1[k]=0 and all_onesi,j[k]=1all_onesi,j[k]=1.

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

using ll = long long;

int N;
bool ok;

ll solve() {
ll ans = 0;
vector<int> lst(N,N-1);
for (int i = N-1; i >= 0; --i) {
for (int j = i; j < N; ++j) to_add[j].clear();
for (int k = 0; k < N; ++k) {
if (ok[i][k] == 0) lst[k] = i-1;
}
int sum_comb = 0;
vector<int> lef(N,-1), rig(N,-1);
for (int j = N-1; j >= i; --j) {
// all_ones_{i,j+1}[k] = 0, all_ones_{i,j}[k] = 1
int l = k, r = k;
auto c2 = [](int x) { return (x+1)*(x+2)/2; };
if (k && lef[k-1] != -1) {
l = lef[k-1];
sum_comb -= c2(k-1-l);
}
if (k+1 < N && rig[k+1] != -1) {
r = rig[k+1];
sum_comb -= c2(r-k-1);
}
lef[r] = l, rig[l] = r;
sum_comb += c2(r-l);
}
ans += sum_comb;
}
}
return ans;
}

int main() {
cin >> N;
vector<vector<int>> pasture(N,vector<int>(N));
for (vector<int>& a: pasture)
for (int& b: a) cin >> b;

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
ok[i][j] = pasture[i][j] >= 100;
ll ans = solve();

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
ok[i][j] = pasture[i][j] > 100;
ans -= solve();

cout << ans << "\n";
}
```

For an additional challenge, try Maximum Building II.