A 2021 week

TopCoder Open 2020 Round 1B was the first round of this week (problems, results, top 5 on the left, parallel round results, analysis). This was the last chance to get into Round 2 for those who have not qualified yet, and the problemset was correspondingly even more on the easier side. It turned out that a nonzero score was enough to advance, so contestants were mostly competing against the problems instead of between themselves. In order to get the first place, however, one required a few successful challenges as well. jzd got three and won — congratulations!

Google Code Jam Round 1C followed on Saturday (problems, results, top 5 on the left). Just like in the TCO round, this was the last chance to get into Round 2, but the competition was more intense: one needed to solve at least the first two problems completely to advance, and do it in about one hour. Just half an hour was enough for all three problems for Rafbill and maroon, and Rafbill held to a 4-second edge to claim the win :) Well done!

Finally, Open Cup 2019-20 Grand Prix of Nanjing wrapped up the action (results, top 5 on the left, analysis). Team NNSU Almost Retired claimed their second win of the season and seem to be in great form — congratulations! It looks like they'll need to maintain the form for quite a bit longer, as ICPC 2020 World Finals got rescheduled to 2021. Team USA1 got 11 problems as well, but an enormous amount of incorrect attempts has ruined their penalty time.

Problem B was very easy for some teams, but we got stuck on it for the whole contest, only to come up with a solution right after the end :) It went like this: we have a string which is initially empty. Then we repeatedly add characters either to the beginning of the string, or to the end of the string, n times (n<=1000000). Then, we need to print n numbers: how many period lengths did the string have after each addition? A string s has a period length k if 1<=k<=length(s) and for each valid i s_i=s_i+k (note that under this definition the last repetition of a period may be incomplete). For example, the string ababa has 3 period lengths: 2, 4 and 5. Can you see the trick?

Thanks for reading, and check back next week!

A Lucas week

Codeforces Round 637 last week was declared unrated after the reference solution for problem E turned out to be incorrect, and the problem seemed to be unsolvable.

Therefore TopCoder SRM 784 was the first round that counted (problems, results, top 5 on the left, TCO qualification standings, analysis). The constructive hard problem required one to come up with a pattern, and some people did it much faster than others :) I could not come up with an explicit pattern myself, instead finding a pattern in row and column sums from solutions of small inputs, and finding the actual grid using max flow. This took me about 3 times longer than the fastest solutions to this problem, though, so I was out of contention for the top places. tourist was among the fastest solvers there, and he was also twice faster than me on each of the first two problems. Congratulations on the well-deserved victory!

Open Cup 2019-20 continued its non-stop return with the Grand Prix of Moscow (results, top 5 on the left, analysis). After the same 3 teams split the first 12 stages between them, we started getting new winners, and team japan02 is already the sixth team to win a stage this season. Congratulations on the superb performance!

In my previous summary, I have mentioned an Open Cup problem: you are given k (k<=200) distinct positive integers a_i (a_i<=10⁵). Consider all sequences of length n (n<=10¹⁸) with all elements equal to one of the given integers. Count the number of those sequences with the given sum s (s<=10¹⁸). Is that number odd or even?

Since we're asked about the answer modulo 2, a natural idea is to try and discard groups of sequences which have an even count. There are actually multiple ways to do that, but for us the most natural way was to notice that since the order of the numbers matters, we can count the number of different orderings for each multiset of n numbers that add up to s, and discard those multisets for which this number of orderings is even. When our multiset has c_i occurrences of the number a_i, this number of orderings is given by the multinomial coefficient: n!/(c₁!*c₂!*...*c_k!).

A quick Google query led us to this mathoverflow post, which tells that this coefficient is odd if and only if there is no carry when performing the addition c₁+c₂+...+c_k=n modulo 2. This, in turn, means that for each bit that is set in n, there must be exactly one c_i that has this bit set. Or, in other words, if the binary representation of n is 2^b₁+2^b₂+...+2^b_t, then we need to count the parity of the number of ways to take one of the a_i's 2^b₁ times, one of the a_i's 2^b₂ times (possibly the same one), and so on, so that the sum of all that is s.

I find it beautiful that there is a completely orthogonal argument that leads to exactly the same subproblem, obtained by noticing that the number of non-palindromic sequences is always even. You can find more details in this Codeforces comment.

Now, how to solve the subproblem? Given that s is up to 10¹⁸, it still seems to be a pretty tough instance of the knapsack problem. A naive approach would be to implement dynamic programming which counts the [parity of] the number of ways to reach every sum u<=s using the first i powers of two 2^b₁, 2^b₂, ..., 2^b_i, but the running time of that would be O(s*k*t), which is enormous.

However, we can notice that many states of that dynamic programming are actually useless! Suppose we're processing the powers of two in increasing order, and we have processed all powers of two up to but not including 2^b_i. Then everything that we will add later will be divisible by 2^b_i. Therefore, only the states that are equal to s modulo 2^b_i can contribute to the final answer. On the other hand, our current sum will not exceed m*(1+2+...+2^b_i-1)<m*2^b_i, where m is the maximum of a_i. So there are at most m possible sums with the given remainder modulo 2^b_i, therefore our new solution runs in time O(m*k*t).

Since m=10⁵, k=200 and t=60, this is about one billion operations — somewhat borderline. It was fast enough for us during the contest, but in case it would not be, I was planning to optimize it further taking advantage of the fact that we only care about parity, and therefore can use bitsets to represent our dynamic programming arrays and do operations on them.

Thanks for reading, and check back for this week's summary!