PLAYSTR - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Anik Sarker, Ezio Auditore

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

PREREQUISITES:

Basic Math.

PROBLEM:

Given two binary strings S and R, determine if it’s possible to convert string S to string R if you are allowed to swap any pair of characters in the string S any number of times (including zero times).

EXPLANATION

Since we can make any number of swaps, we can get all possible orderings of the characters of string S. So, we need to find whether string R is one of the ordering of string S. Hence, the only condition here is that if a character is present in string R but not in string S, then no ordering of string S is same as string R, and hence the answer is NO.

Similarly, Let us suppose some character appears x times in string S and y times in string R, then a valid ordering of string S can exist if and only if x equals y. It can be proven that it is sufficient condition for the existence of the required ordering of string S.

So, in conclusion, we just need the frequency of each character to be same among both strings. This can be easily checked by maintaining the frequency of each character.

Bonus 1: Find out the minimum number of swaps needed to make S and R equal.

Bonus 2: Find out the minimum number of swaps needed to make S and R equal, if both S and R contain lowercase English characters.

Bonus 3: Find out the minimum number of swaps needed to make S and R equal, if only swaps among adjacent positions are allowed.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter 1 Solution
#include <bits/stdc++.h>
using namespace std;

int main(){
	int T;
	scanf("%d",&T);

	for(int cs=1;cs<=T;cs++){
	    int N;
	    scanf("%d",&N);

	    string a,b;
	    cin>>a>>b;

	    sort(a.begin(),a.end());
	    sort(b.begin(),b.end());
	    cout<< ((a==b) ? "YES" : "NO") <<endl;
	}
}
Setter 2 Solution
#include<bits/stdc++.h>
using namespace std;
int t, cs = 1, n;

string s1, s2;
int main()
{
//    freopen("input00.txt", "r", stdin);
//    freopen("output00.txt", "w", stdout);
	cin >> t;
	if(t < 1 || t > 400) assert(false);

	while(t--){

	    cin >> n >> s1 >> s2;
	    if(s1.size() != n || s2.size() != n) assert(false);
	    if(n < 1 || n > 100) assert(false);

	    int cnt0 = 0, cnt1 = 0;

	    for(int i = 0; i < n; i++){
	        if(s1[i] == '0') cnt0++;
	        else if(s1[i] == '1') cnt1++;
	        else{
	            assert(false);
	        }

	        if(s2[i] == '0') cnt0--;
	        else if(s2[i] == '1') cnt1--;
	        else{
	            assert(false);
	        }

	    }

	    if(cnt0 == 0 && cnt1 == 0) printf("YES\n");
	    else printf("NO\n");

	}

	return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		string s,t;
		cin>>s>>t;
		int i;
		int cnt=0;
		rep(i,n){
			if(s[i]=='1')
				cnt++;
			if(t[i]=='1')
				cnt--;
		}
		if(cnt==0){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}

	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class PLAYSTR{
	//SOLUTION BEGIN
	//Into the Hardware Mode
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    char[] c1 = n().toCharArray(), c2 = n().toCharArray();
	    int[] f = new int[2];
	    for(char c:c1)f[c-'0']++;
	    for(char c:c2)f[c-'0']--;
	    pn((f[0]==0 && f[1] == 0)?"YES":"NO");
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long IINF = (long)1e18, mod = (long)1e9+7;
	final int INF = (int)1e9, MX = (int)2e5+5;
	DecimalFormat df = new DecimalFormat("0.00000000000");
	double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-6;
	static boolean multipleTC = true, memory = false, fileIO = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    if(fileIO){
	        in = new FastReader("input.txt");
	        out = new PrintWriter("output.txt");
	    }else {
	        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{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new PLAYSTR().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new PLAYSTR().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	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;
	    }
	}
}

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

what are the expected time complexity of bonuses ?
I mean brute force solution exists :sweat_smile::sweat_smile:

As problem says we need to check that can we make to strings identical or not so
I just Sorted both the string and compare it if it’s equal then print “YES” else “NO”.

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin>>t;
	while(t--)
	{
        int n;
        cin>>n;
        
        string s,r;
        cin>>s>>r;
        
        sort(s.begin(),s.end());
        sort(r.begin(),r.end());
        
        if(s == r)
            cout<<"YES\n";
        else
            cout<<"NO\n";
	}
	return 0;
}
6 Likes

