A second extremal week

The last week of March featured more contests from the regular platforms. First off, TopCoder SRM 732 took place very early on Friday (problems, results, top 5 on the left). Both the medium and the hard problem involved asymmetric games requiring quite some insight to solve, and thus only two contestants were able to solve each (top 4 in the table to the left). Congratulations to all four, and especially to pashka on the win!

Then AtCoder held its Grand Contest 022 on Saturday (problems, results, top 5 on the left, analysis). The contest had three relatively easy problems, and three very hard ones. Only a few contestants were able to solve one of the three (I couldn't solve any, for that matter), so it is extremely impressive that Um_nik got all three — huge congratulations on very well deserved victory!

Problem E was the most approachable of the three. Consider a string of 0s, 1s and ?s of odd length up to 300000. First, we need to replace each ? with a 0 or a 1. Then, we repeatedly do the following operation: take any 3 consecutive characters, and replace them with the most frequent character among them. For example, 001 is replaced with 0. In the end we end up with a string of length 1, and our goal is to get the string 1. How many ways are there to replace the ?s so that it's possible to get the 1 after all reductions?

And finally, Open Cup 2017-18 Grand Prix of Moscow on Sunday wrapped up the week, but its results have not yet been published.

In my previous summary, I have mentioned an Open Cup problem: you are given n points p₁, p₂, ..., p_n on the plane and q queries (n, q <= 100000). Each query is defined by two numbers a, b, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from a-th to b-th (from the list p_a, p_a+1, ..., p_b) except maybe one.

Assuming we forget about "except maybe one" part, we need to find the bounding box of a segment of points, which can be done by finding the leftmost, rightmost, topmost and bottom-most points using interval trees in O(n*log(n)).

Now we can notice that when the skipped point is not one of the four extremal points, then the bounding box does not change, so we need to check at most four possibilities for the skipped point. In order to be able to find extremal points after skipping one point, our interval trees will need hold two extremal points instead of one, but otherwise the solution stays the same.

Thanks for reading, and check back for more!

ACM ICPC 2018 World Finals stream on Twitch

We have figured out a working setup for our stream, so tune in to https://www.twitch.tv/petrmitrichev around 10:00 Beijing time tomorrow!

A group embedding week

VK Cup 2018 Round 2 took place during the The Mar 19 - Mar 25 week (problems, results, top 5 on the left, parallel round results, analysis). Team Нижний Магазин SU: BZ would be first by far even without solving the last problem, but getting all problems accepted in the final minutes of the contest was of course the icing on the cake. Congratulations!

Open Cup 2017-18 Grand Prix of America wrapped up that week (results, top 5 on the left, parallel round results), with another two World Finals favorites in top 5: SPb ITMO 1 and Moscow SU Red Panda. The first place, however, went to team Past Glory — once again thanks to their incredible accuracy. Congratulations!

Problem K in this round was quite educational, if a bit professional. You are given n points p₁, p₂, ..., p_n on the plane and q queries (n, q <= 100000). Each query is defined by two numbers a, b, and you need to print the size of the smallest square with sides parallel to coordinate axes that contains all points from a-th to b-th (from the list p_a, p_a+1, ..., p_b) except maybe one. Can you dissect this problem into standard pieces?

In my previous summary, I have mentioned a Yandex.Algorithm problem: you are given a string s with 100000 characters, each a, b or c. You must swap exactly two distinct letters to obtain a new string t. How many ways are there to do that in such a way that the string t is good? In this problem we define a good string somewhat similarly to a valid parentheses sequence: empty string is good, if a string u is good then the strings aua, bub, cuc are good as well, and if two strings u and v are good, then their concatenation uv is also good.

The key insight in this problem is to learn to check if a string is good easily. Let's pick a group and 3 elements of order 2 in it: aa=1, bb=1, cc=1. We will then map each string to the product of the corresponding elements of the group. We can see that any good string will map to 1. Moreover, if our group is general enough, in other words does not have any other non-derived products that are equal to 1 (or if such products are simply unlikely to be equal to 1), then the opposite is also true: when a string maps to 1, it is good. As an example group that works in this problem we can use the group of movements of 3D space that keep the origin fixed, where a, b and c correspond to reflections through three random planes passing through origin. This way, we obtain a compressed representation for a string of any length as a single 3x3 matrix (modulo some prime number, to avoid dealing with floating point).

We can then use the divide-and-conquer approach: we start by splitting our string in two in the middle, and consider the case where the two positions being swapped are in different halves. If we also try all 6 possibilities for the letters being swapped, we have a sub-problem of the following kind: we have two strings, and need to replace a single a with b in the first string, and a single b with a in the second string, so that after doing those replacements and concatenating the strings we get a good one.

We can compute the compressed representation of each candidate for the first half using prefix and suffix products, then compute the compressed representation of each candidate for the second half in the same way, and then for each representation of first half find its inverse element in the second half, thus processing the case where the swapped elements are in different halves in O(n).

In order to handle the case where both swapped elements are in the same half, we follow the divide-and-conquer approach and recursively execute the same algorithm for each half, with the only difference that the target product in each half we want to get is not 1, but rather the inverse of the product of the other half. This allows to complete the solution of the entire problem in O(n*log(n)).

Thanks for reading, and check back soon!

A favorites week

The Mar 12 - Mar 18 week started with Yandex.Algorithm Round 2 on Tuesday (problems with Yandex login, results, top 5 on the left, my screencast). The hardest problem A was left unsolved despite 78 attempts, and yet the actual implementation is quite straightforward once one gets the idea. You are given a string s with 100000 characters, each a, b or c. You must swap exactly two distinct letters to obtain a new string t. How many ways are there to do that in such a way that the string t is good? In this problem we define a good string somewhat similarly to a valid parentheses sequence: empty string is good, if a string u is good then the strings aua, bub, cuc are good as well, and if two strings u and v are good, then their concatenation uv is also good.

TopCoder SRM 731 took place on Saturday (problems, results, top 5 on the left). mjhun was the fastest during the coding phase, but Gassa was close enough to require just one successful challenge to climb into the first place. Congratulations to both of you!

Finally, the Open Cup 2017-18 Grand Prix of Belarus happened on Sunday (problems, results, top 5 on the left). Team Past Glory was once again the fastest — well done! This round also provided a World Finals prediction perspective, as there are two teams in the top 5 who will be competing in Beijing: Seoul NU and Peking U. This year's World Finals looks to be extremely competitive, with top teams like Seoul NU, Peking U, SPb ITMO, Moscow SU, Warsaw U all of comparable strength (did I miss a team that you think is one of the favorites to win? Sorry, and please share in comments!) I'm looking forward to the final showdown on Thursday!

In my previous summary, I have mentioned a cute Open Cup problem: 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, in O(n³).

The answer never exceeds n, which in very rough terms can be derived from looking at Jordan normal forms (is there a simpler argument?..), which enables the following O(n⁴) approach: just compute the first n powers of A. It can be sped up to O(n³*log(n)) by using binary search, since once a power of A is zero, all following powers are zero as well.

In order to speed it up to O(n³), we need to come up with a beautiful idea: instead of computing just A^k, we will compute A^k*v for some vector v of size n. In case A^k=0, then A^k*v=0 as well. It turns out the opposite is almost always true: A^k*v over all v defines a linear subspace, which has at least one dimension in case A^k is not zero, and thus we can just pick v randomly and the probability of A^k*v being zero will not exceed 1/p.

Since we can multiply a matrix by a vector in O(n²), we can compute v, A*v, A²*v, ..., Aⁿ*v in sequence in O(n³) overall.

Thanks for reading, and check back for more!

ACM ICPC 2018 World Finals stream

ACM ICPC 2018 World Finals take place this Thursday at 10:00 Beijing time (click for other timezones). Just like last year, we'll try to solve it in parallel with tourist and Endagorion, and stream the process, assuming the problems will be available for submission on Kattis.

I'm not yet sure if it's going to be on Youtube, which does not work well in China, or somewhere else. I will post an update here and in Twitter once we figure out the right setup. Stay tuned!

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!

Google Code Jam qualification - last chance

There's about 4 hours left in the Google Code Jam 2018 qualification round. There were some stability issues with the new system earlier in the day, but they seem to have been resolved, so now's your chance to join the Code Jam if you haven't already. As usual I'm setting some problems this year, and I hope you'll find them interesting!