Flip the Bits (Codeforces 1504B)
Tags: Math, implementation

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\to [10001011]00$$$.  In the second operation, we can select the prefix of length $$$2$$$ since it has one $$$0$$$ and one $$$1$$$: $$$[10]00101100\to [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 a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$) — 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\cdot 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).

Note: The first test case is shown in the statement.In the second test case, we transform $$$a$$$ into $$$b$$$ by using zero operations.In the third test case, there is no legal operation, so it is impossible to transform $$$a$$$ into $$$b$$$.In the fourth test case, here is one such transformation:   Select the length $$$2$$$ prefix to get $$$100101010101$$$.  Select the length $$$12$$$ prefix to get $$$011010101010$$$.  Select the length $$$8$$$ prefix to get $$$100101011010$$$.  Select the length $$$4$$$ prefix to get $$$011001011010$$$.  Select the length $$$6$$$ prefix to get $$$100110011010$$$. In the fifth test case, the only legal operation is to transform $$$a$$$ into $$$111000$$$. From there, the only legal operation is to return to the string we started with, so we cannot transform $$$a$$$ into $$$b$$$.

Sample Inputs:
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100

Sample Outputs:
YES
YES
NO
YES
NO

Solution (Python):
def solve(n, a, b):
    a += '0'
    b += '0'
    cnt = 0
    for i in range(n):
        cnt += (a[i] == '1') - (a[i] == '0')
        if (a[i] == b[i]) != (a[i + 1] == b[i + 1]) and cnt != 0:
            print('NO')
            return
    print('YES')
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
    if a == b:
        print('YES')
    else:
        solve(n, a, b)

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    n = readInt()
    (a, b) = (readStr(), readStr())
    ps = [0] * (n + 1)
    for i in range(n):
        ps[i + 1] = ps[i] + 1 if a[i] == '1' else ps[i] - 1
    cnt = 0
    for i in range(n - 1, -1, -1):
        if int(a[i]) ^ cnt == int(b[i]):
            continue
        if ps[i + 1] == 0:
            cnt ^= 1
        else:
            return 'NO'
    return 'YES'
for _ in range(int(input())):
    print(solve())

Solution (Python):
from collections import defaultdict
from decimal import Decimal

def main():
    n = int(input())
    l = input()
    l2 = input()
    c = 0
    zero = l.count('0')
    i = n - 1
    while i >= 0:
        if c == 0:
            if l[i] == l2[i]:
                if l[i] == '0':
                    zero -= 1
            else:
                i += 1
                c = 1
                if zero != i // 2 or i % 2 != 0:
                    print('No')
                    return
        elif c == 1:
            if l[i] != l2[i]:
                if l[i] == '0':
                    zero -= 1
            else:
                i += 1
                c = 0
                if zero != i // 2 or i % 2 != 0:
                    print('No')
                    return
        i -= 1
    print('Yes')
    return
for i in range(int(input())):
    main()