A Geronimo week

The Mar 23 - Mar 29 week had two events on the weekend. TopCoder SRM 782 was the first one to go (problems, results, top 5 on the left, TCO stage 2 results, analysis). With about 30 seconds remaining in the challenge phase I've noticed that I need one more successful challenge for the first place, but I did not find any bugs. Therefore I decided to guess which solution is most likely to have a bug, and to challenge it with a large testcase that I prepared earlier. I was extremely lucky that this strategy worked, given that the solution I chose — Egor's 1000 — turned out to be the only remaining incorrect solution in the room at that point :)

Open Cup 2019-20 Grand Prix of Wroclaw took place on Sunday (results, top 5 on the left, analysis). Since Open Cup is a (multi-)onsite team contest, this required some big changes, as teams were asked to all participate online without even gathering a team together in one place, instead using audio/video conferencing and coordinating to use at most one computer at the same time. Team USA1 has been participating like this all season and therefore maybe had a slight edge over the competitors, winning by 11 problems to 10. Well done!

Team HDU-Coach in the second place is doing very well this season in general, however unlike other top teams their team members are not listed in the standings. Does anybody know their Codeforces handles, for example?

In my previous summary, I have mentioned an AtCoder problem: you are given a sequence of n<=10⁶ numbers, each number is 1, 2 or 3. Then, you create a new sequence of length n-1 by taking the absolute values of the differences between adjacent numbers. Then you create a new sequence of length n-2 from the sequence of length n-1 in the same way, and so on until there's just one number in the sequence. What will this number be?

First of all, it's convenient to subtract 1 from all numbers in the input so that we have 0, 1 and 2 — this will not change the differences.

Then, let's assume the input sequence contains just 0s and 1s. The absolute difference in this case is the same as addition modulo 2, so for example starting from five numbers a, b, c, d, e, we'll get: a+b, b+c, c+d, d+e; then a+2b+c, b+2c+d, c+2d+e; then a+3b+3c+d, b+3c+3d+e; and finally a+4b+6c+4d+e (everything modulo 2). We can now notice (and prove) that the coefficient next to the k-th input number is equal to C(k-1,n-1), and thanks to Lucas's theorem we know it's equal to 1 modulo 2 when (k-1)&(n-1)=k-1 (& is bitwise and), and to 0 modulo 2 otherwise, which allows us to solve this case by summing the input numbers multiplied by the corresponding coefficients.

What can we do if the input sequence also contains 2s? First of all, we can notice that if we declare that 0 and 2 are the same, then our operation is still equivalent to addition modulo 2! This allows us to determine if the final number is 1, or if it's 0/2. If it is 1, we're done, but how to decide between 0 and 2 in the other case?

It turns out that if the input sequence contains a 1, then the final number will never be 2. To see that, we can notice that if the sequence contains at least one 1, and at least one 0/2, then two of those will be adjacent, and therefore the next step will also contain at least one 1. So the only way to get rid of all 1s if there were any is to get a sequence with all numbers equal to 1, in which case all following steps will have all numbers equal to 0. In any case, if the input sequence contains at least one 1, the final number will always be a 0 or a 1, therefore the above approach solves this case.

The only remaining case is: the input sequence contains only 0s and 2s. In this case we can just divide all numbers by 2 to reduce the problem to the one with only 0s and 1s, solve it and then multiply its answer by 2.

I found it very enjoyable that such simple problem statement requires one to unwrap multiple layers to solve it, even if each layer by itself is not very hard.

Thanks for reading, and check back for more!