2025 January USACO Bronze Problems
Problem 1 (Astral Superposition)
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.
Problem 2 (It's Mooin' Time II)
Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest."
Elsie still doesn't understand, so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as an array of N (1≤N≤10^6) integers a_1,a_2,…,a_N (1≤a_i≤N). Farmer John defines a moo as an array of three integers where the second integer equals the third but not the first. A moo is said to occur in the contest if it is possible to remove integers from the array until only the moo remains.
As Bessie allegedly "mooed all over the contest", help Elsie count the number of distinct moos that occur in the contest! Two moos are distinct if they do not consist of the same integers in the same order.
Problem 3 (Cow Checkups)
Farmer John's N (1≤N≤7500) cows are standing in a line, with cow 1 at the front of the line and cow N at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from 1 to N. The i'th cow from the front of the line is of species a_i (1≤a_i≤N).
FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the i'th cow in the line, only if it is of species b_i (1≤b_i≤N).
FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once.
- Select two integers l and r such that 1≤l≤r≤N. Reverse the order of the cows that are between the l-th cow and the r-th cow in the line, inclusive.
FJ wants to measure how effective this approach is. For each c=0…N, help FJ find the number of distinct operations (l,r) that result in exactly c cows being checked. Two operations (l_1,r_1) and (l_2,r_2) are different if l_1≠l_2 or r_1≠r_2.
