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!