2025 January USACO Bronze Problems/Problem 1
Contents
Problem
Note
Note: The time limit for this problem is 4s, twice the default.
Problem
Bessie is using her nifty telescope to take photos of all the stars in the night sky. Her telescope can capture an N×N (1≤N≤1000) photo of the stars where each pixel is either a star or empty sky. Each star will be represented by exactly one pixel, and no two distinct stars share the same pixel.
Overnight, something strange happens to the stars in the sky. Every star either disappears or moves A pixels to the right, and B pixels downwards (0≤A,B≤N). If a star disappears or moves beyond the photo boundary, it no longer appears in the second photo.
Bessie took photos before and after the shifting positions, but after experimenting in Mootoshop, she accidentally superimposed one photo onto the other. Now, she can see white pixels where both photos were empty, gray pixels where stars existed in exactly one photo, and black pixels where there was a star in both photos. Bessie also remembers that no new stars moved into the frame of the second photo, so her first photo contains all of the stars in the night sky.
Given the final photo, determine the minimum possible number of stars in the sky before the shifting incident for T (1≤T≤1000) independent test cases. If no arrangement of stars can produce the given final photo, output −1.
Input Format
The first line of input contains T and T test cases will follow.
The first line of each test case will contain N A B.
Then follow N lines each representing one row of the superimposed photo. The ith row from the top is represented by a string c_i,1 c_i,2 … c_i,N, where each c_i,j∈{W,G,B}, representing the colors white, gray, and black respectively.
It is guaranteed that the sum of N^2 over all test cases will not exceed 10^7.
Output Format
For each test case, output the minimum number of stars that existed before the shifting, or −1 if impossible.
Sample Input
1 3 0 0 WWB BBB GGG
Sample Output
7
Scoring
Input 3: A=B=0
Inputs 4-7: A=1,B=0,N≤10
Inputs 8-9: A=1,B=0
Inputs 10-12: No additional constraints.
Solution
Note that black and white pixels immediately imply that certain locations do or do not contain stars, so let's deal with them first and the gray pixels later. More specifically,
- Place all stars required to satisfy black pixels.
- Check whether there are any unsatisfied white pixels.
- Add stars to satisfy gray pixels, without causing any white pixels to be unsatisfied.
The first two steps are straightforward, while the last can be accomplished using a greedy approach. While there is an unsatisfied gray pixel, consider the leftmost such gray pixel - then we must choose to place a star in at least one of two locations (at the gray pixel, or to the left of it). It is always optimal to place a star at the gray pixel due to the following reasons:
- The location to the left of that pixel might be outside of the grid or correspond to the white pixel, so it might not be available.
- A star at that gray pixel can potentially satisfy a gray pixel to the right, whereas a star to the left of that gray pixel will not.
This approach can be implemented with two left-to-right passes over each row of the input grid, the first for the black pixels and the second for the remaining pixels. The runtime per test is O(N^2).
