Triple Flips
Contest: Technocup 2019 - Elimination Round 2
Difficulty rating: 2600
Tags: constructive algorithms

You are given an array $$$a$$$ of length $$$n$$$ that consists of zeros and ones.

You can perform the following operation multiple times. The operation consists of two steps:

1. Choose three integers $$$1 \le x < y < z \le n$$$, that form an arithmetic progression ($$$y - x = z - y$$$).
2. Flip the values $$$a_x, a_y, a_z$$$ (i.e. change $$$1$$$ to $$$0$$$, change $$$0$$$ to $$$1$$$).

Determine if it is possible to make all elements of the array equal to zero. If yes, print the operations that lead the the all-zero state. Your solution should not contain more than $$$(\lfloor \frac{n}{3} \rfloor + 12)$$$ operations. Here $$$\lfloor q \rfloor$$$ denotes the number $$$q$$$ rounded down. We can show that it is possible to make all elements equal to zero in no more than this number of operations whenever it is possible to do so at all.

Input format:
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — the elements of the array.

Output format:
Print "YES" (without quotes) if the answer exists, otherwise print "NO" (without quotes). You can print each letter in any case (upper or lower).

If there is an answer, in the second line print an integer $$$m$$$ ($$$0 \le m \le (\lfloor \frac{n}{3} \rfloor + 12)$$$) — the number of operations in your answer.

After that in ($$$i + 2$$$)-th line print the $$$i$$$-th operations — the integers $$$x_i, y_i, z_i$$$. You can print them in arbitrary order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample the shown output corresponds to the following solution:

- 1 1 0 1 1 (initial state);
- 0 1 1 1 0 (the flipped positions are the first, the third and the fifth elements);
- 0 0 0 0 0 (the flipped positions are the second, the third and the fourth elements).

Other answers are also possible. In this test the number of operations should not exceed $$$\lfloor \frac{5}{3} \rfloor + 12 = 1 + 12 = 13$$$.

In the second sample the only available operation is to flip all the elements. This way it is only possible to obtain the arrays 0 1 0 and 1 0 1, but it is impossible to make all elements equal to zero.

Example input:
5
1 1 0 1 1

Example output:
YES
2
1 3 5
2 3 4

Example input:
3
0 1 0

Example output:
NO

Editorial:
This problem has a lot of solutions including those ones which are difficult to prove. Let's describe one of the author's solutions.
We can find answer with bruteforce if size of array is rather small. For example we can check all combinations of arithmetic progressions with length equals to three.
We can find by hand or bruteforce that for $$$3 \le n \le 7$$$ arrays with no solution exists but for $$$n = 8$$$ (and consequently for $$$n \ge 8$$$) we always can make all elements be equal to zero.
We want solution with such steps:
1. If $$$n$$$ is small just run bruteforce
2. Else try to make all elements besides the first $$$k$$$ ($$$k \ge 8$$$) be equal to zero
3. Run bruteforce on the first $$$k$$$ elements.
How to make the second step? Let's try to make three last elements of array be equal to zero with only one operation. We can use previous elements. So if we have array $$$\dots, 0, 0, 1$$$ we can change values of the first, the fourth and the seventh elements from the end. But $$$\dots, 0, 1, 1$$$ is counter-example.
Ok, let's try to make six last elements of array be equal to zero with two operations. We can check by hand or bruteforce that it can be done and $$$n \ge 11$$$ is enough.
So we have such solution:
1. Let $$$k$$$ is the number of first elements of array which we didn't try to make be equal to zero. In the start $$$k = n$$$
2. While $$$k \ge 11$$$ make $$$k$$$-th, $$$(k - 1)$$$-th,.., $$$(k - 5)$$$-th elements be equal to zero. Subtract 6 from $$$k$$$.
3. If $$$k \le 10$$$ run bruteforce on the first $$$10$$$ elements or on the whole array if $$$n < 10$$$.
How many operations will be done?
• In the second item the number of operations is less or equal than $$$2 \cdot \lfloor \frac{n}{6} \rfloor \le \lfloor \frac{n}{3} \rfloor$$$
• In the third item the number of operations is less or equal than 6 (can be checked by hand or bruteforce)
• So the total number of operations is less or equal than $$$\lfloor \frac{n}{3} \rfloor + 6$$$, what is good enough.