Complementary XOR (Codeforces 1750C)
Tags: Others, implementation

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:  You choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$);  For every $$$i$$$ that respects $$$l \le i \le r$$$, change $$$a_i$$$ to the opposite. That is, $$$a_i := 1 - a_i$$$;  For every $$$i$$$ that respects either $$$1 \le i < l$$$ or $$$r < i \le n$$$, change $$$b_i$$$ to the opposite. That is, $$$b_i := 1 - b_i$$$. 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. 

Input: 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.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.The second line of each test case contains a binary string $$$a$$$, consisting only of characters 0 and 1, of length $$$n$$$.The third line of each test case contains a binary string $$$b$$$, consisting only of characters 0 and 1, of length $$$n$$$.It is guaranteed that sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: 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.If there are several correct answers, print any of them.

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

Sample Inputs:
5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111

Sample Outputs:
YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3

Solution (Python):
import random

def brute(s1, s2, moves):
    s1_orig = s1
    s2_orig = s2
    s1 = list(map(int, s1))
    s2 = list(map(int, s2))
    for move in moves:
        (x, y) = map(int, move.split(' '))
        for i in range(x - 1, y):
            s1[i] = 1 - s1[i]
        for i in range(x - 1):
            s2[i] = 1 - s2[i]
        for i in range(y, len(s2)):
            s2[i] = 1 - s2[i]
    if s1.count(0) != len(s1) or s2.count(0) != len(s2):
        print(s1_orig, s2_orig, moves, s1, s2)
        raise RuntimeError

def solve(s1, s2, ans):
    all_same = False
    all_diff = False
    n = len(s1)
    for i in range(n):
        if not all_same and (not all_diff):
            if s1[i] == s2[i]:
                all_same = True
            else:
                all_diff = True
        else:
            if all_same and s1[i] != s2[i]:
                ans.append('NO')
                return
            if all_diff and s1[i] == s2[i]:
                ans.append('NO')
                return
    moves = []
    start = -1
    end = -1
    for i in range(n):
        if s1[i] == '1':
            if start == -1:
                start = i
            end = i
        else:
            if start != -1:
                moves.append(str(start + 1) + ' ' + str(end + 1))
            start = -1
            end = -1
    if start != -1:
        moves.append(str(start + 1) + ' ' + str(end + 1))
    if all_same:
        if len(moves) % 2 != 0:
            moves.append('1 1')
            moves.append('1 ' + str(len(s1)))
            moves.append('2 ' + str(len(s1)))
    elif s1.count('0') == len(s1) or len(moves) % 2 == 0:
        moves.append('1 1')
        moves.append('1 ' + str(len(s1)))
        moves.append('2 ' + str(len(s1)))
    assert len(moves) <= n + 5
    ans.append('YES')
    ans.append(len(moves))
    ans.extend(moves)

def main():
    t = int(input())
    ans = []
    for i in range(t):
        n = int(input())
        s1 = input()
        s2 = input()
        solve(s1, s2, ans)
    print('\n'.join(map(str, ans)))
main()

def get(n):
    s = ''
    for i in range(n):
        s += str(random.randint(0, 1))
    return s

def test():
    t = 1000
    for i in range(t):
        n = random.randint(2, 1000)
        s1 = get(n)
        s2 = get(n)
        solve(s1, s2, [])

Solution (Python):
import re
f = open(0)
I = f.readline
for _ in [0] * int(I()):
    n = int(I())
    a = I()[:-1]
    c = [[*m.span()] for m in re.finditer('1+', a)]
    i = (''.join((chr(ord(x) ^ 1) for x in a)), a, (b := I()[:-1])).index(b)
    if ~(len(c) ^ i) & 1:
        if c:
            (x, y) = c.pop()
            c += ((x - 1, y), (x - 1, x)) if x else ((x, x + 1), (x + 1, y)) if y - x > 1 else ((x, y + 1), (y, y + 1))
        else:
            c = ((0, 1), (0, n), (1, n))
    print(*(['NO'], ['YES', len(c)] + [f'{x[0] + 1} {x[1]}' for x in c])[i < 2])

Solution (Python):
import sys
input = sys.stdin.readline

def sol(n, a, b):
    ra = ''
    for i in a:
        if i == '0':
            ra += '1'
        if i == '1':
            ra += '0'
    if a == b or ra == b:
        res = []
        state = int(b[0])
        for i in range(n):
            if a[i] == '0':
                res.append([i, i])
                if i > 0:
                    state ^= 1
        if state:
            res.append([0, 0])
            res.append([1, n - 1])
        else:
            res.append([0, n - 1])
        print('YES')
        print(len(res))
        for (i, j) in res:
            print(i + 1, j + 1)
    else:
        print('NO')
t = int(input())
for case in range(t):
    n = int(input())
    a = input()[:-1]
    b = input()[:-1]
    sol(n, a, b)