## Sunday, August 11, 2024

### A two times two week

There were no contests that I wanted to mention last week, but in the week before that I forgot to mention the 3rd Universal Cup Stage 5: Moscow (problems, results, top 5 on the left). Team HoMaMaOvO was the only one to wrap things up before the last hour, but they still lost out to USA1 because they were a bit slower on the easier problems: this was one of the relatively rare cases where the ICPC and the AtCoder penalty time formulas place different teams in the first place. Congratulations to both teams, to team Polish Mafia who were as fast but had much more incorrect attempts, at to team MIT Isn't Training who were the only remaining team to AK!

First, consider the case n=2. If the permutation is an identity permutation, we can just print w=0, and we're done. The only other case is when the permutation is a swap. Even in that case, there is actually not that many options for what we can do on the first pass. First, notice that we must not lose information after the first pass: all 2n possible sets of values of ai before and after the first pass must be in a one to one bijective relationship, as otherwise we would have two initial states map to the same state after the first pass, and since our program is then restarted and we have no other memory except the current state of ai, we would not be able to distinguish those two initial states, but the end results for them must be different.

By the same argument, on the second pass where we go from right to left we keep a1 unchanged and write a1+a0 as the new value for a0, and so on. After three passes, we actually obtain the well-known algorithm to swap two values without using additional memory (note that + and - are the same thing modulo 2):

• a1=a1+a0
• a0=a1-a0
• a1=a1-a0

This means that we have applied the swap as needed. We could only do one thing for n=2, but this thing turned out to be exactly what we needed when w=3!

Now consider the case of higher n, but when the given permutation is the reverse permutation. The reverse permutation consists of independent swaps: we need to swap the 0th and the (n-1)-th bits, the 1st and the (n-2)-th, and so on. Therefore we can simply apply the above trick for swapping a pair for all of those swaps, and do it in parallel during the same 3 passes, therefore solving this case with w=3 as well.

We can do the same for any permutation that consists of independent swaps — in other words for any permutation of order 2. But how to handle the general case? It turns out that any permutation can be represented as a product of two permutations of order 2! To see how to do it, we can first notice that it suffices to represent a cycle of arbitrary length as such a product, as several cycles can be handled independently. We can then consider what happens when we multiply the following two permutations: the first permutation swaps the 0th and 1st elements, then the 2nd and 3rd elements, and so on; the second permutation keeps the 0th element in place, swaps the 1st and 2nd elements, the 3rd and 4th elements, and so on. It is not hard to see that every swap of the second permutation will swap two elements of different cycles, which means that those cycles will merge, which in turn means that in the end we will have one big cycle. The nodes along this cycle will not come in the order 0, 1, 2, ..., but it does not matter since we can renumber them arbitrarily to obtain a solution for any cycle.

This fact can be used to solve the general case with w=6 by applying each of the two permutations of order 2 using 3 passes. However, we can do one better and achieve w=5 if we notice that the last pass of applying the first permutation and the first pass of applying the second permutation can be merged into one. In order to see this, notice that we can make both of those passes go from left to right, and then each of them would find a new value for a certain bit using the old values of this bit and all previous bits; since our memory is not erased within one pass, we might as well compute the new value for that bit for the first pass of the second permutation using the values that would have been computed by the last pass of the first permutation instead, and write that one directly.

Going from w=5 to the optimal w=3 is a bit more technical, so I will not describe it in detail. To come up with my own solution for w=3 I relied on a more sophisticated version of the argument from the solution for n=2. After the second pass, we must leave the bits in such a state that the final state of each bit depends only on the state of this bit and the previous bits (since the third pass goes from left to right). And there are actually not too many different things that we can do during the first pass if we need to be able to leave the bits in such a state after the second pass. You can also check out alernative approaches in this Codeforces comment, or in the editorial

The second problem came from Codeforces: you are given an empty n times m grid (4 <= n, m <= 10). You need to write all integers from 1 to nm exactly once in the grid. You will then play the following game on this grid as the second player and need to always win. The first player takes any cell of the grid for themselves. Then the second player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves. Then the first player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves, and so on until all cells are taken. The second player wins if the sum of the numbers of the cells they have in the end is smaller than the sum of the numbers of the cells of the first player.

I did not solve this problem, but it turned out that I was on the right track :) On the left you can see the picture I had in my notes during the contest, where I placed 1, 2 and 3, and was trying to prove that if the starting player takes one of them, I can always take the remaining two for myself. On the right you can see the picture from the excellent editorial, to which I refer you for the actual solution, as I do not have much to add :)

Thanks for reading, and check back for this week's summary!