Menu Close

Transform the binary string A into the string B using finite operations

There is a binary string a of length n . In one operation, you can select any prefix of a with an equal number of 0 and 1 symbols. Then all symbols in the prefix are inverted: each 0 becomes 1 and each 1 becomes 0 .

For example, suppose a = 0111010000 .

In the first operation, we can select the prefix of length 8 since it has four 0 ‘s and four 1 ‘s: [01110100]00→[10001011]00 .
In the second operation, we can select the prefix of length 2 since it has one 0 and one 1 : [10]00101100→[01]00101100 .
It is illegal to select the prefix of length 4 for the third operation, because it has three 0 ‘s and one 1 .

Can you transform the string a into the string b using some finite number of operations (possibly, none)?

``````Input:
The first line contains integer t — the number of test cases.

The first line of each test case contains integer n — the length of the strings a and b .

The following two lines contain strings a and b of length n , consisting of symbols 0 and 1 .

The sum of n across all test cases does not exceed 3⋅10^5 .

Output:
For each test case, output "YES" if it is possible to transform a into b , or "NO" if it is impossible. You can print each letter in any case (upper or lower).``````
```#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int n_cases, n, balance, diff;
char s1[300001], s2[300001], *c1, *c2;
bool any_same, any_different;
scanf("%d", &n_cases);

while (n_cases--) {
scanf("%d", &n);
scanf("%s\n%s", s1, s2);
c1 = s1;
c2 = s2;
any_same = false;
any_different = false;
balance = 0;
diff = 0;

while (*c1) {
any_same = any_same||*c1==*c2;
any_different = any_different||*c1!=*c2;
if (any_same && any_different) break;
balance += *c2 == '1' ? 1 : -1;
diff += *c1 - *c2;
if (balance == 0) {
any_same = false;
any_different = false;
}
c1++;
c2++;
}
printf(((any_same && any_different)||diff!= 0)?"NO\n" : "YES\n");
}
return 0;
}```

INPUT_1:
2
8
00100011
00011001
10
0101010101
0110011010

OUTPUT:
NO
YES

INPUT_2:
5
4
0000
0000
8
01001010
11110000
3
001
000
12
010101010101
100110011010
6
000111
110100

OUTPUT:
YES
NO
NO
YES
NO

Morae Q!