Button Pressing (Codeforces 1906B)
Tags: Others, hashing

You are given $$$N$$$ buttons (numbered from $$$1$$$ to $$$N$$$) and $$$N$$$ lamps (numbered from $$$1$$$ to $$$N$$$). Each lamp can either be on or off. Initially, lamp $$$i$$$ is on if $$$A_i = 1$$$, and off if $$$A_i = 0$$$.Button $$$i$$$ is connected to lamp $$$i - 1$$$ (if $$$i > 1$$$) and lamp $$$i + 1$$$ (if $$$i < N$$$). In one move, you can press a button $$$i$$$ only if lamp $$$i$$$ is on. When a button is pressed, the state of the lamps connected to this button is toggled. Formally, the lamps will be on if it was off previously, and the lamps will be off if it was on previously. Note that lamp $$$i$$$ is not connected to button $$$i$$$, thus, the state of lamp $$$i$$$ does not change if button $$$i$$$ is pressed.After zero or more moves, you want lamp $$$i$$$ to be on if $$$B_i = 1$$$, and off if $$$B_i = 0$$$. Determine if it is possible to achieve this task.

Input: This problem has multiple test cases. The first line consists of an integer $$$T$$$ ($$$1 \leq T \leq 1000$$$), which represents the number of test cases. Each test case consists of three lines.The first line of each test case consists of an integer $$$N$$$ ($$$3 \le N \le 200\,000$$$). The sum of $$$N$$$ over all test cases does not exceed $$$200\,000$$$.The second line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$A$$$ can either be 0 or 1. The $$$i$$$-th character represents the initial state of lamp $$$i$$$.The third line of each test case consists of a string $$$A$$$ of length $$$N$$$. Each character of $$$B$$$ can either be 0 or 1. The $$$i$$$-th character represents the desired final state of lamp $$$i$$$.

Output: For each test case, output YES in a single line if the final state of all lamps can be reached after zero or more moves, or NO otherwise.

Note: Explanation for the sample input/output #1For the first test case, by pressing the buttons $$$4, 2, 4, 3, 1, 2$$$ in sequence, the condition of the buttons changes as: $$$0101 \rightarrow 0111 \rightarrow 1101 \rightarrow 1111 \rightarrow 1010 \rightarrow 1110 \rightarrow 0100$$$.For the second test case, you are unable to press any button, hence it is impossible to reach the final state.

Sample Inputs:
2
4
0101
0100
3
000
010

5
7
0101011
1111010
5
11111
00000
4
1101
1101
6
101010
100100
3
000
000

Sample Outputs:
YES
NO

NO
NO
YES
YES
YES

Solution (Python):
def rankk(n, s):
    i = s.find('0')
    if i == -1:
        return n
    j = s.find('1', i)
    if j == -1:
        return i
    k = s.find('0', j)
    while True:
        if k == -1:
            if (n - j) % 2:
                return n - j + i + 1
            else:
                return n - j + i
        if (k - j) % 2 == 0:
            i += k - j
            j = s.find('1', k)
            if j == -1:
                return i
            k = s.find('0', j)
        else:
            j2 = s.find('1', k)
            if j2 == -1:
                if j - i > n - k:
                    j -= n - k
                    k = -1
                elif j - i == n - k:
                    return n
                else:
                    return k + (j - i)
            elif j - i > j2 - k:
                j -= j2 - k
                k = s.find('0', j2)
            elif j - i == j2 - k:
                i = s.find('0', j2)
                if i == -1:
                    return n
                j = s.find('1', i)
                if j == -1:
                    return i
                k = s.find('0', j)
            else:
                i = k + (j - i)
                j = j2
                k = s.find('0', j2)
t = int(input())
for i in range(t):
    n = int(input())
    (a, b) = (input(), input())
    if (rankk(n, a) + 1) // 2 == (rankk(n, b) + 1) // 2:
        print('YES')
    else:
        print('NO')

Solution (Python):
def best(n):
    x = len(n)
    cz = 0
    i = 0
    while i < x:
        if n[i] == 0:
            cz += 1
            i += 1
        elif cz == 0:
            i += 1
        elif i + 1 != x:
            if n[i + 1] == 0:
                cz -= 1
                n[i + 1] = 1
                i += 1
            else:
                i += 2
        else:
            cz -= 1
            i += 1
    return cz
t = int(input())
for _i in range(t):
    nn = int(input())
    a = [int(i) for i in input()]
    b = [int(i) for i in input()]
    aa = nn - best(a)
    bb = nn - best(b)
    if (aa + 1) // 2 == (bb + 1) // 2:
        print('YES')
    else:
        print('NO')

Solution (Python):
def best(n):
    x = len(n)
    cz = 0
    i = 0
    while i < x:
        if n[i] == 0:
            cz += 1
            i += 1
        elif cz == 0:
            i += 1
        elif i + 1 != x:
            if n[i + 1] == 0:
                cz -= 1
                n[i + 1] = 1
                i += 1
            else:
                i += 2
        else:
            cz -= 1
            i += 1
    return cz
t = int(input())
for _i in range(t):
    nn = int(input())
    a = [int(i) for i in input()]
    b = [int(i) for i in input()]
    aa = nn - best(a)
    bb = nn - best(b)
    if (aa + 1) // 2 == (bb + 1) // 2:
        print('YES')
    else:
        print('NO')