An Eliška week

EGOI 2024 in Veldhoven, the Netherlands was the main event of last week (problems, results, top 5 on the left, analysis). Eliška has won for the second time in a row, this time with an even more commanding margin — huge congratulations! She was one of the four girls (together with Lara, Vivienne and Anja) who has participated in all four EGOIs, but it seems that this was the last year for all of them. Nevertheless, the new stars are already there as well, with so many medalists having several EGOI years ahead of them. It is great to see that this wonderful new community has been built and thrives!

Just like last year, I was onsite as a task author, but my task did not end up being used in the contest. I really need to up my game and submit more and better problems next year :) Of the problems that did end up in the contest, I'd like to highlight problem D from the first day which had the unusual multirun format. There is a sequence of n bits (each 0 or 1) a_i that is unknown to you. In addition, there is a permutation p_j of size n that is known to you. Your goal is to apply this permutation to this sequence, in other words to construct the new sequence b_i=a_pi. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation p_j, print an integer w, and exit. It will then be executed w more times. On the first of those runs, it will read the run number (1) and the permutation p_j again, and then it will read the sequence a_i from left to right, and after reading the i-th bit, it has to write the new value for the i-th bit before reading the next one. After processing the n bits, your program must exit. On the second of those runs, it will read the run number (2) and p_j again, and then read a_i (potentially modified during the first run) from right to left, and it has to write the new value for the i-th bit before reading the previous one. On the third of those runs, it goes left to right again, and so on. After the w-th run is over, we must have b_i=a_pi, where b_i is the final state of the sequence, and a_i is the original state of the sequence.

To get the full score on this problem you must always have w<=3, but I find that solving for w<=5 (which would give 95 points out of 100) is more approachable and potentially more fun. As another hint, two of the subtasks in the problem were as follows:

• n=2
• the given permutation is a reverse permutation

Can you see how to move from those subtasks to a general solution with w<=5? 

Codeforces ran Pinely Round 4 on Sunday (problems, results, top 5 on the left, analysis). As Um_nik rightly points out, tourist has continued his amazing run of form, and is potentially one more win away from crossing the magical boundary of 4000. Very well done!

I also share Yui's sentiment: it is very cool and quite surprising that problems H and I can in fact be solved. During the contest, I did not manage to make any significant progress in both of them in about 1 hour and 15 minutes I had left after solving the first 7. On the other hand, the (nicely written!) editorial almost makes them look easy :)

If you have not checked out the editorial yet, you can try crack problem I yourself. The statement is quite simple and beautiful: 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.

Given that the first player can choose the starting cell arbitrarily, it seems quite hard to believe that the second player can have any advantage. Can you see the way?