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.