Xor of 3 (Codeforces 1573D)
Tags: Others, constructive algorithms

You are given a sequence $$$a$$$ of length $$$n$$$ consisting of $$$0$$$s and $$$1$$$s.You can perform the following operation on this sequence:   Pick an index $$$i$$$ from $$$1$$$ to $$$n-2$$$ (inclusive).  Change all of $$$a_{i}$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ to $$$a_{i} \oplus a_{i+1} \oplus a_{i+2}$$$ simultaneously, where $$$\oplus$$$ denotes the bitwise XOR operation  Find a sequence of at most $$$n$$$ operations that changes all elements of $$$a$$$ to $$$0$$$s or report that it's impossible.We can prove that if there exists a sequence of operations of any length that changes all elements of $$$a$$$ to $$$0$$$s, then there is also such a sequence of length not greater than $$$n$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2\cdot10^5$$$) — the length of $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 0$$$ or $$$a_i = 1$$$) — elements of $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, do the following:   if there is no way of making all the elements of $$$a$$$ equal to $$$0$$$ after performing the above operation some number of times, print "NO".  otherwise, in the first line print "YES", in the second line print $$$k$$$ ($$$0 \le k \le n$$$) — the number of operations that you want to perform on $$$a$$$, and in the third line print a sequence $$$b_1, b_2, \dots, b_k$$$ ($$$1 \le b_i \le n - 2$$$) — the indices on which the operation should be applied. If there are multiple solutions, you may print any.

Note: In the first example, the sequence contains only $$$0$$$s so we don't need to change anything.In the second example, we can transform $$$[1, 1, 1, 1, 0]$$$ to $$$[1, 1, 0, 0, 0]$$$ and then to $$$[0, 0, 0, 0, 0]$$$ by performing the operation on the third element of $$$a$$$ and then on the first element of $$$a$$$.In the third example, no matter whether we first perform the operation on the first or on the second element of $$$a$$$ we will get $$$[1, 1, 1, 1]$$$, which cannot be transformed to $$$[0, 0, 0, 0]$$$.

Sample Inputs:
3
3
0 0 0
5
1 1 1 1 0
4
1 0 0 1

Sample Outputs:
YES
0
YES
2
3 1
NO

Solution (Python):
import collections
import math
import itertools
import sys
import time
import random

def fast_input():
    return sys.stdin.readline().strip()
input = fast_input

def ints_input():
    return list((int(x) for x in input().split()))

def int_input():
    return int(input())

def solve():
    n = int_input()
    a = ints_input()
    if sum(a) % 2 == 1:
        print('NO')
        return
    reversed = False
    ops = []

    def do_op(i):
        ops.append(i + 1)
        a[i] = a[i + 1] = a[i + 2] = a[i] ^ a[i + 1] ^ a[i + 2]
    if a[0] == 1:
        i = 1
        found = False
        while i + 1 < n:
            if a[i] == a[i + 1]:
                i += 2
            else:
                found = True
                break
        if not found:
            if i == n - 1 and a[i] == 1:
                print('NO')
                return
            else:
                reversed = True
                a = a[::-1]
                if a[0] == 1:
                    do_op(0)
        else:
            x = i
            while x >= 1:
                do_op(x - 1)
                x -= 2
    p = 1
    while p + 1 < n:
        if a[p] != a[p + 1]:
            do_op(p)
            if a[p] == 0:
                p += 2
        else:
            if a[p] != 0:
                do_op(p - 1)
            p += 2
    print('YES')
    print(len(ops))
    if reversed:
        ops = [n - 1 - i for i in ops]
    print(' '.join([str(x) for x in ops]))
if True:
    for _ in range(int_input()):
        solve()
else:
    solve()

Solution (Python):
import collections
import math
import itertools
import time
import random

def ints_input():
    return list((int(x) for x in input().split()))

def int_input():
    return int(input())
for _ in range(int_input()):
    n = int_input()
    a = ints_input()
    if sum(a) % 2 == 1:
        print('NO')
        continue
    reversed = False
    ops = []

    def do_op(i):
        ops.append(i + 1)
        a[i] = a[i + 1] = a[i + 2] = a[i] ^ a[i + 1] ^ a[i + 2]
    if a[0] == 1:
        i = 1
        found = False
        while i + 1 < n:
            if a[i] == a[i + 1]:
                i += 2
            else:
                found = True
                break
        if not found:
            if i == n - 1 and a[i] == 1:
                print('NO')
                continue
            else:
                reversed = True
                a = a[::-1]
                if a[0] == 1:
                    do_op(0)
        else:
            x = i
            while x >= 1:
                do_op(x - 1)
                x -= 2
    p = 1
    while p + 1 < n:
        if a[p] != a[p + 1]:
            do_op(p)
            if a[p] == 0:
                p += 2
        else:
            if a[p] != 0:
                do_op(p - 1)
            p += 2
    print('YES')
    print(len(ops))
    if reversed:
        ops = [n - 1 - i for i in ops]
    print(' '.join([str(x) for x in ops]))

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list((int(x) for x in input().split()))
    if sum(a) % 2:
        print('NO')
        continue
    reversed = False
    ops = []

    def do_op(i):
        ops.append(i + 1)
        a[i] = a[i + 1] = a[i + 2] = a[i] ^ a[i + 1] ^ a[i + 2]
    if a[0] == 1:
        i = 1
        found = False
        while i + 1 < n:
            if a[i] == a[i + 1]:
                i += 2
            else:
                found = True
                break
        if not found:
            if i == n - 1 and a[i] == 1:
                print('NO')
                continue
            else:
                reversed = True
                a = a[::-1]
                if a[0] == 1:
                    do_op(0)
        else:
            x = i
            while x >= 1:
                do_op(x - 1)
                x -= 2
    p = 1
    while p + 1 < n:
        if a[p] != a[p + 1]:
            do_op(p)
            if not a[p]:
                p += 2
        else:
            if a[p]:
                do_op(p - 1)
            p += 2
    print('YES')
    print(len(ops))
    if reversed:
        ops = [n - 1 - i for i in ops]
    print(' '.join([str(x) for x in ops]))