A Seattle week

Codeforces Round 684 warmed the contestants up before the remaining TCO20 rounds (problems, results, top 5 on the left, analysis). It was very close between the top 3, but ecnerwala has managed to avoid getting TLE on pretests in the last problem (and therefore having to spend more time speeding up the solution) and thus gained a very small edge. Congratulations on the first place!

The problemsetters received a lot of flak for the tight time limits. I have not solved the round myself, so I can't offer any firsthand experience. However, I found it quite impressive that three different coders were complaining about having to squeeze their solutions only to learn that the have bad asymptotic complexity (1, 2, 3 — thanks a lot to dorijanlendvaj for investigating those!). 

TCO20 Semifinal 2 followed next day (problems, results on the left, stream recording, analysis). The problems were significantly easier compared to Semifinal 1, with a relatively standard easy, a unique but not very hard medium, and a hard which was mostly solved by printing out the nimbers for small inputs and figuring out a pattern. Solving all three problems was enough to advance without any additional concerns; Egor and uwi solved two each, and Egor got ahead thanks to uwi's resubmit and his own successful challenge.

The top 4 from this round, together with the top 5 from the first round, competed in the TCO20 Final on Saturday (results on the left, stream recording). The problems were also not too difficult, and the competition came down to speed and random bugs, with less than 50 points separating many contestants at the top. tourist was just a tiny bit faster than everybody except Um_nik, and Um_nik's hard failed the system tests paving the way for the second TCO victory in a row for tourist — congratulations!

My contest was compromised early by two things: first, I had to resubmit the easy because I forgot to apply the modulo in one of the operations and therefore got an integer overflow. I guess it is a good lesson that tells me to start using a "modint" class that everybody else is using (which might be prohibitively slow in Java, but fine in C++). Second, after opening the medium I've immediately started to implement a brute force solution that computes the losing positions for small inputs, inspired by what happened in the semifinal. This strategy has backfired in this problem, as just a tiny bit of thinking on paper could've allowed me to achieve the same insight (that the losing positions are exactly the same as in the normal Nim) much quicker. I was therefore more than 100 points behind tourist and Um_nik after the first two problems.

I have managed to recover a big part of that gap on the hard problem, using the same strategy — implementing a brute force solution to see a pattern that enables a real solution (that all interesting states are the multiples of interesting 0/1 states), so one could say that this strategy worked out about even if one looks at the medium and hard combined.

I was therefore less than 50 points behind the first place, and needed just one successful challenge to win. I could not find any incorrect solutions, though, so I went with a last-second challenge on neal_wu's medium, which used an approach that was different from the approach that I and most others have taken, and which I hypothesized could TLE. It turned out it was fast enough, but I think it was definitely worth a try.

It is also interesting that the only incorrect solution in this round — Um_nik's hard — had a bug that I considered during the coding phase: it computed differences with the previous element instead of differences with the next element on every iteration. However, I was not sure if this bug can affect the results, so I've ran both variants of my solution on the biggest testcase (26, 10¹⁸), and they indeed gave the same output. I've thought that maybe the parity of n plays a role, so I've also tried (25, 10¹⁸) and the results were also the same, which got me completely convinced that the direction does not matter :) It turns out that both (24, 10¹⁸) and (26, 10¹⁷) have different outputs for those two solutions, so I was really close to discovering this and then checking all other solutions for this bug and challenging Um_nik successfully.

It is a bit more painful to come so close to winning in multiple ways (compared to for example 2019 where I did not really have any chance). Well, better luck next time, and congratulations to tourist once again!

In my previous summary, I have mentioned an AtCoder problem: you start with a sequence of n zeros (n<=50), and can apply the following four operations any number of times:

1. Add one to any number. This operation costs 1.
2. Subtract one from any number. This operation costs 1.
3. Add one to any contiguous segment of numbers. This operation costs C.
4. Subtract one from any contiguous segment of numbers. This operation costs C.

Now, you are given k (k<=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 10⁹. You need to find sum of the minimum costs to obtain the final state for each of kⁿ possible final states, modulo 10⁹+7.

Swistakk has explained my approach in this comment, so I will only clarify that reducing the problem to O(n*k) problems where each element is 0 or 1 is done by considering independent problems "how to add 1 to all numbers which must be >=1 in the end", "how to add 1 to all numbers which must be >=2 in the end" and so on.

November was quite packed with onsite finals that were in limbo given the circumstances, and ended up happening online close to the end of the year. Now most of them have passed (VK Cup, Yandex Cup, TopCoder Open), AtCoder WTF is most likely postponed further (judging from the list of upcoming contests here), so the only remaining big onsite-turned-online final (and my last chance to win something this year) is the Facebook Hacker Cup on December 5.

Thanks for reading, and check back next week!