My solution-I am not a great coder so i did this

#include <bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin >>t;
	while (t--){
		int o=0,z=0,o1=0,z1=0;
		int n;
		cin >>n;
		string s ;
		string r;
		cin >> s;
		cin  >> r;
		for (int i =0;i<n;i++){
			int sx = s[i]-'0';
			int rx = r[i]-'0';
			if (sx==1){
				o++;
				}
				else{
					z++;
					}
					
			if (rx==1){
				o1++;
				}
				else{
					z1++;
					}
			
			}
		
		
		
			if (o1==o ){
				cout <<"YES"<<endl;
				}
				else {
					cout <<"NO"<<endl;}
		
		}
	
	
	return 0;
	}
1 Like

As I’ve seen people are asking for the problem in their codes.
What I’ve seen:
While declaring a string in C/C++
Do follow this:
char s[Length of string + 1], s1[Length of string + 1];
That “+ 1” is for the extra space as the strings are terminated by a null character “\0”.
Hope it helps someone. :slight_smile:

6 Likes

You can just count number of 1 in both strings, if the number of 1 is equal in both string then YES else NO.

Can anyone help me to figure out this! I have written the code but the compiler shows the runtime error. It executed in others compiler but not on this!

#include<stdio.h>
#include<string.h>
int main()
{
int t,i,l1,l2,j,k,l,m,count=0,n,x;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d\n",&n);
char s[n],r[n],temp,temp2;
scanf("%s\n",&s);
scanf("%s",&r);
l1=strlen(s);
l2=strlen ®;
if(l1!=l2)
{
printf(“NO\n”);
}
else
{
for(j=0;j<l1;j++)
{
for(k=j+1;k<l1;k++)
{
if(s[j]>s[k])
{
temp=s[j];
s[j]=s[k];
s[k]=temp;
}
}
}
for(l=0;l<l2;l++)
{
for(m=l+1;m<l2;m++)
{
if(r[l]>r[m])
{
temp2=r[l];
r[l]=r[m];
r[m]=temp2;
}
}
}
for(x=0;x<l1;x++)
{
if(s[x]==r[x])
{
count++;
}
}
if(count==l1)
{
printf(“YES\n”);
}
else
{
printf(“NO\n”);
}
}
l1=0;
l2=0;
n=0;
temp=’\0’;
temp2=’\0’;
count=0;

}
return 0;

}

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

Actually, I can decipher enough of it to see the problem - you’re trying to scanf a string of length n into an array of length n - since scanf("%s", blah) adds a null-terminator, your array(s) are too small to hold the read string and you get Undefined Behaviour.

Edit2:

Basically, what @duddumahesh said, above :slight_smile:

2 Likes

I counted the number of 0’s and 1’s in both strings and compared the numbers. If the numbers were different I would output “NO” else I would output “YES”

using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		string s, r;
		cin >> s >> r;
		int counters1 = 0;
		int counters0 = 0;
		int counterr0 = 0;
		int counterr1 = 0;
		for(int i = 0; i < n; i++) {
			if(s[i] == '1') {
				counters1++;
			}
			if(s[i] == '0') {
				counters0++;
			}
			if(r[i] == '1') {
				counterr1++;
			}
			if(r[i] == '0') {
				counterr0++;
			}
		}
		if(counterr0 != counters0 || counters1 != counterr1 || (counterr0 != counters0 && counters1 != counterr1)) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
		}
	}
}
	```