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.
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
- Clockwise Fence USACO 2021 February Contest
- Just Green Enough USACO 2021 February Contest
- Year of the Cow USACO 2021 February Contest
- Comfortable Cows USACO 2021 February Contest
- Count the Cows USACO 2021 February Contest
- Modern Art 3 USACO 2021 February Contest
- Stone Game USACO 2021 February Contest
- Counting Graphs USACO 2021 February Contest
- Minimizing Edges USACO 2021 February Contest
- No Time to Dry USACO 2021 February Contest
- Maze Tac Toe USACO 2021 US
- Balanced Subsets USACO 2021 US
- Routing Schemes USACO 2021 US
- United Cows of Farmer John USACO 2021 US
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
Codechef Long Challenge Solutions
July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP