A binary block week

The Mar 5 - Mar 11 week had two Codeforces rounds. Round 469 took place on Friday (problems, results, top 5 on the left, analysis). Since I'm writing this post on the plane to Beijing for ICPC 2018 World Finals, I can't help but look at the scoreboard from the ICPC angle: the winner dotorya will be participating in the Seoul NU team, and the third-placed Syloviaely is part of the host Peking U team. Congratulations on the great Codeforces result, and best of luck in the World Finals!

VK Cup 2018 Round 1 took place one day later (problems, results, top 5 on the left, parallel round results, analysis). Team VK Cup 24329020081766400008 from Saratov was already among the fastest in coding, but managed to stand out thanks to the challenges, even despite their solution for the hardest problem failing systests. Well done!

Finally, after a week's hiatus the Open Cup came back for another five-week marathon which started with the Grand Prix of Baltic (problems, results, top 5 on the left). Team Past Glory was not as fast as t.me/umnik_team, but they were more accurate, and thus won by a few penalty minutes. Congratulations to both teams on the great performance!

Problem E had a very simple statement and a very cute solution. You are given a n times n matrix A of integers modulo a prime number p. You need to find the smallest positive integer k such that A^k=0 (modulo p), or report that it does not exist. It is relatively straightforward to do in O(n³*log(n)), but your solution needs to run in O(n³).

In my previous summary, I have mentioned a difficult Codeforces problem: consider an unknown binary string of length k, k is up to a billion. You're given up to 100000 segments [a_i,b_i], and know that each of those segments contains at least one 0. In a similar vein, you're also given up to 100000 segments [c_i,d_i], and know that each of those segments contains at least one 1. How many such binary strings exist, modulo 10⁹+7?

First, how can we approach this problem if we forget that k is very big? Let's split our string into blocks of 0s and 1s, and compute p_j — the number of ways to choose the first j characters ending with a block of 0s, and q_j — the number of ways to choose the first j characters ending with a block of 1s. To compute p_j, we iterate over the ending point t of previous block of 1s, and we see that p_j is a sum of q_t. t must be at most j-1, and at least max(c_i) over all i such that d_i<=j, to make sure that no [c_i,d_i] segment only contains 0s. We can compute q_j in a symmetric way.

Since max(c_i) only ever increases as we increase j, we can maintain a sliding window of q_t's together with their sum, and thus obtain a O(k) amortized time solution.

Now let's look more closely at this process in case we don't encounter any new segment endpoints. Suppose we have just found p_j and q_j, and now are looking to find p_j+1 and q_j+1 while the left boundaries of our summation max(a_i) and max(c_i) stay the same. p_j+1 is the same sum as p_j, but with extra term q_j added, so p_j+1=p_j+q_j. Similarly, q_j+1=p_j+q_j as well. So we got two equal numbers at (j+1)-th step, and on each further step these numbers will just keep multiplying by two until we encounter a new segment endpoint and summation left boundaries change.

This allows to obtain a O(nlogn) solution, where n is the number of segments: instead of computing all individual values of p_j and q_j, we will split our string into blocks between the segment endpoints, and in each block we will only store the first number, and all following numbers will be 2x the previous number. The formula for the sum of a geometric progression allows to handle such segments quickly.

Thanks for reading, and check back soon for more summaries and for some ICPC blogging!