Just Green Enough USACO 2021 February Contest

by

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.

See Also : USACO 2021 Challenges

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++).

SAMPLE INPUT:

3
57 120 87
200 100 150
2 141 135

SAMPLE OUTPUT:

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][0]) 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.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class JustGreenEnough2 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[][] pasture = new int[n][n];
        for (int y = 0; y < n; y++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            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);
            }
        }
        long answer = 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++;
                    }
                    answer += y2 - y1;
                }
            }
        }
        System.out.println(answer);
    }
}

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[1000][1000];
 
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[1000][1000];
 
ll solve() {
	ll ans = 0;
	vector<int> lst(N,N-1);
	vector<int> to_add[1000];
	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;
			else to_add[lst[k]].push_back(k);
		}
		int sum_comb = 0;
		vector<int> lef(N,-1), rig(N,-1);
		for (int j = N-1; j >= i; --j) {
			for (int k: to_add[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.

USACO 2021 February Contest

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

July Long Challenge 2021 Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment