USACO 2026 First Contest Bronze Division - COW Splits#

Problem link: here

Problem Solution#

We work with a string of length $3n$ made from the letters C, O, and W, grouped as $n$ blocks of length $3$. If $n$ is odd then the whole pairing idea breaks immediately — you need to match each block with another one, and with an odd number you will always have one unmatched, so the answer is just $-1$. In the original problem, if $n$ is even and $k = 1$, there is a simple $m = 3$ solution where you just take all C first, then all O, then all W (or the reverse if $k = 0$), and you’re done.

The more interesting case is $k = 0$ and $n$ even, which is what the code handles. The idea is to split the big string into $n$ blocks of length $3$, i.e. strings like COW, OWC, or WCO. Then we pair block $i$ with block $i + n/2$ for all $i$ in the first half. For each such pair of blocks, we check if they are identical; if they are, they can be handled in one operation. If they differ, then you can still always do it in two operations by matching overlapping 2-character pieces. Concretely, if the left block is $l$ and the right block is $r$:

if $l[0..1] = r[1..2]$, then we take the last character of $l$ in the second operation and the first character of $r$ in the second operation,
if $l[1..2] = r[0..1]$, then we take the first character of $l$ in the second operation and the last character of $r$ in the second operation.

So globally the answer is either $1$ or $2$ depending on whether any pair requires the second operation, and the output array marks which positions are used in which round.

Source code#

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    if (n % 2 == 1) {
        cout << -1 << '\n';
        return;
    }

    vector<int> ans(n * 3, 1);

    for (int i = 0; i < n / 2; i++) {
        int leftStart = i * 3;
        int rightStart = (i + n / 2) * 3;

        bool sameBlock = true;
        for (int k = 0; k < 3; k++) {
            if (s[leftStart + k] != s[rightStart + k]) {
                sameBlock = false;
                break;
            }
        }

        if (!sameBlock) {
            bool leftFirstTwo_eq_rightLastTwo = (s[leftStart] == s[rightStart + 1]) && (s[leftStart + 1] == s[rightStart + 2]);
            bool leftLastTwo_eq_rightFirstTwo = (s[leftStart + 1] == s[rightStart]) && (s[leftStart + 2] == s[rightStart + 1]);

            if (leftFirstTwo_eq_rightLastTwo) {
                ans[leftStart + 2] = 2;
                ans[rightStart] = 2;
            } 
            else if (leftLastTwo_eq_rightFirstTwo) {
                ans[leftStart] = 2;
                ans[rightStart + 2]= 2;
            }
        }
    }

    cout << *max_element(ans.begin(), ans.end()) << '\n';
    for (int i = 0; i < n * 3; i++) {
        cout << ans[i];
        if (i + 1 < n * 3) {
            cout << " ";
        }
        else {
            cout << '\n';
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t, x;
    cin >> t >> x; 

    while (t--) {
        solve();
    }
    return 0;
}