FAKESWAP - EDITORIAL

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. :slight_smile:

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 :slight_smile:

1 Like

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

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?