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 10

After playing with the problem a bit, one can notice that it's helpful to separate the numbers into

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(

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

We can notice that among the above four numbers only

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 10

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 [

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!

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 10

^{15}, 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 10
^{15}.

^{5}, so the products of four numbers would end up being on the order of 10^{20}, 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

*a*for each row, a number_{i}*b*for each column, and put_{j}*a**_{i}*b*as the small numbers. Then the four small numbers surrounding a big number at position (_{j}*i*,*j*) are*a*_{i-1}**b*,_{j}*a*_{i+1}**b*,_{j}*a**_{i}*b*_{j-1}, and*a**_{i}*b*_{j+1}. They have quite a few common divisors, and their least common multiple is at most*a*_{i-1}**a*_{i}**a*_{i+1}**b*_{j-1}**b*_{j}**b*_{j+1}. If each*a*and_{i}*b*are on the order of 10_{j}^{3}(we have 500 rows + 500 columns), the product of six such numbers is on the order of 10^{18}, two orders of magnitude better than the naive approach but still not good enough.We can notice that among the above four numbers only

*a*and_{i}*b*were repeated, thus contributing to the reduction of the least common multiple, while_{j}*a*_{i-1},*a*_{i+1},*b*_{j-1}, and*b*_{j+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 10^{12}.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 10

^{15}, 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*.

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!

https://codeforces.com/blog/entry/63226

ReplyDeletePetr please help with Chelper settings

fun

ReplyDelete