*n*bits (each 0 or 1)

*a*that is unknown to you. In addition, there is a permutation

_{i}*p*of size

_{j}*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*. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation

_{pi}*p*, print an integer

_{j}*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*again, and then it will read the sequence

_{j}*a*from left to right, and after reading the

_{i}*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*again, and then read

_{j}*a*(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

_{i}*w*-th run is over, we must have

*b*=

_{i}*a*, where

_{pi}*b*is the final state of the sequence, and

_{i}*a*is the original state of the sequence.

_{i}*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?

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?

## No comments:

## Post a Comment