USACO 2022 US Open Contest, Silver Problem 3. COW Operations

USACO 2022 US Open Contest, Silver Problem 3. COW Operations

Bessie finds a string ss of length at most 21052⋅105 containing only the three characters 'C', 'O', and 'W'. She wants to know if it's possible to turn this string into a single 'C' (her favorite letter) using the following operations:

1. Choose two adjacent equal letters and delete them.

2. Choose one letter and replace it with the other two letters in either order.

Finding the answer on the string itself isn't enough for Bessie, so she wants to know the answer for QQ (1Q21051≤Q≤2⋅105) substrings of ss.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains ss.The next line contains QQ.

The next QQ lines each contain two integers ll and rr (1lr|s|1≤l≤r≤|s|, where |s||s| denotes the length of ss).

OUTPUT FORMAT (print output to the terminal / stdout):

A string of length QQ, with the ii-th character being 'Y' if the ii-th substring can be reduced and 'N' otherwise.

SAMPLE INPUT:

COW
6
1 1
1 2
1 3
2 2
2 3
3 3


SAMPLE OUTPUT:

YNNNYN


The answer to the first query is yes because the first character of ss is already equal to 'C'.

The answer to the fifth query is yes because the substring OW from the second to the third character of ss can be converted into 'C' in two operations:

   OW
-> CWW
-> C


No other substring of this example string COW can be reduced to 'C'

SCORING:

• Test cases 2-4 satisfy |s|5000|s|≤5000 and Q5000Q≤5000.
• Test cases 5-11 satisfy no additional constraints.

Problem credits: Ray Bai

USACO 2022 US Open Contest, Silver Problem 3. COW Operations 题解(翰林国际教育提供，仅供参考)

[/hide]

(Analysis by Brian Dean)

Since NN and QQ are both large, we are motivated to look for way to characterize the answer to any query that can be evaluated very quickly.

Let CCOO, and WW be the counts of their respective characters in a query substring. We can evaluate these in constant time for any query using a difference of two pre-computed prefix sums -- e.g. the number of CC's in the query window iji…j is the cumulative number of CC's up to index jj minus the cumulative number up to index i1i−1 (as in Breed Counting).

We claim the answer to a query is YES if and only if O+WO+W has even parity and C+OC+O has odd parity (this is equivalent to saying O+WO+W is even and C+WC+W is odd). Note that any modification of our string has no impact on the parity of any sum of two of CCOO, and WW like O+WO+W.

The answer to a query is clearly NO if O+WO+W is odd, since in this case O+WO+W stays odd as an invariant, and we can never reduce it to zero. The answer is also clearly NO if C+OC+O (or C+WC+W) is even, since in this case we can't ever get down to a single CC without also having OO's or WW's. All that remains is showing that the answer is always YES when O+WO+W is even and C+OC+O is odd. There are several ways to do this. For example, starting with an arbitrary query, first get rid of all the WW's. Then reduce any run of more than one of the same character to just one of that character. This leaves a string of alternating CC's and OO's. You can transform OCOOCO into CC, so we can further reduce the string down to the point where it has at most one OO, and since O+WO+W must be even, it most actually have no OO's, and hence just one CC. Here is another way: first, note that you can always convert any adjacent two characters in a string into at most one. Either they’re the same and you can directly apply the first operation to remove them, or if they’re different, you can convert the first one into the not-present character followed by the second one, and then delete the two adjacent occurrences of the second character. This way any string can be reduced to a string with at most one character, and if O + W is even and C + O is odd the only such string is “C”.

Benjamin Qi's code:

#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<array<int, 3>> prefix_counts{{}};
string s;
cin >> s;
for (char c : s) {
prefix_counts.push_back(prefix_counts.back());
if (c == 'C') ++prefix_counts.back()[0];
if (c == 'O') ++prefix_counts.back()[1];
if (c == 'W') ++prefix_counts.back()[2];
}
int Q;
cin >> Q;
string ans;
while (Q--) {
int l, r;
cin >> l >> r;
array<int, 3> query_counts;
for (int i = 0; i < 3; ++i) {
query_counts[i] = prefix_counts[r][i] - prefix_counts[l - 1][i];
}
ans += ((query_counts[1] + query_counts[2]) % 2 == 0 &&
(query_counts[0] + query_counts[1]) % 2 == 1)
? 'Y'
: 'N';
}
cout << ans << "\n";
}


An elegant take on this solution is as follows. Since two adjacent equal characters can be removed and two adjacent different characters can be converted into single instance of the other character, we can identify each of the letters C, O, W with 1, 2, 3 and an empty string with 0. Then the XOR operation has exactly the same effect when combining two numbers, so for any substring we can calculate its XOR using prefix "XOR sums", then check whether this XOR is equal to 1.

Ray Bai's code:

import java.util.*;
import java.io.*;

public class COW
{
public static void main(String omkar[]) throws Exception
{
int[] map = new int[420];
map['C'] = 1;
map['O'] = 2;
map['W'] = 3;
int N = arr.length;
int[] prefix = new int[N+1];
for(int i=1; i <= N; i++)
prefix[i] = prefix[i-1]^map[arr[i-1]];
StringBuilder sb = new StringBuilder();
while(Q-->0)
{
int L = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
if((prefix[R]^prefix[L-1]) == 1)
sb.append("Y");
else
sb.append("N");
}
System.out.println(sb);
}
}


Interestingly, including GCC optimization pragmas allows an O(N2)O(N2) solution to pass. See this CodeForces blog for details.

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

unsigned char xo[200005];

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
s = "?" + s;
for (int i = 0; i < (int)size(s); ++i) {
if (s[i] == 'C') xo[i] = 1;
if (s[i] == 'O') xo[i] = 2;
if (s[i] == 'W') xo[i] = 3;
}
int Q;
cin >> Q;
string ans;
while (Q--) {
int l, r;
cin >> l >> r;
unsigned char acc = 0;
for (int j = l; j <= r; j++) {
acc ^= xo[j];
}
ans += acc == 1 ? 'Y' : 'N';
}
cout << ans << "\n";
}

[/hide]