PROBLEM LINK:
Contest Div 1
Contest Div 2
Contest Div 3
Practice
Setter: S.Manuj Nanthan
Tester: Anshu Garg
Editorialist: Keyur Jain
DIFFICULTY
Simple-Easy
PREREQUISITES
None
PROBLEM
You are given two binary strings S and P. You need to convert S into P using the following operation any number of times (possibly zero):
- Pick three binary values X, Y, and Z, such that at least one of them is equal to 1 and at least one of them is equal to 0. Then, pick three distinct indices i, j, and k, and assign S_i=X, S_j=Y, and S_k=Z.
Determine whether it’s possible to convert S into P.
QUICK EXPLANATION
- It is impossible to convert S into P only when S != P and P is either all 0s or all 1s.
EXPLANATION
Let us try to think of all the cases when S cannot be converted to P.
There are two types of operations allowed on string S:
- set two characters to 1 and one character to 0
- set two characters to 0 and one character to 1
For us to make a valid operation we need to set atleast one character to 0 and atleast one character to 1. Since we are trying to make S equal to P, it follows that P must have atleast one 0 and atleast one 1.
If P comprises of all 0s or all 1s we will not be able to make S = P because S will end up having atleast one 0 and atleast one 1 after our operations while P only has a single distinct character.
A boundary case is when S is already equal to P, so we achieve our goal without any operations. It does not matter what the composition of P is in this case.
TIME COMPLEXITY
The time complexity is O(N)
SOLUTIONS
Setter's Solution
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
string s, t;
cin >> s >> t;
int ct = 0;
for(auto &it:t)
ct += (it - '0');
if(ct == n || ct == 0)
{
if(s == t)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else
cout << "Yes" << endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
const int M = 1000000007;
const int MM = 998244353;
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif
long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sum = 0;
int _runtimeTerror_()
{
int N = readIntLn(3,1000);
sum += N;
string S = readStringLn(N, N);
string P = readStringLn(N, N);
int one = 0, zero = 0;
for(int i=0;i<N;++i) {
assert(S[i] == '0' || S[i] == '1');
assert(P[i] == '0' || P[i] == '1');
one += P[i] == '1';
zero += P[i] == '0';
}
// assert(N == 1000);
if((zero && one) || S == P) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS = 1;
TESTS = readIntLn(1,1000);
//cin >> TESTS;
while(TESTS--)
_runtimeTerror_();
assert(getchar() == -1);
cerr << sum << "\n";
return 0;
}
Editorialist's Solution
public class FakeSwaps {
public void solve(int testNumber, InputReader in, OutputWriter out) {
int n = in.readInt();
String s = in.readString();
String p = in.readString();
if (s.equals(p)) {
out.printLine("Yes");
} else {
Set<Character> distinctCharactersInP = new HashSet<>();
for (char ch : p.toCharArray()) {
distinctCharactersInP.add(ch);
}
if (distinctCharactersInP.size() == 2) {
out.printLine("Yes");
} else {
out.printLine("No");
}
}
}
}```
Feel free to share your approach. Suggestions are welcomed as always. 
