How to solve this Olympiad problem?

Question

Programming

Anniversary task
Each of the N lampposts located along N-sky Prospekt is painted in one of three colors: gray, brown or crimson. The chief architect wants all the pillars to have the same color by the city's anniversary. He decided to draw up a plan for repainting, but he does not have time to get acquainted with the existing coloring. Therefore, the plan must be universal, that is, lead to the desired result for any initial coloring. The plan consists of a list of pairs of pillars. This list is viewed sequentially. If both columns of the next pair of the list have the same color, then they are not touched, otherwise they are repainted in the third color (which does not match their colors).
Help the chief architect draw up such a plan, as short as possible.
Input data
It is required to solve the problem for the following input data: 5, 7, 8, 12, 25, 32, 34, 128, 253, 511, 999, 1000
Output
The output files are the solution to the problem. The first line of the output file must contain the number N for this test. If the problem cannot be solved, the second line should contain the number 0. Otherwise, the second line should contain the number M - the number of pairs in the plan, each of the next M lines should contain a pair of numbers - the numbers of the pillars.
Example 1
N = 3
3
0
Example 2
N = 4
4
4
1 2
3 4
1 3
2 4
Comment
So, I don't even know where to start. At first glance, the task seems simple, but for me personally, only at first glance. I myself am in my 3rd year in college, I'm almost 19 and I started programming myself relatively recently. I write in JS, not great, but I understand it quite well. But on the current task, I'm just blunt. What I just did not try to do, but I can not understand why there is no solution for N = 3.
The problem clearly states that the number of lanterns is initially unknown, and their coloring is also unknown. It turns out that the option "3 lanterns = 3 different colors => two are repainted and the problem is solved" takes place.
Please help, if at least you don’t solve the problem, then at least somehow roughly explain it in words, and I’ll try to transfer it to the code myself

Answer 1

This is a task of inventing a pattern and proving it. Here it is necessary to draw all sorts of cases on a piece of paper and generalize.
Firstly, when the question arises whether it is possible or not possible to obtain something by some operations, the first thought should be to come up with an invariant. Some property that does not change when an operation is applied. With experience, you will gain ideas for invariants. Here the following immediately comes to mind: Let's denote the colors by numbers from 0 to 2. Then, for any recoloring, the sum of all numbers modulo 3 does not change. If the columns are the same, the numbers themselves do not change, if 01 is recolored into 22, 02 into 11 and 12 into 00, then the sum remains with the same remainder of division by 3.
From this we can immediately conclude that when N is divided by 3, there is no answer. Because at the end we must get all the colors the same, which means the sum will be 0, N or 2N - divisible by N. Since N is divisible by 3, then the final sum gives a remainder of 0 (modulo 3). But the original coloring can have any remainder (for example, 00..0001). So there is no solution for such N.
Further, one can easily figure out how to "double" the solution. Let we be able to get some N, then we can get an algorithm for 2N. First, repaint the first half according to a known plan. Then the second half. Then in pairs, pillars of two halves. I hope it's obvious why this works?
So you can get an answer for 2,4,8,16, but this is not enough.
The next thought on how to build a universal paint plan is to take advantage of the fact that if we make all the posts the same, then all subsequent actions will not spoil anything. Those. you can take a specific coloring of the pillars, draw up a plan for it. Then take the next version of the input data, run it through the already drawn up plan. If the result is not one-color - supplement the plan in such a way as to paint everything in one color for this version of the original coloring. Repeat with all possible inputs. It is too slow to use this idea for all variants of N colorings (there are 3^N of them). We'll get back to her later.
The next idea should be - since indivisibility by 3 is important for the existence of a solution, then perhaps we can add 3 columns to a group of identical columns?
After analyzing several cases on paper, I realized that we need to separately consider the cases N%3=1 and N%3=2.
Let's consider the first case. We have 3k columns of color A, and at the end 4 more columns - AXYC (one of N and 3 new ones). The task is to get 4 identical colors at the end. We already have a solution for N=4 in the example. Just apply it to the 4th last columns. Now we have ...AAAZZZZ. If A=Z, then all our operations will do nothing. Consider only the case A!=Z. Paint A+Z, get AAYYZ..Z at the end Paint 2 times A+Y. Those. in 3 operations, we repainted the last 3 A's into Z. We repeat the operation until all A's are repainted (there are 3k of them, I remind you).
Now the case N=3k+2. We have 3k A, and AAXYC at the end. If you have a solution for 5, then you get 5 Z at the end and, similarly to the previous case, recolor the last 3 A's in the color of the last pillars.
Those. separately consider the case of different residues N%3. Then you solve the problem for the N=4 or 5 first columns, then add 3 columns each: solve the problem for the last 4/5 columns and iteratively recolor 3 columns from the previous ones.
This solution will require a maximum of N/3*(F(5)+N) steps, where F(5) is how many operations are needed to solve N=5.
Now the solution for N=5. Here it will be necessary to use the observation about the completion of the plan for different input data. There are 5 pillars here. Let's color 1+2 and 3+4. Now we have AABBC. Maybe some of the colors are the same. But first, let's assume that they are all three different. We paint in pairs A+B(1+3 and 2+4). All. But what if B=C, B!=A? We had AABBB. We painted 1+3 and 2+4 - got CCCSA. Paint 4+5 - CCCBB. Now, as before, recolor 3C to B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
Now we need to consider the case B=A, C!=A: AAAAC. It is necessary to carefully repeat all the operations above - we get BBBBB. The plan for this case works, nothing needs to be added. The remaining case is A=C, C!=B. Those. given by AABBA. Apply the steps above and get (recheck!) AAAAA.
That is, the whole plan for N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.
That's all the solution. I brought it in its entirety so that you get ideas and can understand how you can come to it.
It can be optimized by the number of operations. At the beginning, I gave a simple version of doubling. which quickly obtains a plan for powers of two. Below I have given how, having 2 groups of one-color pillars, if one group consists of triples, repaint everything in one color. Let's use these two methods.
Take the maximum power of two that fits in N. Let it be k (2k > N, k <= N). Apply the plan for the first k. then for the last k. In total, you will get Nk columns of one color and k columns of (possibly) another color at the end. If Nk is divisible by 3 then, according to the well-known "recoloring by triplets" plan, recolor the first Nk in the color of the last k. If Nk is not divisible by 3, then pair the columns with the colors of the first Nk and the colors of the second Nk. Then some pillars will remain at the end of another color, but their number will definitely be divisible by 3 (think up the proof of this fact yourself. Consider what the remainders of dividing by 3 can be for k and Nk). Since we have a group of a different color consisting of triplets, we can recolor it.
This option will require not a quadratic, but O (n log n) number of operations.