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!