We first make three observations. Firstly, if the string has odd length, then it is clearly impossible to transform $S$ into an empty string, as we will always remove an even number of characters from $S$. Therefore, we assume that the string has even length. Secondly, it is easy to check if $M=1$, as the first half of $S$ must be exactly equal to the second half of $S$. Thirdly, we prove that $M \le 3$. Since the string has even length, it has an even number of C's, O's, and W's, so we can always transform $S$ into an empty string in 3 operations - the first operation removes all the C's, the second operation removes all the O's, and the third operation removes all the W's.
Therefore, the main difficulty in this problem reduces to checking whether $M=2$.
Subtask 1: Since $N$ is small, we can brute-force all $2^N$ ways of partitioning $N$ into two subsequences and checking whether each of those is square. Note that the provided code does pass the subtask 1 test case without handling the possibility that $M=3$, which is strong evidence that $M \le 2$.
#include <iostream>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
if(n%2) return void(cout << "-1\n");
if(s.substr(0, s.size()/2) == s.substr(s.size()/2)) {
cout << "1\n";
for(int i = 0; i < s.size(); i++) cout << 1 << " \n"[i+1==s.size()];
return;
}
for(int mask = 0; mask < (1<<s.size()); mask++) {
if(__builtin_popcount(mask)%2) continue;
string a = "";
string b = "";
for(int i = 0; i < s.size(); i++) (mask&(1<<i) ? a : b) += s[i];
if(a.substr(0, a.size()/2) == a.substr(a.size()/2) && b.substr(0, b.size()/2) == b.substr(b.size()/2)) {
cout << "2\n";
for(int i = 0; i < s.size(); i++) cout << (1+(1&(mask>>i))) << " \n"[i+1 == s.size()];
return;
}
}
}
int main() {
int t, _; cin >> t >> _;
while(t--) solve();
}
Subtask 2: Per the observations made at the beginning, it suffices in this test case to print the three-operation construction if $M > 1$.
#include <iostream>
using namespace std;
const string ALPHA = "COW";
void solve() {
int n;
string s;
cin >> n >> s;
if(n%2) return void(cout << "-1\n");
if(s.substr(0, s.size()/2) == s.substr(s.size()/2)) {
cout << "1\n";
for(int i = 0; i < s.size(); i++) cout << 1 << " \n"[i+1==s.size()];
return;
}
cout << "3\n";
for(int i = 0; i < s.size(); i++) cout << (1+ALPHA.find(s[i])) << " \n"[i+1==s.size()];
}
int main() {
int t, _; cin >> t >> _;
while(t--) solve();
}
Full solution: We will prove that $M \le 2$.
Note that if we take any pair of strings where either string is one of COW, OWC, and WCO, the length of the longest common substring of the pair is at least 2.
We can therefore construct a two-operation sequence as follows:
Aakash's and Melody's programs follow the above faithfully. Nick's program simply brute forces over all pairs of length-2 substrings and checks all of them for equality.
Aakash Gokhale's C++ code:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t, x; cin >> t >> x;
while (t--) {
int n; cin >> n;
string s; cin >> s;
if (n & 1) {
cout << -1 << endl;
continue;
}
vector<int> ans(n * 3, 1);
for (int i = 0; i < n / 2; i++) {
string l = s.substr(i * 3, 3);
string r = s.substr((i + n / 2) * 3, 3);
if (l != r) {
if (l.substr(0, 2) == r.substr(1, 2)) {
ans[i * 3 + 2] = 2;
ans[(i + n / 2) * 3] = 2;
} else if (l.substr(1, 2) == r.substr(0, 2)) {
ans[i * 3] = 2;
ans[(i + n / 2) * 3 + 2] = 2;
}
}
}
cout << *max_element(ans.begin(), ans.end()) << endl;
for (int i = 0; i < n * 3; i++) {
cout << ans[i] << " \n"[i == 3 * n - 1];
}
}
}
Melody Yu's Python code:
def check(s):
for i in range(len(s)//2):
if s[i]!=s[i + len(s)//2]:
return False
return True
t,k = list(map(int,input().split()))
for _ in range(t):
n = int(input())
s = input()
if n%2==1:
print(-1)
continue
if check(s):
print(1)
print(" ".join(["1"]*len(s)))
continue
ans=[1]*(n*3)
for i in range(n//2):
a=s[i*3:i*3+3]
b=s[(i+n//2)*3:(i+n//2)*3+3]
if a!=b:
if a[:2]==b[1:]:
ans[i*3+2]=ans[(i+n//2)*3]=2
else:
ans[i*3]=ans[(i+n//2)*3+2]=2
print(max(ans))
for i in range(n*3):
print(ans[i],end=" \n"[i==3*n-1])
Nick Wu's Java code:
import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
static BufferedReader br;
static PrintWriter pw;
static StringTokenizer st;
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());
while(t-- > 0) solve();
pw.close();
}
public static void solve() throws Exception {
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
if(s.length() % 2 != 0) {
pw.println(-1);
return;
}
if(s.substring(0, s.length()/2).equals(s.substring(s.length()/2))) {
pw.println(1);
for(int i = 0; i < s.length(); i++) {
if(i > 0) pw.print(' ');
pw.print(1);
}
pw.println();
return;
}
int[] ans = new int[s.length()];
int src = 0;
int dst = s.length()/2;
for(int i = 0; i < n/2; i++) {
if(s.substring(src, src+2).equals(s.substring(dst, dst+2))) {
ans[src++] = 1; ans[src++] = 1; ans[src++] = 2;
ans[dst++] = 1; ans[dst++] = 1; ans[dst++] = 2;
continue;
}
if(s.substring(src, src+2).equals(s.substring(dst+1, dst+3))) {
ans[src++] = 1; ans[src++] = 1; ans[src++] = 2;
ans[dst++] = 2; ans[dst++] = 1; ans[dst++] = 1;
continue;
}
if(s.substring(src+1, src+3).equals(s.substring(dst, dst+2))) {
ans[src++] = 2; ans[src++] = 1; ans[src++] = 1;
ans[dst++] = 1; ans[dst++] = 1; ans[dst++] = 2;
continue;
}
if(s.substring(src+1, src+3).equals(s.substring(dst+1, dst+3))) {
ans[src++] = 2; ans[src++] = 1; ans[src++] = 1;
ans[dst++] = 2; ans[dst++] = 1; ans[dst++] = 1;
continue;
}
throw new RuntimeException();
}
pw.println(2);
for(int i = 0; i < ans.length; i++) {
if(i > 0) pw.print(' ');
pw.print(ans[i]);
}
pw.println();
}
}