We will start by proving that it is always possible for Bessie to type out a specific string. We can formally prove this by induction on the length of the string, but the core observation to solving this problem that also shows that it is always possible is to focus on the very last keystroke Bessie types.
If the last character in Bessie's favorite moo is an $\texttt{M}$, then Bessie will always type an $\texttt{M}$ as her final character. If the last character is an $\texttt{O}$ though, then Bessie will always type an $\texttt{O}$ as her final character. Furthermore, Bessie now wants to have typed the remaining characters incorrectly. If Bessie can intentionally type all the characters correctly, then she can also intentionally type all the characters incorrectly.
Subtask 1: To pass this subtask, it is sufficient to print $\texttt{YES}$ $T$ times.
Subtask 2: Since $N$ is small, we can brute-force all possible strings of length $N$ to find one that works.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static PrintWriter pw;
static StringTokenizer st;
static int mode;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
mode = Integer.parseInt(st.nextToken());
while(t-- > 0) solve();
pw.close();
}
public static void solve() throws Exception {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
pw.println("YES");
if(mode == 0) return;
for(int mask = 0; mask < (1 << n); mask++) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++) {
if((mask&(1<<i)) == 0) {
sb.append('M');
}
else {
for(int j = 0; j < i; j++) {
sb.setCharAt(j, (char)('M' + 'O' - sb.charAt(j)));
}
sb.append('O');
}
}
if(sb.toString().equals(s)) {
for(int i = 0; i < n; i++) {
if((mask&(1<<i)) == 0) pw.print('M');
else pw.print('O');
}
pw.println();
return;
}
}
throw new RuntimeException();
}
}
Subtask 3: We will generate the string from right to left, since we know the last character Bessie types must exactly match the last character of her favorite moo.
Since we know what characters Bessie will type in the future, we can count how many times Bessie presses $\texttt{O}$, which lets us know whether the current character should be typed correctly or incorrectly.
Therefore, it suffices to loop over the characters from right to left, keeping careful track of whether the current character should be typed correctly or incorrectly.
import java.io.*;
import java.math.*;
import java.util.*;
public class MainQuadratic {
static BufferedReader br;
static PrintWriter pw;
static StringTokenizer st;
static int mode;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
mode = Integer.parseInt(st.nextToken());
while(t-- > 0) solve();
pw.close();
}
public static void solve() throws Exception {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
StringBuilder sb = new StringBuilder();
for(int i = n-1; i >= 0; i--) {
int numflips = 0;
for(int a = 0; a < sb.length(); a++) if(sb.charAt(a) == 'O') numflips++;
if(numflips%2 == 0) sb.append(s.charAt(i));
else sb.append((char)('M'+'O'-s.charAt(i)));
}
sb.reverse();
pw.println("YES");
if(mode == 0) return;
pw.println(sb.toString());
}
}
Full solution: We don't need to track exactly how many flips happened, we only need to know if the number of flips was even or odd.
Nick Wu's Java code:
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static PrintWriter pw;
static StringTokenizer st;
static int mode;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
mode = Integer.parseInt(st.nextToken());
while(t-- > 0) solve();
pw.close();
}
public static void solve() throws Exception {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
StringBuilder sb = new StringBuilder();
boolean flipped = false;
for(int i = n-1; i >= 0; i--) {
if(!flipped) sb.append(s.charAt(i));
else sb.append((char)('M'+'O'-s.charAt(i)));
flipped ^= sb.charAt(sb.length()-1) == 'O';
}
sb.reverse();
pw.println("YES");
if(mode == 0) return;
pw.println(sb.toString());
}
}
Python code:
t, mode = (int(x) for x in input().split())
for _ in range(t):
n = int(input())
s = input()
print("YES")
if mode == 0: continue
flipped = False
ret = []
for x in s[::-1]:
if not flipped:
ret.append(x)
else:
ret.append(chr(ord('M')^ord('O')^ord(x)))
if ret[-1] == 'O':
flipped = not flipped
print("".join(ret[::-1]))
It is also possible to solve this problem "forwards". Note that when we append two characters in a row, those two characters will either always be equal or always be unequal no matter what happens to future characters. We can therefore observe that if $S_i$ and $S_{i+1}$ are both equal, then the only way that the keys corresponding to keystrokes $i$ and $i+1$ can be the same is if we type an $\texttt{M}$ for keystroke $i$, and symmetrically the only way that the keys corresponding to keystrokes $i$ and $i+1$ can be different is if we type an $\texttt{O}$ for keystroke $i$.
Finally, we observe that the last keystroke is always exactly the last character in $S$.
#include <iostream>
using namespace std;
int main() {
int t, mode;
cin >> t >> mode;
while(t--) {
int n;
string s;
cin >> n >> s;
cout << "YES\n";
if(mode == 0) continue;
for(int i = 0; i+1 < n; i++) {
if(s[i] == s[i+1]) cout << 'M';
else cout << 'O';
}
cout << s.back() << "\n";
}
}