SWAP10HG - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hriday
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Just observation would do. Prefix sums would be added bonus.

PROBLEM

Given two binary strings S and P of length N each, determine whether S can be made equal to P if we can apply the following operation on S any number of times.

Choose two indices i and j (1 \leq i \leq j \leq N) such that S_i is ‘1’ and S_j is ‘0’, swap S_i and S_j

QUICK EXPLANATION

  • The operation doesn’t change the number of 1s and 0s in string S, so if the number of 0s or 1s differ among strings, they can never become equal with the above operation.
  • If some prefix of P contains more 1s than the prefix of S of the same length, it is not possible to make S and P equal.
  • In all other cases, strings can be made equal.

EXPLANATION

The first observation is easy. Since the number of 0s and 1s remains unaltered, so if initially, the number of occurrences of 0s and 1s differ in S and P, there’s no way we can ever make both strings equal.

Now, coming to the operation, we can visualize it as moving a 1 towards the right. It is easy to see that after some sequence of swaps if the initial position of 1 was p, it must end up in position q such that p \leq q.

So now, let’s number the 1s present in S and T from right to left. Position of i-th labeled 1 in S denote its start position and it’s the position in T denote its end position. So if there exists any 1 whose start position is to the right of the end position, it is impossible to make strings equal.

An alternate view of the above condition is:
If there’s any length L such that prefix of length L of S contains strictly less 1s than prefix of length L of string T, then the answer is impossible.

This happens because the last occurrence of 1 in the prefix of T must have start position > L and end position \leq L, leading to the impossible case as above.

Using the above condition, we can simply check the count of 1s for each prefix to determine the possibility.

Bonus: Find the minimum number of operations needed to convert S to T.

TIME COMPLEXITY

The time complexity is O(N) per test case.
The memory complexity can be O(1) per test case excluding input.

SOLUTIONS

Setter's Solution
/**
 >> the_hyp0cr1t3
 >> 24.12.2020 17:28:43
**/
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
 
const int64_t DESPACITO = 2e18;
const int INF = 2e9, MOD = 1e9+7;
const int N = 2e5 + 5;
 
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t; cin >> t;
	while(t--) {
	    int n; string s, t;
	    cin >> n >> s >> t;
	    bool good = count(all(s), '1') == count(all(t), '1');
	    for(int i = 0, pref = 0; i < n; i++) {
	        pref += (s[i] == '1') - (t[i] == '1');
	        good &= pref >= 0;
	    } cout << (good? "YEs" : "nO") << '\n';
	}
	
} // ~W 
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}

int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			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_n=0;
void solve() {
	int n=readIntLn(1,100000);
	sum_n+=n;
	assert(sum_n<=100000);
	string s=readStringLn(n,n);
	string t=readStringLn(n,n);
	for(char i:s)
		assert(i=='0'||i=='1');
	for(char i:t)
		assert(i=='0'||i=='1');
	int p=0;
	for(int i=0; i<n; i++) {
		p+=ll(s[i])-ll(t[i]);
		if(p<0) {
			cout<<"No"<<endl;
			return;
		}
	}
	if(p==0)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}



signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,100'000);
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class SWAP10HG{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni();
	    String S = n(), T = n();
	    int sum = 0;
	    boolean good = true;
	    for(int i = 0; i< N; i++){
	        if(S.charAt(i) == '1')sum++;
	        if(T.charAt(i) == '1')sum--;
	        good &= sum >= 0;
	    }
	    good &= sum == 0;
	    pn(good?"Yes":"No");
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new SWAP10HG().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

2 Likes

I simply tried to convert s to p, making sure if conversion is possible.

https://www.codechef.com/viewsolution/40797888

4 Likes

Some test cases for Python3 give NZEC. It seems that both strings S and P and not always the same length. See Solution: 40846253 | CodeChef and Solution: 40846170 | CodeChef where the only difference is the answer given if the strings on not the same length.

Each testcase has 3 lines. One of them is length of given strings. You forgot to take that as input.

4 Likes

Can someone give test case where my code fails?
https://www.codechef.com/viewsolution/40847231

https://www.codechef.com/viewsolution/40800450
Please tell why i am failing the first 2 cases iam getting 80/100

1 Like

Plz check where my code failed
https://www.codechef.com/viewsolution/40838022

It’s been a quite easy using Stack and optimal also
can try it out my solution
https://www.codechef.com/viewsolution/40848571

1 Like

https://www.codechef.com/viewsolution/40830001
Can anybody check where my 20 point task failed

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lli long long int
#define pb push_back
#define vi vector
#define vll vector
#define vlli vector
#define fo1(i,n) for (ll i=0; i<n; i++)
#define fo2(i,m) for (ll i=0; i<m; i++)

void solve(){
ll n;
string s, p;
cin >>n;
cin >>s;
cin >>p;

if (s==p)
    cout<<"Yes";
else{
    sort(s.begin(), s.end());
    sort(p.begin(), p.end());
    if (s==p)
        cout<<"Yes";
    else
        cout<<"No";
}

}
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
ll tc=1;
cin >>tc;
while(tc–){
solve();
cout<<"\n";
}
}

//Is this solution is right and if wrong then what’s problem in there can anybody please explain it to me? I see it as a correct solution.

It’s wrong because the question states that your ith term should be 1 and jth term should be 0 before swap even if all the elements are same but you are unable to swap for example
0011 - S
1100 - P
I can’t swap 0 with 1 in S because i < j condition would be voided hence this example comes under “No”

4 Likes

No you can’t. Read the question carefully, especially where swapping condition is given. It says 1<=i<j<=N such that Si is 1 and Sj is 0. There will be cases where this condition will fail even if the number of 1s are equal in both strings.

Your code will fail for this test case-
1
6
110100
001011

Your code will fail for this test case-
1
6
110100
001011
Output should be Yes

TEST Case:
011
101
Hint: Read question again

:100: potential test cases
2
7
1110000
0011100
7
0110100
1011000
i think :thought_balloon: they may suffice to aid debugging if you are getting wa ,
note the triffle difference b/w the 2 test case ,

Hey Everybody,
Link for my solution
Solution: 40830211 | CodeChef
Can anybody help me get why this solution is wrong because this solution got 20 pts initially but after CodeChef removed some test cases the same solution got 70 pts but I am not able to get how this solution is getting WA is some cases?

thanks for looking into this, yes I see I made a stupid mistake.

I created a variable got = 0.
I just iterated from 0 to the length of the string.
Then I checked if (s[i] == '1' and p[i] == '0') got++; else if(s[i] == '0' && p[i] == '1') { if (got >= 1) got--; else { cout << "No\n"; break; } }
and after the loop I printed “Yes\n”.
Though my solution got accepted, I am not sure about the proof.
Can someone explain, please??

can anyone help me figure out where the code is breaking??

void solve()

{

// cout << fixed << setprecision(10);

int n;

string s, p;

cin >> n >> s >> p;

int sOne(0), sZero(0), pOne(0), pZero(0);

rep(i, n)

{

    if (s[i] == '1')

        sOne++;

    else

        sZero++;

}

rep(i, n)

{

    if (p[i] == '1')

        pOne++;

    else

        pZero++;

}

if (sOne != pOne || sZero != pZero)

{

    cout << "No\n";

    return;

}

int i(0), j(0);

while (i < n)

{

    while (i < n && s[i] == p[i])

    {

        i++;

    }

    if (i >= n || s[i] != '1')

    {

        break;

    }

    j = i + 1;

    while ((j < n && s[j] == p[j]) || (j < n && s[j] == '1'))

    {

        j++;

    }

    if (j >= n || s[j] != '0')

    {

        break;

    }

    swap(s[i], s[j]);

    i = j + 1;

}

if (s == p)

{

    cout << "Yes\n";

}

else

{

    cout << "No\n";

}

return;

}