Saturday, April 14, 2018

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 Ak=0 (modulo p), or report that it does not exist. It is relatively straightforward to do in O(n3*log(n)), but your solution needs to run in O(n3).

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 [ai,bi], and know that each of those segments contains at least one 0. In a similar vein, you're also given up to 100000 segments [ci,di], and know that each of those segments contains at least one 1. How many such binary strings exist, modulo 109+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 pj — the number of ways to choose the first j characters ending with a block of 0s, and qj — the number of ways to choose the first j characters ending with a block of 1s. To compute pj, we iterate over the ending point t of previous block of 1s, and we see that pj is a sum of qt. t must be at most j-1, and at least max(ci) over all i such that di<=j, to make sure that no [ci,di] segment only contains 0s. We can compute qj in a symmetric way.

Since max(ci) only ever increases as we increase j, we can maintain a sliding window of qt'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 pj and qj, and now are looking to find pj+1 and qj+1 while the left boundaries of our summation max(ai) and max(ci) stay the same. pj+1 is the same sum as pj, but with extra term qadded, so pj+1=pj+qj. Similarly, qj+1=pj+qj 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 pj and qj, 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!