A respects week

Codeforces Global Round 9 was the main event of the Jun 29 - Jul 5 week (problems, results, top 5 on the left, analysis). The problemsetters warned us to read all problems before spending too much time on one of them, and yet my story is quite similar to Radewoosh's: I've spent 1.5 hours on problem F, and then solved problems G and H immediately after reading their problem statements, but lacked 5 minutes to finish the solution to H (it passed in practice). tourist, on the other hand, just didn't get stuck and got the first place with some margin. Well done!

Let me highlight a (relatively) easier problem this time, problem E: you are given an array a with at most 1000 elements. Then we write down all pairs of positions that form an inversion: pairs (u,v) such that u<v and a_u>a_v, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once). Can you see a way to achieve this?

Thanks for reading, and check back for more!

A tube week

There were no contests that I'd like to mention during the Jun 22 - Jun 28 week, so let's come back to the Codeforces problem from the previous summary: there are n lamps arranged in a circle (n<=1000), and two players are turning them on and off. Initially all lamps are off. The first player starts by turning on any subset of lamps that are off. Let the number of lamps turned on by the first player be k. Then the second player chooses any subset of k consecutive lamps (along the circle), and turns off all lamps in that subset that were on. Then the first player can turn on any subset of lamps that are off again, and so on. The first player can choose to finish the game instead of making their turn. The goal of the first player is to maximize the number of lamps that are on when the game is finished (and they have to finish the game at some point, they can't continue forever), and the second player tries to minimize that number. What is the optimal strategy for the first player?

Let's call a move of the first player followed by a move of the second player one step. Since the second player always turns off at most the same number of lamps that the first player has just turned on, the number of lamps never decreases after a step. We can further classify the steps into two types: the ones that increase the number of lamps that are on, and the ones that keep it unchanged.

Consider a game that was played optimally by both players, and let's focus on the last increasing step of that game. Suppose the first player has turned k lamps on during their move. If there were k consecutive lamps that were on after that, the second player could have turned them all off, and make the step not increasing. Therefore in order to make an increasing step, the first player needs to keep at least one lamp off among each k consecutive lamps. Therefore the maximum number of lamps that are on after his move is n-ceil(n/k), and then the second player will turn k-1 lamps off in the worst case, so the number of lamps that will be on after this step will be n-ceil(n/k)-k+1.

The first player can pick the value of k that maximizes n-ceil(n/k)-k+1 and achieve such score in the following way: choose any set of lamps of size n-ceil(n/k) that does not have k consecutive lamps, and keep turning on any k lamps from this set that are off. This will guarantee that each step will be increasing until we reach the score of n-ceil(n/k)-k+1.

The second player can guarantee that the score never exceeds max(n-ceil(n/k)-k+1) by simply turning off the maximum number of lamps that they can at each turn, which will make sure that whenever a step is increasing and the first player turned on k lamps, the score after this step will not exceed n-ceil(n/k)-k+1. This is not an entirely formal proof, but the remaining details are left to the reader :)

Thanks for reading, and check back for more!