PROBLEM LINK:
Setter: jeevanjyot
Testers: gamegame
Editorialist: aryanag_adm
DIFFICULTY:
1982
PREREQUISITES:
None
PROBLEM:
You are given two binary strings A and B of length N.
In one operation, you can select any index 1 \leq i < N, and change both A_i and A_{i+1} to A_i \oplus A_{i+1}.
Determine whether it’s possible to convert A to B by performing these operations.
EXPLANATION:
The operations have the following effects:
- 01 becomes 11
- 10 becomes 11
- 00 becomes 00
- 11 becomes 00
Let’s get the easy cases out of the way:
- If A = B, the answer is YES
- If A is 000...00 (i.e A does not have a 1), then we can only the third type of operation, which does not change anything. Therefore, the answer is NO if A \neq B.
Now, assume A \neq B and A has a 1.
Claim: It is possible to convert A to B if any only if B has two consecutive characters that are equal
Proof:
Assume it is possible to convert A to B. Since A \neq B, we have to do at least 1 operation on A. Assume that the last operation is done on index i and i+1. Then, after this operation, A_i = A_{i+1} which implies that B_i = B_{i+1}. Therefore, B must have two consecutive characters that are equal.
Now assume that B has two consecutive equal characters B_i and B_{i+1}. First, using the type 1 and type 2 operations, we can convert A to 111....1 (the string without 0). Now, by performing the 4th type of operation and possibly an extra operation of type 1 or 2, we can turn every element of A to 0, except A_i and A_{i+1} which both remain 1. Now, we need to turn this A into B.
First, we look at all indices < i. Pick the smallest index j such that B_j = 1. We can perform operations to make A_j = 1 and not affect any other index in A as follows:
- Assume that j = 1, i = 3, so we want to convert 0011 into 1011. The same idea works for larger i.
- 0|01|1 = 0111
- |01|11 = 1111
- 1|11|1 = 1001
- 10|01| = 1011
This way, we can keep fixing the 1s from left to right until index i.
For indices > i, we can perform the same operations symmetrically and fix 1s from right to left.
Now, for all indices j such that j < i or j > {i+1}, we have A_j = B_j, and we have A_i = A_{i+1} = 1. Finally, if B_i = B_{i+1} = 0, we perform an operation on i and i+1 which would make A_i = A_{i+1} = 0, else we leave it as it is.
This completes the proof.
We can easily check all 3 of these conditions. This solves the problem.
TIME COMPLEXITY:
Time complexity is O(N).
SOLUTION:
Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
//#define int long long
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string a, b;
cin>>a>>b;
int oc = (a[n-1]=='1'), co = 0;
for(int i = 0;i<(n-1);i++){
oc += (a[i] == '1');
co += (b[i] == b[i+1]);
}
if((oc>0 && co>0) || (a==b)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
