2025 February USACO Bronze Problems

Problem 1 (Reflection)

Farmer John has a square canvas represented by an N by N grid of cells (2≤N≤2000, N is even). He paints the canvas according to the following steps:

• First, he divides the canvas into four equal quadrants, separated by horizontal and vertical lines through the center of the canvas.
• Next, he paints a lovely painting in the top-right quadrant of the canvas. Each cell of the top-right quadrant will either be painted (represented by '#') or unpainted (represented by '.').
• Finally, since he is so proud of his painting, he reflects it across the previously mentioned horizontal and vertical lines into the other quadrants of the canvas.

For example, suppose N=8 and FJ painted the following painting in the top-right quadrant in step 2:

.#..
.#..
.##.
....

Then after reflecting across the horizontal and vertical lines into the other quadrants in step 3, the canvas would look as follows:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

However, while FJ was sleeping, Bessie broke into his barn and stole his precious canvas. She totally vandalized the canvas—removing some painted cells and adding more painted cells! Before FJ woke up, she returned the canvas to FJ.

FJ would like to modify his canvas so that it once again satisfies the reflective condition: that is, it is the result of reflecting the top-right quadrant into each of the other quadrants. Since he only has a limited number of resources, he would like to achieve this in as few operations as possible, where a single operation consists of either painting a cell or removing paint from a cell.

You are given the canvas after Bessie's vandalism, as well as a sequence of U (0≤U≤10^5) updates to the canvas, each toggling a single cell to '.' if it is '#', or vice versa. Before any updates, and after each update, output the minimum number of operations x FJ needs to perform so that the reflective condition is satisfied.

Solution

Problem 2 (Making Mexes)

You are given an array a of N non-negative integers a_1,a_2,…,a_N (1≤N≤2⋅10^5,0≤a_i≤N). In one operation, you can change any element of a to any non-negative integer.

The mex of an array is the minimum non-negative integer that it does not contain. For each i in the range 0 to N inclusive, compute the minimum number of operations you need in order to make the mex of a equal i.

Solution

Problem 3 (Printing Sequences)

Bessie is learning to code using a simple programming language. She first defines a valid program, then executes it to produce some output sequence.

Defining:

• A program is a nonempty sequence of statements.
• A statement is either of the form "PRINT c" where c is an integer, or "REP o", followed by a program, followed by "END," where o is an integer that is at least 1.

Executing:

• Executing a program executes its statements in sequence.
• Executing the statement "PRINT c" appends c to the output sequence.
• Executing a statement starting with "REP o" executes the inner program a total of o times in sequence.

An example of a program that Bessie knows how to write is as follows.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

The program outputs the sequence [1,2,2,1,2,2,1,2,2].

Bessie wants to output a sequence of N (1≤N≤100) positive integers. Elsie challenges her to use no more than K (1≤K≤3) "PRINT" statements. Note that Bessie can use as many "REP" statements as she wants. Also note that each positive integer in the sequence is no greater than K.

For each of T (1≤T≤100) independent test cases, determine whether Bessie can write a program that outputs some given sequence using at most K "PRINT" statements.

Solution