codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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