Blog/USACO Photoshoot
Yash Singh

# USACO Photoshoot Bronze US Open 2022 Problem 1

In this blog post I'll go over the USACO Photoshoot Bronze US Open 2022 Problem 1 using other resources and solutions.

## Statement

According to the problem statement, the input is a string that consists of two characters, G and H, both representing two separate breeds of cows. The farmer wants to arrange the string in such a manner that as many as possible of the even positions contain a G. The commands he gives to the cows is a number $k$ where the first $k$ cows have to reverse themselves in order.

## Solution

First of all, we can group the cows into pairs because reversals might change a GH to an HG but the two cows will still be in a pair. Next, let's represent all GH's as a 1 and all HG's as a 0. Also represent all GGs and HHs as _s. For example, the following input: GG|HG|GH will become _01. We want to maximize the amount of HG or 0s. Whenever we reverse any prefix, we are flipping the 1s to 0s and 0s to 1s and reversing the order. For example, an operation on a prefix of 5 to the following:

For clarity, let's drop all _s as they do not have any effect on the end result. Now we have the following: 1101011. Given any string like this, we can come up with an all 0 solution to it, through the following:

To get to this point, it took us 5 operations. Notice that in each operation we are "equalizing" the first two segments of opposite bits. For example, when we have a 110 we are turning it into a 000 so we can flip the first three as a whole. We continue this process till all the segments are equalized with one operation for each segment. Let's try another input 010100110.

Notice how even though we could divide the 010100110 into 7 segments, we took 6 operations since the last segment consisted of 0 which could be neglected. This is an edge case we need to account for in our implementation.

## Implementation

Let's go through an implementation in C++:

## Lessons Learnt

A few lessons learnt through this problem is that you should try to break down and make the input simpler, because through that patterns may emerge that can ultimately lead to the solution.