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.