Hello there, here's an unofficial editorial for 1136D. Yui and Mahjong Set by a tester PinkRabbitAFO.
Observation: Focus on the differential of triplets/straights before and after an operation.
By doing an operation on $$$a_i$$$, you'll find that the differential of triplets equals $$$x (x - 1) / 2$$$, where $$$x$$$ equals $$$a_i$$$ before the operation.
So if we did a single operation on $$$a_i$$$, we can get the exact value of initial $$$a_i$$$ iff initial $$$a_i \ge 2$$$, otherwise initial $$$a_i$$$ must be equal to $$$0$$$ or $$$1$$$.
If we did two (or more, but unnecessary?) operation on $$$a_i$$$, we can now get the exact value of initial $$$a_i$$$ no matter whether $$$a_i$$$ is less than $$$2$$$ or not.
One of the most natural ideas is to perform operation in the order of $$$1, 2, \ldots, n$$$, it works like this:
Now, assume we get the exact value of $$$a_1 \sim a_i$$$, and we want to determine $$$a_{i + 1}$$$.
If $$$a_{i + 1} \ge 2$$$, done. Just consider the case $$$a_{i + 1} = 0$$$ or $$$1$$$.
Consider the differential of straights when doing the operation on $$$a_i$$$, let it be $$$d_i$$$ for convenience.
We have $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) a_{i + 1} + a_{i + 1} a_{i + 2}]$$$ (if any indices out of bounds, just ignore that term).
If $$$a_{i + 1} = 0$$$, then $$$d_i = (a_{i - 2} + 1) (a_{i - 1} + 1)$$$.
If $$$a_{i + 1} = 1$$$, then $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) + a_{i + 2}] > (a_{i - 2} + 1) (a_{i - 1} + 1)$$$ (because $$$a_{i - 1} + 1 > 0$$$).
So we can determine $$$a_{i + 1}$$$ by comparing $$$d_i$$$ and $$$(a_{i - 2} + 1) (a_{i - 1} + 1)$$$.
Note that you cannot use $$$d_{i - 1} = [(a_{i - 3} + 1) (a_{i - 2} + 1) + (a_{i - 2} + 1) * a_i + a_i * a_{i + 1}]$$$, because when $$$a_i = 0$$$ it's impossible to solve $$$a_{i + 1}$$$ (dividing by zero).
It's easy to see that only when $$$i \ge 2$$$, the method will work, so we need to get $$$a_1$$$ and $$$a_2$$$.
But it seems so hard to get any information of them.
Why not brute force? Try all possibilities of $$$a_1$$$ and $$$a_2$$$ (not many, $$$2^2 = 4$$$ at most) and run solution above.
I came up with this idea when testing the round, and got a verdict of WA on test 11.
Unfortunately, it cannot distinguish between $$$a = [1, 0, 0, 0]$$$ and $$$a = [0, 0, 0, 1]$$$.
More optimization needed.
First, notice that we don't need to do an operation on $$$a_n$$$. Why?
When $$$i = n - 1$$$, $$$d_i = [(a_{n - 3} + 1) (a_{n - 2} + 1) + (a_{n - 2} + 1)a_ n]$$$, thanks to the disappearance of the third term, and the coefficient $$$(a_{n - 2} + 1) \ne 0$$$, now can use division to solve $$$a_n$$$.
So we saved a move, where can it be added to?
It turns out if you add the operation to $$$a_1$$$ once more, you'll have a chance to find the correct solution.
That is, ask $$$1, 2, \ldots, (n - 1)$$$ and then $$$1$$$, in total $$$n$$$ operations.
Focus on the new operation, from it we can get $$$a_1$$$ at once.
Don't forget to use $$$d$$$, here $$$d = (a_2 + 1) (a_3 + 1)$$$.
Compare with the first $$$d_1 = a_2 a_3$$$, do a subtraction, we can get the value of $$$a_2 + a_3$$$.
Now the classification comes:
If $$$a_2 \ge 2$$$ or $$$a_3 \ge 2$$$, we can immediately get both $$$a_2$$$ and $$$a_3$$$.
Else if $$$a_2 + a_3 = 0$$$, $$$a_2 = a_3 = 0$$$.
Else if $$$a_2 + a_3 = 2$$$, $$$a_2 = a_3 = 1$$$.
Now exactly one of $$$a_2$$$ and $$$a_3$$$ is $$$1$$$ and the other is $$$0$$$.
Consider $$$d_2 = (a_1 + 1) a_3 + a_3 a_4$$$.
If $$$a_3 = 0$$$, then $$$d_2 = 0$$$.
If $$$a_3 = 1$$$, then $$$d_2 > 0$$$.
So, just check whether $$$d_2$$$ is equal to $$$0$$$ or not.
Now $$$a_{1, 2, 3}$$$ are known, use the method above, problem solved.
As I mentioned before, until the contest ends (tester round), I didn't realize "$$$1, 2, \ldots, n$$$" is not gonna work.
After communicating with Sulfox about the main solution, I made up my mind to discover a different solution.
After hours of "thinking" (chatting online) I found this solution.
Coincidentally, many participants came up with the same idea, and I'm very glad to see that.
Said too much.
Sorry for bad English expression (didn't check) (hopefully ouuan and Sulfox will fix them in the official editorial).
Questions welcomed.
Gonna sleep (almost 6 AM here).
