Flip the Bits
Contest: Codeforces Round 712 (Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, greedy, implementation, math

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 format:
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 format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

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

Example output:
YES
YES
NO
YES
NO

Editorial:
Let's call a prefix legal if it contains an equal number of $$$0$$$ and $$$1$$$ symbols. The key observation is that applying operations never changes which prefixes are legal. In fact, suppose we apply an operation to a prefix of length $$$i$$$, and consider a prefix of length $$$j$$$. We want to show that if $$$j$$$ was legal before, it remains legal. And if it wasn't legal, it won't become legal.
• If $$$j<i$$$, then all bits in the length $$$j$$$ prefix are inverted. The numbers of $$$0$$$'s and $$$1$$$'s swap, so it cannot change whether they are equal, and hence it cannot change whether $$$j$$$ is legal.
• If $$$j\ge i$$$, then $$$i/2$$$ of the $$$0$$$ symbols become $$$1$$$ and $$$i/2$$$ of the $$$1$$$ symbols become $$$0$$$. So the numbers of both symbols do not change, so it cannot change whether $$$j$$$ is legal.
Using prefix sums, we can determine for each prefix whether it is legal.
Consider an index $$$i$$$. If $$$i=n$$$ and $$$a_n\ne b_n$$$, then we must flip the length $$$n$$$ prefix at some point. If $$$i<n$$$ and $$$a_i=b_i$$$, $$$a_{i+1}\ne b_{i+1}$$$, or $$$a_i\ne b_i$$$, $$$a_{i+1}=b_{i+1}$$$, then we must flip the length $$$i$$$ prefix at some point. If we flip precisely these prefixes in any order, it will transform $$$a$$$ into $$$b$$$. So we should simply check that every prefix that must be flipped is legal.
Complexity is $$$O(n)$$$.