A Radewoosh week

Codeforces did not take any breaks, and held two contests in the first week of 2019. The first one was appropriately named "Hello 2019" (problems, results, top 5 on the left, my screencast, analysis). V--o_o--V took a gamble and started with problem G which looks doable on the surface but takes quite a lot of time to get right. This was not optimal in terms of the number of points, but it or the five incorrect attempts did not matter in the end as nobody else was able to solve all problems. Congratulations to V--o_o--V!

I was actually quite close to getting all problems, as I've fixed the last bug in my solution for H just 30 seconds after the end of the contest (you can still see it on the screencast). And given the unexpectedly low point total of V--o_o--V, that would be enough for the first place :)

Problem E mostly relied on a well-known theorem, but had an interesting twist on top of it: you are given a permutation of size n <= 100000, and you need to split it into subsequences such that each subsequence is either monotonically decreasing or monotonically increasing. The number of subsequences needs to be small, but does not need to be minimal. More precisely, your solution should have the optimal worst case performance for any given n: the number of subsequences should not exceed the maximum number of subsequences necessary for any permutation of size n.

Codeforces Round 530 took place one day later (problems, results, top 5 on the left, my screencast, analysis so far partially in Russian). Problem E required a lot of careful implementation, and the speed of that implementation was the deciding factor in the standings. Of the four contestants finishing before the round ended, Radewoosh was the fastest. Well done!

I found problem B quite cute: you are given a nxm matrix such that n*m<=300000, with one character from the set A, C, G or T in each cell. You need to change as few characters as possible (to other characters from the set) in such a way that each 2x2 submatrix has all four different characters. Can you see a way?

In my previous summary, I've mentioned a couple of problems. The first one came from AtCoder: you are given a number k which is at most 1000. You need to come up with any nxn toroidal grid (the first row is adjacent to the last row, and the first column is adjacent to the last column), where you choose the number n but it must be at most 500, such that each cell of the grid is colored with one of the k colors, each color is used at least once, and for all pairs of colors i and j all cells with color i must have the same number of neighbors with color j.

During the round, I could only come up with approaches that produce a number of colors that is either smaller than n, or divisible by n. At some point I had an idea to write a backtracking solution that would find me any solution that does not have these properties, hoping that would help come up with its generalization. In retrospect, that might have done it, as the following approach (which seems to be the only one that works) does look recognizable from one example: let's pick an even n, and split the grid into n (toroidal) diagonals. For each diagonal, we either color it with one color, or with two alternating colors, thus making it possible to get any number of colors between n and 2n. Since each element of a diagonal has exactly two neighbors from each neighboring diagonal, the required properties hold.

The other problem came from Codeforces. I've cited a simplified version of the statement: there is a pile with n<=200000 stones, and two players are playing Nim with a fixed set of possible moves a₁, a₂, ..., a_k: in each turn a player can take a number of stones that is equal to one of the a_i, and the player who can't make a move loses. Your goal is to find the nimbers for all values of n between 1 and 200000.

I have forgot to mention one important additional property in this simplification: that the nimbers are guaranteed to be not too big (below 100), which is actually important for the solution below to be fast — sorry for that!

Let's put all possible moves in one bitmask m, and also store a bitmask for each nimber value that represents which pile sizes have a move to a position with that nimber value. Those bitmasks start as empty. In order to determine the nimber for the next pile size, we go through those bitmasks until we find one that has a zero in the corresponding position. Then we need to update the bitmasks for higher pile sizes, and the key trick is that we only need to update one of them: the one corresponding to the newly determined nimber, and the update is simply applying bitwise or with the move bitmask m shifted left by the current pile size. This means that the solution runs in O(n²/64+n*max_nimber) (I know, this is not a perfect use of the O-notation, but I hope you understand what I mean), which is fast enough.

Thanks for reading, and check back next week!