USACO 2022 US Open Contest Silver Division - COW Operations

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main idea will be to rely on a few observations related to how the operations work in order to simplify the algorithm checked for finding whether we can reduce the string to a single \(C\) or not.

Let's analyze what kind of strings will be valid: of course, the single \(C\) is valid, and also any string which looks like OOC. Something like OW is also valid and we can already start seeing a pattern here. Basically, \(O+W\) has to be even and \(O+C\) has to be odd and these things can be checked with prefix sums.

Source code

The source code in C++ can be seen below.

#include <iostream>

using namespace std;

string s;
int n, q, pref[3][200002];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;
    n = s.size();
    for (int i = 1; i <= n; i++) {
        pref[0][i] = pref[0][i - 1] + (s[i - 1] == 'C');
        pref[1][i] = pref[1][i - 1] + (s[i - 1] == 'O');
        pref[2][i] = pref[2][i - 1] + (s[i - 1] == 'W');
    }

    cin >> q;

    for (; q; q--) {
        int L, R;
        cin >> L >> R;

        int c = pref[0][R] - pref[0][L - 1];
        int o = pref[1][R] - pref[1][L - 1];
        int w = pref[2][R] - pref[2][L - 1];

        if ((c + o) % 2 == 1 && (o + w) % 2 == 0)
            cout << "Y";
        else
            cout << "N";
    }

    return 0;
}