 # FAKESWAP - EDITORIAL

Setter: S.Manuj Nanthan
Tester: Anshu Garg
Editorialist: Keyur Jain

Simple-Easy

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 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){
}
long long readIntLn(long long l,long long r){
}
}
}

int sum = 0;
int _runtimeTerror_()
{
sum += 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;
//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) {
if (s.equals(p)) {
out.printLine("Yes");
} else {
Set<Character> distinctCharactersInP = new HashSet<>();
for (char ch : p.toCharArray()) {
}
if (distinctCharactersInP.size() == 2) {
out.printLine("Yes");
} else {
out.printLine("No");
}
}
}
}```
``````

Feel free to share your approach. Suggestions are welcomed as always. 2 Likes

Can anyone tell me please what’s wrong with my code.
https://www.codechef.com/viewsolution/51316753

in line 50 just make this small change,

if ((cntOne>0 & zero>0) || isEqual)

1 Like

in 50th line just use this if ((cntOne>0 & zero>0) || isEqual) , your code can be wrong for cntOne=3 and zero=4 because 3 & 4 = 0 means both condition will be failed a/c to your code. Simple reason is first you should check that both is more than zero or not 1 Like

You are using & instead of && due to which you are getting the wrong answer. I hope it helps. 1 Like

Your code will give wrong answer in the cases where the and of cntOne and zero will give zero.Like if cntOne is 5 and zero is 2.
Test case :
1
7
0000000
1111100

1 Like

please any one can tell me that
1
6
111110
000001
how we can go through this test case
according to editorial it is ans is YES but this should be NO

take last 3 and make last one 1 and rest two zero and then in starting 3 1’s
make 2 zero and then take remaining 1 and last 1 and any zero and make remaining 1 to 0 .

Ohh, so silly mistake. My intention was to use && but don’t know how I missed one ‘&’ and that made me wrong thank you everyone.

In test case
6
100001
111110
how can it be converted by changing 3 indices?

100001 → 110001 → 111001 → 111101 → 111110

Can you please explain this solution? Aren’t 5 indices being changed?