1504B.md (2460B)
1 Source: https://codeforces.com/problemset/problem/1504/B 2 3 B. Flip the Bits 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 For example, suppose $a=0111010000$. 24 25 * 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$. 26 * 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$. 27 * It is illegal to select the prefix of length $4$ for the third operation, because it has three $0$'s and one $1$. 28 29 Can you transform the string $a$ into the string $b$ using some finite number of operations (possibly, none)? 30 31 Input 32 33 The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. 34 35 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$. 36 37 The following two lines contain strings $a$ and $b$ of length $n$, consisting of symbols $0$ and $1$. 38 39 The sum of $n$ across all test cases does not exceed $3\cdot 10^5$. 40 41 Output 42 43 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). 44 45 Example 46 47 Input 48 49 ``` 50 5 51 10 52 0111010000 53 0100101100 54 4 55 0000 56 0000 57 3 58 001 59 000 60 12 61 010101010101 62 100110011010 63 6 64 000111 65 110100 66 ``` 67 68 Output 69 70 ``` 71 YES 72 YES 73 NO 74 YES 75 NO 76 ``` 77 78 Note 79 80 The first test case is shown in the statement. 81 82 In the second test case, we transform $a$ into $b$ by using zero operations. 83 84 In the third test case, there is no legal operation, so it is impossible to transform $a$ into $b$. 85 86 In the fourth test case, here is one such transformation: 87 88 * Select the length $2$ prefix to get $100101010101$. 89 * Select the length $12$ prefix to get $011010101010$. 90 * Select the length $8$ prefix to get $100101011010$. 91 * Select the length $4$ prefix to get $011001011010$. 92 * Select the length $6$ prefix to get $100110011010$. 93 94 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$.