USACO 2026 Second Contest Bronze Division - It's Mooin' Time IV

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Typing \(\texttt{M}\) simply appends an \(\texttt{M}\) to the text; typing \(\texttt{O}\) first flips every character typed so far (\(\texttt{M}\,\leftrightarrow\,\texttt{O}\)) and then appends an \(\texttt{O}\). We must decide whether a given string \(S\) of length \(N\) can be produced, and when \(k=1\) also exhibit the keystroke sequence.

Each keystroke appends exactly one character, so producing \(S\) takes exactly \(N\) keystrokes; call them \(a_1 a_2 \dots a_N\). The crucial point is the \(\emph{direction of influence}\): a keystroke can only be altered by keystrokes typed \(\emph{after}\) it. The letter typed at position \(i\) is flipped once for every \(\texttt{O}\) among \(a_{i+1}, \dots, a_N\), since each such \(\texttt{O}\) flips the entire current text before appending itself. The last keystroke \(a_N\) is never flipped and appears in \(S\) unchanged.

So if \(o_i\) is the number of \(\texttt{O}\) in \(a_{i+1} \dots a_N\), then \(S_i\) equals \(a_i\) when \(o_i\) is even, and equals the flipped version of \(a_i\) when \(o_i\) is odd. This immediately suggests building the answer \(\textbf{from right to left}\): by the time we decide \(a_i\), every keystroke that could flip it (\(a_{i+1}, \dots, a_N\)) is already fixed, so \(a_i\) is forced: take \(S_i\) if the current parity is even, or its flip (\(\texttt{M} \leftrightarrow \texttt{O}\)) if the parity is odd.

Scan \(i\) from \(N-1\) down to \(0\), maintaining a counter \(o\) of \(\texttt{O}\) among the already-chosen keystrokes (only its parity matters):

for (int i = n-1; i >= 0; i--) {
  ans[i] = (o % 2 == 1 ? flip(s[i]) : s[i]);
  if (ans[i] == 'O') {
     o++;
  }
}

No decision can ever fail: whatever \(S_i\) and the current parity are, exactly one valid letter for \(a_i\) exists, because both \(\texttt{M}\) and \(\texttt{O}\) are always legal keystrokes. Hence the answer to the decision question is \(\texttt{YES}\) for \(\emph{every}\) input string, and the same right-to-left pass doubles as the construction for \(k=1\). For example, for \(S = \texttt{OOMOO}\) the pass produces \(\texttt{MOOMO}\), which matches the sample explanation: each suffix of the keystroke string, after the induced flips, yields the corresponding suffix of \(S\).

The greedy is correct because it is actually a \(\emph{forced}\) reconstruction: the parity argument shows \(a_i\) is uniquely determined by \(S_i\) and the suffix \(a_{i+1}\dots a_N\), so there is no branching and no possibility of a dead end.

One pass per test case gives \(O(N)\) time and \(O(N)\) memory, i.e. \(O(\sum N) \le 4 \cdot 10^5\) overall, easily fast enough even with \(T\) up to \(10^4\). When \(k = 0\), we skip the reconstruction entirely and simply print \(\texttt{YES}\).

Source code

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, k;
    cin >> t >> k;
    while (t--){
        if (k == 0){
            cout << "YES" << "\n";
        }
        else{
            int n;
            cin >> n;
            string s;
            cin >> s;
            vector<char> ans(n);
            int o = 0;
            for(int i = n - 1; i >= 0; i--){
                //odd number of o's
                //flip
                if (o % 2 == 1) { 
                    if (s[i] == 'O') {
                        ans[i] = 'M';
                    }
                    else
                        ans[i] = 'O';
                }
                else
                    ans[i] = s[i];

                if (ans[i] == 'O') {
                    o++;
                }
            }
            cout << "YES" << "\n";
            for (int i = 0; i < n; i++) {
                cout << ans[i];
            }
            cout << "\n";
        }

    }
}