A Kotlin week

Codeforces hosted the first round of its Kotlin Heroes series during the May 27 - Jun 2 week (problems, results, top 5 on the left, my screencast, analysis). All solutions needed to be in Kotlin, and there were two main approaches: either writing in Kotlin from scratch, or writing in Java and using IntelliJ IDEA's built-in Java-to-Kotlin converter. In the top 5, myself and abacabadabacaba have used the converter approach. Some level of Kotlin understanding was still required for us, as the converter did not work flawlessly all the time. If you're interested in details, the screencast should demonstrate some of the issues I had to overcome :)

TopCoder SRM 759 followed a day later (problems, results, top 5 on the left, analysis). Just tourist and ecnerwal were able to solve all three problems, and 200 challenge points gave tourist a clear edge :) Congratulations to both!

The hard problem in this round required a few nice observations to make the dynamic programming fast enough. 500 table tennis players are sitting in a row. Repeatedly, we do the following: pick two adjacent players uniformly at random, play a game between them, and eliminate the player who lost, until there is only one player left. Each player has a rating r_i, and the probability that the i-th player wins against the j-th player is r_i/(r_i+r_j). What is the probability that the given player wins the entire tournament?

Codeforces Global Round 3 took place on Saturday (problems, results, top 5 on the left, my screencast, analysis). I was able to squeeze in a randomized heuristic solution for G, but spent quite a bit more time doing so than mnbvmar and tourist spent implementing the correct solution :) Congratulations for mnbvmar for the win!

Problem F in this round was very easy for me, but quite difficult and with a lot of system test failures overall: you have 300000 objects, with each object having two attributes: a value between -10⁹ and 10⁹, and a nonzero mask with at most 62 bits. Given another mask s, we compute f(s) as the sum of values of objects which have an even number of shared bits between their mask and s minus the sum of values of objects which have an odd number of shared bits between their mask and s. f(0), which is just the sum of all values, is not equal to zero. Your goal is to find any s such that f(0)*f(s) is negative, in other words to flip the sign of the sum. Can you see how to do it?

AtCoder Grand Contest 034 was the last event of this week (problems, results, top 5 on the left, my screencast, analysis). Problem D in this round was not so hard to reduce to min-cost-flow, but the hard part was to make sure that the network has a linear number of edges instead of quadratic. Some people managed to skip the hard part by using a very efficient flow implementation :)

Here's what the problem was about: you are given at most 1000 groups of red balls, and at most 1000 groups of blue balls. Each group contains at most 10 balls in the same location, and the coordinates of those locations are integers not exceeding 10⁹ by absolute value. The total number of red balls is equal to the total number of blue balls. Consider all possible matchings where each red ball is matched with one blue ball and vice versa. You need to find the maximum sum of Manhattan distances between the matched balls. Can you see how to make the network linear?

In my previous summary, I have mentioned an Open Cup problem: you have n (n<=50) cells arranged in a circle and a token in one of the cells. Then you repeatedly do the following: pick a number uniformly at random from the set {-2,-1,+1,+2}, and move the token this many cells along the circle (positive numbers corresponding to the clockwise movement, and negative to the counter-clockwise one). What is the expected number of moves before the token visits the same cell twice? The cells that are passed through in the middle of a -2/+2 move do not count as being visited.

The most straightforward dynamic programming solution would just remember the set of already visited cells and the position of the token, but there are too many possible combinations. The first optimization we can make is to avoid storing the position of the token, instead rotating the set so that the token is always in a fixed position.

This does not make the solution fast enough, so we need another key optimization idea: notice that we can never jump over two consecutive visited cells, so if we find the closest such pair to the left and to the right of the token, everything outside those does not really matter, and we can assume that all outside cells are visited as well, for example replacing the state 0101110T001011010 with 1111110T001011111.

Now the number of reachable states is actually polynomial, since outside the all-one part we will always have a prefix/suffix of alternating 0s and 1s, and maybe some 0s in between those. We could try to encode them effectively using that observation, but we don't actually need to: we can still represent them as bitmasks, and just rely on the fact that the number of reachable bitmasks will be small. Since the largest testcase is obvious, we can run our solution on it to make sure it's fast enough before submitting it. And even if it weren't, we could precalculate the answers.

Thanks for reading, and check back for more!