Sunday, November 18, 2018

A fjzzq2002 week

TopCoder SRM 737 started the competitive Sep 17 - Sep 23 week (problems, results, top 5 on the left, analysis). There was quite a bit of challenge phase action at the top, but the final results mostly reflect the coding phase order. Congratulations to fjzzq2002 on the win!

Codeforces Round 511 followed (problems, results, top 5 on the left, analysis). eds467 was quite a bit slower than the rest of the top scorers on the first three problems, but managed to squeeze in problem E in 982 ms out of 1 second time limit and won. Well done!

Open Cup 2018-19 Grand Prix of SPb opened a busy Sunday (results, top 5 on the left). Team Past Glory has managed to solve Artur Riazanov's trademark "formal logic" problem B with a few minutes to go, cementing the first place they earned by solving other problems fast. Well done!

Finally, Codeforces Round 512 started even before the Open Cup ended (problems, results, top 5 on the left, analysis). This time fateice was actually able to solve the hardest problem E, but the five incorrect attempts they needed to pass pretests meant that they ended up below the competitors who solved problem D instead. Nevertheless, congratulations to fateice on solving E and to fjzzq2002 on the second victory of the week!

In my previous summary, I have mentioned an AtCoder problem: construct any 500 by 500 matrix of distinct positive integers up to 1015, such that if we take any two vertically or horizontally adjacent numbers a, b in the matrix and compute max(a,b) mod min(a,b) we always get the same non-zero result.

After playing with the problem a bit, one can notice that it's helpful to separate the numbers into big and small numbers (in any given pair of adjacent numbers, we call the dividend max(a,b) the big number, and the divisor min(a,b) the small number). If we put the big numbers into the black cells of a chessboard pattern, and the small numbers into the white cells of the same pattern, then in any pair of adjacent numbers one will be big and one will be small, just as we need.

Suppose we have chosen the small numbers. Then we can pick each big number as least common multiple of the adjacent small numbers plus one, and max(a,b) mod min(a,b) will always be equal to one. However, that's not yet a solution, as we need to balance two conflicting needs:
  • The small numbers need to be big enough to be distinct and for the resulting least common multiples to also be distinct.
  • The least common multiples, however, need to be small enough to fit under 1015
Naively picking the small numbers randomly, as they need to be distinct, would result in numbers on the order of 105, so the products of four numbers would end up being on the order of 1020, and the least common multiple of random numbers is not too unlikely to be equal to their product.

That means we need to find a way for the least common multiple of four numbers to be significantly smaller than their product, which means that they must have large common divisors. One way to achieve that is to pick a number ai for each row, a number bj for each column, and put ai*bj as the small numbers. Then the four small numbers surrounding a big number at position (i,j) are ai-1*bjai+1*bjai*bj-1, and ai*bj+1. They have quite a few common divisors, and their least common multiple is at most ai-1*ai*ai+1*bj-1*bj*bj+1. If each ai and bj are on the order of 103 (we have 500 rows + 500 columns), the product of six such numbers is on the order of 1018, two orders of magnitude better than the naive approach but still not good enough.

We can notice that among the above four numbers only ai and bj were repeated, thus contributing to the reduction of the least common multiple, while ai-1ai+1bj-1, and bj+1 only appeared once; this suggests a way to improve the solution: instead of assigning numbers to rows and columns, we need to assign them to diagonals containing small numbers. Each small number is at intersection of two diagonals, and we still have just 1000 diagonals in total. Since each big number is surrounded by only four diagonals, its least common multiple will be equal to a product of only four diagonal numbers, and thus be only on the order of 1012.

Since we need all products and least common multiples to be distinct, we can't actually assign numbers from 1 to 1000 to the diagonals, but we can take the first 1000 prime numbers, first 500 to diagonals of one kind, and next 500 for the other kind. The 1000-th prime number is 7919, the 500-th prime number is 3571, so our least common multiples will not exceed 7919*7919*3571*3571 which is less than 1015, and the diagonal numbers being distinct primes guarantees that all numbers in the matrix will be distinct, so we're done!

I have also mentioned an Open Cup problem in the previous summary: the judging program has a hidden string of 1000 digits, each either 0 or 1. In one query, you ask about a segment [l,r], and the judging program returns one of the two things, each with probability 50%:
  • the number u of 1s in the given segment
  • a uniformly chosen random integer between 0 and r-l+1 that is not equal to u.
In other words, with probability 50% the judging program gives an incorrect answer to your query. Your goal is to reconstruct the hidden string using at most 18000 queries, with one more important restriction: you are also not allowed to ask the same query twice.

This problem has been discussed quite extensively in the post-match discussion (this is problem E), including my own solution sketch, so I will refer interested readers there :)

Thanks for reading, and check back for more!



    Petr please help with Chelper settings