codeforces-scrape

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

2092B.md (2627B)


      1 Source: https://codeforces.com/problemset/problem/2092/B
      2 
      3 B. Lady Bug
      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 As soon as Dasha Purova crossed the border of France, the villain Markaron kidnapped her and placed her in a prison under his large castle. Fortunately, the wonderful Lady Bug, upon hearing the news about Dasha, immediately ran to save her in Markaron's castle. However, to get there, she needs to crack a complex password.
     22 
     23 The password consists of two bit strings $a$ and $b$, each of which has a length of $n$. In one operation, Lady Bug can choose any index $2 \le i \le n$ and perform one of the following actions:
     24 
     25 1. swap($a_i$, $b_{i-1}$) (swap the values of $a_i$ and $b_{i-1}$), or
     26 2. swap($b_i$, $a_{i-1}$) (swap the values of $b_i$ and $a_{i-1}$).
     27 
     28 Lady Bug can perform any number of operations. The password is considered cracked if she can ensure that the first string consists only of zeros. Help her understand whether or not she will be able to save the unfortunate Dasha.
     29 
     30 Input
     31 
     32 Each test consists of several test cases. The first line of the input data contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains one integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the bit strings of the password.
     35 
     36 The next two lines contain the bit strings of length $n$, $a$ and $b$, which represent the password. Each of the strings contains only the characters 0 and '1'.
     37 
     38 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output "YES" if Lady Bug can crack the password after any number of operations; otherwise, output "NO".
     43 
     44 You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 
     53 3
     54 
     55 000
     56 
     57 000
     58 
     59 6
     60 
     61 010001
     62 
     63 010111
     64 
     65 5
     66 
     67 10000
     68 
     69 01010
     70 
     71 2
     72 
     73 11
     74 
     75 00
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 YES
     82 YES
     83 NO
     84 YES
     85 ```
     86 
     87 Note
     88 
     89 In the first test case, the string $a$ immediately consists only of zeros.
     90 
     91 In the second test case, a possible sequence of operations is:
     92 
     93 1. swap$(a_2, \ b_{1})$
     94 
     95    $\mathtt{0{\color{red}{1}}0001}$
     96 
     97    $\mathtt{{\color{red}{0}}10111}$
     98 2. swap$(b_5, \ a_{4})$
     99 
    100    $\mathtt{000{\color{red}{0}}01}$
    101 
    102    $\mathtt{1101{\color{red}{1}}1}$
    103 3. swap$(a_4, \ b_{3})$
    104 
    105    $\mathtt{000{\color{red}{1}}01}$
    106 
    107    $\mathtt{11{\color{red}{0}}101}$
    108 4. swap$(a_5, \ b_{4})$
    109 
    110    $\mathtt{00000{\color{red}{1}}}$
    111 
    112    $\mathtt{1111{\color{red}{0}}1}$