Contest Python: USACO Bronze › Unit 8 — Prefix Sums
Exercises: Unit 8 — Prefix Sums
Each exercise is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper). Build a 1D prefix array or 2D prefix grid before answering the requested ranges. Use the extra zero entry, row, or column carefully, especially when an inclusive range reaches the final value or the bottom-right grid cell.
Write your program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Arena Range Totals
The first line contains N Q, the second line contains N integer point values, and each of the next Q lines contains zero-indexed inclusive endpoints l r; build one prefix-sum array and return the sum from l through r for every query, in query order with one integer per line. In the sample, the final query reaches index N - 1, and its last value changes that answer from 13 to 22.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= point value <= 1000000000.
0 <= l <= r < N, and re-adding every queried range is too slow.
Sample Input
7 3
4 1 3 2 8 5 9
0 0
1 4
4 6Sample Output
4
14
22How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 2: Lit Tiles in a Range
The first line contains N Q, the second line contains N values that are each 0 for an unlit tile or 1 for a lit tile, and each of the next Q lines contains zero-indexed inclusive endpoints l r; build prefix counts and return the number of lit tiles in every queried range, in query order with one integer per line. In the sample, the final one-cell contribution at index N - 1 makes the last answer 2 instead of 1.
Constraints. 1 <= N, Q <= 200000.
Every tile value is 0 or 1.
0 <= l <= r < N, and scanning every queried range is too slow.
Sample Input
8 3
1 0 1 1 0 0 1 1
0 0
2 5
6 7Sample Output
1
2
2How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 3: Target-Sum Reports
The first line contains N Q T, the second line contains N integer measurements, and each of the next Q lines contains zero-indexed inclusive endpoints l r; build one cumulative-sum array, test each queried range total against target T, and return the number of queries whose total is exactly T. In the sample, only the final query matches 15, and the value at index N - 1 is necessary for that match.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= measurement, T <= 1000000000.
0 <= l <= r < N, and re-summing every queried range is too slow.
Sample Input
7 4 15
2 3 5 1 4 6 9
0 2
1 4
3 5
5 6Sample Output
1How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.
Exercise 4: Strongest Reported Range
The first line contains N Q, the second line contains N integer signal values, and each of the next Q lines contains zero-indexed inclusive endpoints l r; use cumulative sums to find each reported range total and return the greatest of those Q totals. In the sample, the final reported range ends at index N - 1, and the last signal makes its total 12, the unique greatest total.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= signal value <= 1000000000.
0 <= l <= r < N, and scanning every reported range is too slow.
Sample Input
7 3
5 -2 4 1 -3 2 12
0 2
1 5
3 6Sample Output
12How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 5: Map Rectangle Totals
The first line contains R C Q, the next R lines contain a grid of C integers, and each of the next Q lines contains zero-indexed inclusive corners r1 c1 r2 c2 with (r1, c1) at the top left and (r2, c2) at the bottom right; build one 2D prefix grid and return the sum in every queried rectangle, in query order with one integer per line. In the sample, the last two queries reach the last row and column, and the final one-cell query proves that the bottom-right value 20 is included.
Constraints. 1 <= R, C <= 1000, 1 <= Q <= 200000, and R * C <= 1000000.
-1000000000 <= grid value <= 1000000000.
0 <= r1 <= r2 < R and 0 <= c1 <= c2 < C; scanning each rectangle is too slow.
Sample Input
3 4 3
1 2 3 4
5 6 7 8
9 10 11 20
0 0 1 1
1 2 2 3
2 3 2 3Sample Output
14
46
20How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 6: Beacons in a Region
The first line contains R C Q, the next R lines form a grid whose # cells contain beacons and whose . cells are empty, and each of the next Q lines contains zero-indexed inclusive corners r1 c1 r2 c2; build a 2D prefix grid of beacon counts and return the number of beacons in every queried rectangle, in query order with one integer per line. In the sample, the final query is the bottom-right cell alone, so omitting the last row or column changes its answer from 1 to 0.
Constraints. 1 <= R, C <= 1000, 1 <= Q <= 200000, and R * C <= 1000000.
Every grid row has exactly C characters, each either # or ..
0 <= r1 <= r2 < R and 0 <= c1 <= c2 < C; scanning each rectangle is too slow.
Sample Input
4 5 3
#....
..#..
.....
....#
0 0 3 4
1 1 2 4
3 4 3 4Sample Output
3
1
1How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 7: Most Valuable Survey Zone
The first line contains R C Q, the next R lines contain a grid of C integer resource values, and each of the next Q lines contains zero-indexed inclusive corners r1 c1 r2 c2; use a 2D prefix grid to total every surveyed rectangle and return the greatest of the Q totals. In the sample, the final survey reaches the last row and column, and the bottom-right value 20 makes its total 24, the unique greatest total.
Constraints. 1 <= R, C <= 1000, 1 <= Q <= 200000, and R * C <= 1000000.
-1000000000 <= resource value <= 1000000000.
0 <= r1 <= r2 < R and 0 <= c1 <= c2 < C; scanning each rectangle is too slow.
Sample Input
3 3 3
2 1 1
1 2 1
1 1 20
0 0 0 2
0 0 1 1
1 1 2 2Sample Output
24How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.
Exercise 8: Best Bounded Candidate Window
The first line contains N Q K, the second line contains N integer scores, and each of the next Q lines contains zero-indexed inclusive endpoints l r for one candidate window; ignore candidates containing more than K values, use a prefix-sum array to total every remaining candidate in O(1), and return the greatest remaining total. At least one candidate is eligible. In the sample, the fourth candidate ties the best total at 4, then the final eligible candidate ends at index N - 1 and raises the answer to 15.
Constraints. 1 <= N, Q <= 200000 and 1 <= K <= N.
-1000000000 <= score <= 1000000000.
0 <= l <= r < N, and re-adding every eligible candidate is too slow.
Sample Input
8 5 3
4 -3 2 1 5 -2 6 9
0 2
3 5
4 7
5 6
6 7Sample Output
15How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 9: Longest Low-Total Streak
The first line contains N B, and the second line contains N signed integer score changes; build a prefix-sum array, test every contiguous window, and return the greatest number of values in a window whose total is at most limit B. Because values may be negative, do not stop checking longer windows after one total exceeds B; enumerate every start and end position and compute each total as pre[r + 1] - pre[l] in O(1). In the sample, the unique longest valid window is the final seven values, so omitting the last value changes the answer from 7 to 3. If no non-empty window has a total at most B, return 0.
Constraints. 1 <= N <= 4000 and -1000000000000000000 <= B <= 1000000000000000000.
-1000000000 <= score change <= 1000000000.
An O(N squared) search with O(1) prefix-sum range checks is allowed; an O(N cubed) search that re-adds every range is too slow.
Sample Input
8 5
6 6 6 6 6 6 -10 -15Sample Output
7How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.