USACO 2022 US Open Contest, Bronze Problem 1. Photoshoot

USACO 2022 US Open Contest, Bronze Problem 1. Photoshoot

Farmer John, desperate to win the award for best cow photographer at the county fair, is trying to take the perfect photograph of his NN cows (2≤N≤2⋅1052≤N≤2⋅105, NN even).

Farmer John owns cows of two potential breeds: Guernseys and Holsteins. To make his photo as aesthetic as possible, he wants to line up his cows so that as many Guernseys are in even-numbered positions in the line as possible (the first position in the line is an odd position, the next is an even position, and so on). Due to his lack of strong communication with his cows, the only way he can achieve his goal is by asking even length "prefixes" of his cows to reverse themselves (a prefix consists of the range of cows from the first cow up to the jjth cow for some position jj).

Please count the minimum number of reversals required for Farmer John to achieve his goal.

 

 

 

SAMPLE INPUT:

14
GGGHGHHGHHHGHG

SAMPLE OUTPUT:

1

In this example, it suffices to reverse the prefix consisting of the first six cows.

 

   GGGHGHHGHHHGHG (Before)
-> HGHGGGHGHHHGHG (After)

Before the reversal, four Guernseys were at even positions. After the reversal, six Guernseys are at even positions. It is impossible for there to be more than six Guernseys at even positions.

Problem credits: Aryansh Shrivastava

USACO 2022 US Open Contest, Bronze Problem 1. Photoshoot 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Consider replacing every length-two substring of the input string with

 

• . if the two characters are equal
• A if the substring is GH
• B if the substring is HG

For example, the sample input would be transformed as follows:

 

   GG|GH|GH|HG|HH|HG|HG
-> .BBA.AA

Reversing an even-length prefix in the original string corresponds to reversing and then flipping a prefix in the new string (where a flip converts As to Bs, Bs to As, and leaves .s unchanged). Let's call a combination of a reversal and a flip an operation. The goal is to maximize the number of As in the new string with the minimum number of operations.

Now we can use the following observations to simplify the new string. First, drop all occurrences of .:

 

   .BBA.AA
-> BBAAA

Second, condense all consecutive occurrences of the same character into a single occurrence since we can always choose to reverse them as a block.

 

   BBAAA
-> BA

Third, drop the last character of the string if it is an A.

 

   BA
-> B

To recap, we are left with the string s=simplify(.BBA.AA)=Bs=simplify(.BBA.AA)=B. Note that regardless of the input string, ss will always be an alternating sequence of As and Bs that ends with B if it is nonempty.

The final observation is that regardless of how we choose a prefix of ss to operate on, length(simplify(operate(s)))≥length(s)−1length(simplify(operate(s)))≥length(s)−1. For example, when s=ABABs=ABAB we can show that regardless of what prefix of ss we choose to operate on, the simplified string after the operation will have length at least 33:

 

   ABAB
-> BBAB (operate on prefix of length 1)
-> BAB (simplify)

 

   ABAB
-> ABAB (operate on prefix of length 2)
-> ABAB (simplify)

Also, it is always possible to choose a prefix to operate on such that length(simplify(operate(s)))=length(s)−1length(simplify(operate(s)))=length(s)−1 when length(s)>0length(s)>0; just choose to operate on the length-1 prefix of ss.

So the answer is length(s)length(s), which may be computed in O(N)O(N) time.

Danny Mittal's code:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Photoshoot3 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        char[] ordering = in.readLine().toCharArray();
        int answer = 0;
        for (int j = n - 2; j >= 0; j -= 2) {
            if (ordering[j] != ordering[j + 1] && (ordering[j] == 'G') == (answer % 2 == 0)) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

Jichao Qian's code:

 

#include <stdio.h>
#include <stdint.h>
 
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main()
{
    int N;
    scanf("%d", &N);
 
    char str[200002];
    scanf("%s", str + 1);
 
    int ret = 0;
    for (int idx = N; idx >= 2; idx -= 2)
    {
        if (str[idx] == str[idx-1])
            continue;
 
        if (str[idx] == 'G' && ret % 2 == 1)
            ++ret;
 
        if (str[idx] == 'H' && ret % 2 == 0)
            ++ret;
    }
 
    printf("%d\n", ret);
 
    return 0;
}

Benjamin Qi's code:

 

N = int(input())
s = input()
 
lst = '.'
ans = 0
 
for i in range(0,N,2):
	if s[i] != s[i+1]:
		if s[i] != lst:
			ans += 1
			lst = s[i]
 
if lst == 'H':
	ans -= 1
 
print(ans)

Exercise: We did not formally prove all of our observations. Verify that the quantity computed by each solution does not decrease by more than one after any prefix reversal of the input string.

Note: This problem is vaguely similar to Mad Scientist.
[/hide]