codeforces-scrape

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

1750C.md (3122B)


      1 Source: https://codeforces.com/problemset/problem/1750/C
      2 
      3 C. Complementary XOR
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 You have two binary strings $a$ and $b$ of length $n$. You would like to make all the elements of both strings equal to $0$. Unfortunately, you can modify the contents of these strings using only the following operation:
     22 
     23 * You choose two indices $l$ and $r$ ($1 \le l \le r \le n$);
     24 * For every $i$ that respects $l \le i \le r$, change $a_i$ to the opposite. That is, $a_i := 1 - a_i$;
     25 * For every $i$ that respects either $1 \le i \lt l$ or $r \lt i \le n$, change $b_i$ to the opposite. That is, $b_i := 1 - b_i$.
     26 
     27 Your task is to determine if this is possible, and if it is, to find such an appropriate chain of operations. The number of operations should not exceed $n + 5$. It can be proven that if such chain of operations exists, one exists with at most $n + 5$ operations.
     28 
     29 Input
     30 
     31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the strings.
     34 
     35 The second line of each test case contains a binary string $a$, consisting only of characters 0 and 1, of length $n$.
     36 
     37 The third line of each test case contains a binary string $b$, consisting only of characters 0 and 1, of length $n$.
     38 
     39 It is guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each testcase, print first "YES" if it's possible to make all the elements of both strings equal to $0$. Otherwise, print "NO". If the answer is "YES", on the next line print a single integer $k$ ($0 \le k \le n + 5$) — the number of operations. Then $k$ lines follows, each contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the operation.
     44 
     45 If there are several correct answers, print any of them.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 3
     55 
     56 010
     57 
     58 101
     59 
     60 2
     61 
     62 11
     63 
     64 10
     65 
     66 4
     67 
     68 1000
     69 
     70 0011
     71 
     72 2
     73 
     74 10
     75 
     76 10
     77 
     78 3
     79 
     80 111
     81 
     82 111
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 YES
     89 1
     90 2 2
     91 NO
     92 NO
     93 YES
     94 2
     95 1 2
     96 2 2
     97 YES
     98 2
     99 1 1
    100 2 3
    101 ```
    102 
    103 Note
    104 
    105 In the first test case, we can perform one operation with $l = 2$ and $r = 2$. So $a_2 := 1 - 1 = 0$ and string $a$ became equal to 000. $b_1 := 1 - 1 = 0$, $b_3 := 1 - 1 = 0$ and string $b$ became equal to 000.
    106 
    107 In the second and in the third test cases, it can be proven that it's impossible to make all elements of both strings equal to $0$.
    108 
    109 In the fourth test case, we can perform an operation with $l = 1$ and $r = 2$, then string $a$ became equal to 01, and string $b$ doesn't change. Then we perform an operation with $l = 2$ and $r = 2$, then $a_2 := 1 - 1 = 0$ and $b_1 = 1 - 1 = 0$. So both of string $a$ and $b$ became equal to 00.
    110 
    111 In the fifth test case, we can perform an operation with $l = 1$ and $r = 1$. Then string $a$ became equal to 011 and string $b$ became equal to 100. Then we can perform an operation with $l = 2$ and $r = 3$, so both of string $a$ and $b$ became equal to 000.