An asymmetric week

The June 6 - June 12 week started with Codeforces Round 356 on Wednesday evening (problems, results, top 5 on the left, my screencast, analysis). It turned out to be impossible to solve all five problems in time, and thus the winning strategy involved skipping one of the easier problems to spare time for the hardest one.

Here is the problem I skipped: you are given a 500x500 grid where each cell is either black or white. You're given a number k, and are allowed to paint any kxk subgrid black (but only do that once). What's the size of the largest 4-connected black area you can get?

TopCoder SRM 692 took place very early on Friday (problems, results, top 5 on the left). In line with the current TopCoder tradition, just two people have managed to solve all three problems - congratulations Kriii and rng_58! Amusingly, all 3 top finishers were in one room, setting the stage for some challenge phase racing, but it didn't happen as the gaps were probably too big.

Yandex.Algorithm 2016 Round 2 on Friday was the second chance to score points towards qualifying for the top 25, which for most practical purposes is achieved by placing in the top 8 in one of the three rounds (problems requiring Yandex login, results, top 5 on the left, my screencast, analysis). Just like last week, the winning strategy turned out to be submitting everything in the open and racing to solve all problems, although one could place in the top 8 with any strategy. Congratulations to apiad on the victory!

The hardest problem in this round was quite beautiful geometry: you are given a convex polygon with 100000 sides. For each point strictly within the polygon we can define its asymmetry value: the maximum ratio of the two segments between this point and the boundary of the polygon along any line. For example, if that point is the center of symmetry of the polygon, its asymmetry value is 1. What is the smallest asymmetry value over all points inside the given polygon?

On Saturday Google Code Jam 2016 Online Round 3 started another big Code Jam weekend (problems, results, top 5 on the left, analysis). The competition was tough as only the top 25 would qualify for the onside round in New York. The right strategy turned out to involve skipping the large input of problem C, which was a tricky graph problem, and solving the purely mathematical problem D instead. Congratulations to xyz111 for the convincing victory that put all strategy considerations aside!

I was the author of problem B in this round, which went like this: you are given a rooted forest with at most 100 vertices, and consider all valid permutations of its vertices. A permutation of vertices is valid if every non-root vertex comes after its parent. Additionally, each vertex is assigned a letter, so each permutation induces a string when we write all those letters in the order of the permutation. Which fraction of valid permutations induce a string that contains the given substring? Your answer doesn't need to be very precise: an error of 0.03 is allowed.

Finally, Google Distributed Code Jam 2016 Online Round 2 wrapped up this busy week on Sunday (problems, results, top 5 on the left, analysis). The results were once again much more optimistic than last year's, suggesting that the contestants have mastered the new format. Congratulations to eatmore on the victory, and to everybody who qualified for the onsite round - looking forward to seeing you all in New York!

In the last week's summary I've described a hard TopCoder problem: you're given a 50x50 integer matrix with all values between 1 and 61. We pick two (possibly intersecting or even coinciding) submatrices uniformly at random. We find X - the least common multiple of all numbers in those two submatrices combined. Now we find the number Y - the smallest possible integer that does not divide X. What's the expected value of Y?

Since the matrix is just 50x50, we can solve the problem quite easily if only one submatrix is considered: we can just iterate over all possible submatrices and find the value of X and then Y for each of them. We can also notice that the answer is always a power of a prime, and can't exceed 64 (since 64 does not divide the least common multiple of all numbers between 1 and 61).

How do we go from one submatrix to two submatrices? This is where some advanced algorithms come into play. First, instead of finding the Y for each submatrix, let's find the number of submatrices which have each value of X. The number of possible lcms of some subset of values between 1 and 61 isn't very big. Using that information we can "sum over all divisors": find the number of submatrices with the value of X dividing each interesting value. Having done that, making a jump from one submatrix to two submatrices is super easy: the number of ways to pick two submatrices such that their values of X both divide the given value is just the square of such number for one submatrix. And finally, we need to undo the sum over all divisors step: knowing the number of pairs of submatrices with lcm that divides the given value, we compute the number of pairs with lcm that's equal to the given value. Now we just need to find the value of Y corresponding to each possible value of X.

How do we transition to sum over all divisors and back? This is done via dynamic programming, similar to the approaches described in my April post and in this recent Codeforces discussion. The tricky part here is that we don't operate on bitmasks, but rather on sequences of prime powers, which have more than two possible values for smaller primes. But the logic stays exactly the same: iterate over the prime first, and then over the number.

Thanks for reading, and check back soon for more!

Tweet