PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You are given binary strings S and T of the same length.
In one move, you can:
- Choose an index i and swap S_i with T_i, or
- Choose indices i, j and swap S_i with S_j and T_i with T_j.
Decide if it’s possible to make S and T both palindromes simultaneously using these operations.
EXPLANATION:
Let P_i = (S_i, T_i) denote the pair of characters at index i.
Observe that:
- The first operation allows us to swap the order of elements in the pair P_i.
- The second operation allows to swap two different pairs P_i and P_j themselves.
In particular, note that the pairs can’t really be modified much at all: they can really only be moved around.
On the other hand, given that we can swap any pair of the P_i, we are able to freely rearrange them in whatever order we like, which is quite powerful.
Each P_i can take one of three possible values: (0, 0), (1, 1), or (0, 1).
Note that (1, 0) is also possible, but it is equivalent to (0, 1) since we are allowed to swap elements within a pair, so for now we can pretend that all such pairs are (0, 1).
Now, our aim is to make both S and T palindromes.
This means S_i = S_{N+1-i} and T_i = T_{N+1-i} should hold for every i.
So, let’s look at the pairs P_i and P_{N+1-i}.
- Suppose P_i = (0, 0). Then, P_{N+1-i} must also be (0, 0), since if it’s (1, 1) or (0, 1) then either S or T will have a mismatch.
- Similarly, if P_i = (1, 1), then P_{N+1-i} = (1, 1) must hold.
- And, for the exact same reason, if P_i = (0, 1) then P_{N+1-i} = (0, 1) as well.
In essence, all we really need to do is “pair up” equal pairs of elements.
Of course, this means each of the types should occur an even number of times, since they’re being paired up.
The only exception is when N is odd, when one type can occur an odd number of times and must be placed as the middle element.
Since the second operation allows us to freely rearrange the order of pairs, if each type (except one when N is odd) occurs an even number of times then it’s definitely possible to make both strings palindromes.
This gives us a pretty simple final check:
- Let c_{(0, 0)} be the number of (0, 0) pairs we have. Similarly define c_{(1, 1)} and c_{(0, 1)}.
- If all three values are even, or at most one of them is odd, then the answer is
"Yes", otherwise the answer is"No".
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <iostream>
#include <string>
using namespace std;
#define ll long long
int main() {
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string s,t;
cin>>s>>t;
ll cnt[3]={};
ll x,y;
for(int i=0;i<n;i++){
x=s[i]-'0';
y=t[i]-'0';
cnt[x+y]++;
}
ll flag=(cnt[0]%2)+(cnt[1]%2)+(cnt[2]%2);
if(flag<=1){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s, t;
cin>>s>>t;
int dif = 0;
int z = 0;
int o = 0;
for(int i = 0; i < n; i++){
if(s[i] == t[i]){
if(s[i] == '0'){
z++;
}else{
o++;
}
}else{
dif++;
}
}
if((o % 2 + z % 2 + dif % 2 ) <= 1){
cout<<"YeS\n";
}else{
cout<<"nO\n";
}
}
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
t = input()
c = [0, 0, 0]
for i in range(n):
c[0] ^= s[i] == '0' and t[i] == '0'
c[1] ^= s[i] == '1' and t[i] == '1'
c[2] ^= s[i] != t[i]
print('Yes' if sum(c) <= 1 else 'No')