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 10¹⁵, 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¹⁵. 

Naively picking the small numbers randomly, as they need to be distinct, would result in numbers on the order of 10⁵, so the products of four numbers would end up being on the order of 10²⁰, 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_i for each row, a number b_j for each column, and put a_i*b_j as the small numbers. Then the four small numbers surrounding a big number at position (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_i and b_j are on the order of 10³ (we have 500 rows + 500 columns), the product of six such numbers is on the order of 10¹⁸, 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_i and b_j were repeated, thus contributing to the reduction of the least common multiple, while 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¹².

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¹⁵, 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!

An interactive week

AtCoder has returned with its Grand Contest 027 during the Sep 10 - Sep 16 week (problems, results, top 5 on the left, my screencast, analysis). There was a pretty tense fight for the second place with cospleermusora getting problem B accepted with less than a minute remaining; but tourist's victory was not really in doubt as he finished all problems with 25 minutes to spare. Congratulations to both!

I've really enjoyed solving problem D (the choice of constructive problems for this blog is becoming quite a pattern, isn't it?): you need to construct any 500 by 500 matrix of distinct positive integers up to 10¹⁵, 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.

The second Open Cup stage, the Grand Prix of Udmurtia, followed on Sunday (results, top 5 on the left). Team Havka-papstvo had dug themselves into a hole thanks to having a lot of incorrect attempts, then marvelously escaped with just 8 minutes remaining by solving the most difficult problem. Congratulations on the victory!

The Grand Prix of Udmurtia was a pioneer of interactive problems in the past, and this incarnation had four of those, too. Problem E went like this: 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.

In my previous summary, I have mentioned another problem with segment queries: there's a hidden integer between 1 and 10¹⁸. You can make queries, and in one query you give a segment [l,r] and the judging program tells you whether the hidden number lies in that segment. In case it does, and your segment has length 1 (l=r), you win. After each query, the hidden number can change a bit — more precisely, by at most k=10. These changes do not depend on your queries — in each testcase the sequence of changes is always the same. You have at most 4500 queries to win.

If the hidden number did not change, we would do a binary search: by querying the segment [1,m] we can compare the hidden number with m, so if we knew that our number was within some segment [a,b] before our query, we would narrow it down to either [a,m] or [m+1,b] after this query, and determine our number after at most ceil(log(10¹⁸))=60 queries.

When the hidden number changes under the hood, we need to adapt this approach: now we go from [a,b] to either [a-k,m+k] or [m+1-k,b+k]. When the segment [a,b] is big, this still divides it roughly in half, so we can proceed as before. However, when it becomes small, it will actually stop decreasing, and will never converge to a segment of length 1.

So we will do the following: when the length b-a+1 of the current segment is bigger than some boundary b, we will divide it in two using the above approach. And when it's b or less, we will just pick a random number c within the segment, and send [c,c] query. With probability of at least 1/b, we will win in this case. In case we don't, our candidate segment grows from [a,b] to [a-k,b+k], and we continue as before.

It's important to pick the right value of b: if it's too big, the probability of winning in each attempt of the second kind would be too low, and we won't always finish under 4500 queries. And if it's too small, it will take too many queries of the first kind between two queries of the second kind to reduce the segment size, and we would have too few queries of the second kind and also won't finish under 4500 queries. It's probably possible to find mathematically optimal value of b, or we can take a guess (I've used b=99 during the contest) and verify that it leads to good enough probability to finish under 4500 queries.

Thanks for reading, and check back for more!

A too difficult week

The Sep 3 - Sep 9 week started with Codeforces Round 507 on Wednesday (problems, results, top 5 on the left, my screencast, analysis). Once again the hardest problem was not solved during the round, and thus it all came down to the speed on the first four problems. Um_nik was considerably faster than the competition, finishing the four problems under an hour, and thus got a well-deserved first place. Congratulations!

Problem B in this round added a nice twist to a standard setting. This is an interactive problem in which you need to find a hidden integer between 1 and 10¹⁸. You can make queries, and in one query you give a segment [l, r] and the judging program tells you whether the hidden number lies in that segment. In case it does, and your segment has length 1 (l=r), you win. So far this is a classical binary search problem.

Here comes the twist: after each query, the hidden number can change a bit — more precisely, by at most 10. These changes do not depend on your queries — in each testcase the sequence of changes is always the same.

Can you see how to adapt the binary search for this setup? You have at most 4500 queries to win.

On Sunday, the new season of the Open Cup kicked off with the Grand Prix of Zhejiang (results, top 5 on the left). This will most likely be the most brutal contest of the year :) As I understand, this was the first "big" contest set by Yuhao Du, and the scoreboard reminds me of my own first Petrozavodsk contest, or my second TopCoder SRM. Team japan02 chose the solvable problems well and earned the victory with quite some margin. Well done!

Thanks for reading, and check back for more!

A plus four week

Codeforces hosted two rounds during the Aug 27 - Sep 2 week. AIM Tech Round 5 took place on Monday (problems, results, top 5 on the left, analysis). All problems were solvable this time for LHiC and OO0OOO00O0OOO0O00OOO0OO, but Mikhail was considerably faster of the two. Congratulations on the win!

Manthan, Codefest 18 was the second Codeforces round of the week (problems, results, top 5 on the left, analysis). The contest really came down to the wire, with the top three participants all completing the problem set with just a few minutes to go. Tourist was just a tiny bit faster with the easier problems, and thus earned the victory. Well done!

This week also marked the end of the summer Petrozavodsk training camp (results, top 5 on the left), the 9-contest event for top Russian and some other ICPC teams to practice before the new season. Given that the second-placed team in those standings is not actually going to participate in official ICPC contests this year, the gap between the first team (current ICPC World Champions) and the rest of the field is daunting, even though it's only August yet :)

In my previous summary, I have mentioned a TopCoder problem: you are given a 10x10 grid and can place at most 150 unit cubes onto it. A cube can be placed onto a cell of the grid, or on top of another cube. Given a number s between 1 and 500, you need to place the cubes in such a way that the surface area of the resulting figure (the total number of sides of the cubes that do not touch the grid or other cubes) is equal to s, or report that it's impossible.

The approach I will describe is a very typical one for such "constructive" problems. Suppose we have found the solution for some value of s. Let's take one extra cube and put it on top of an existing one. This will increase the surface by four (five new sides appear, and one old one is covered), so we'd get a solution for s+4. We can now apply the same trick to get a solution for s+8, s+12 and so on.

Since we spend one cube to increase the surface by 4, and 150*4 is significantly bigger than 500, we won't run out of cubes.

Now the only task that remains is to find out the smallest possible figure for each remainder of s modulo 4. This can be done by analyzing a few cases by hand: it turns out the minimum solvable s for each remainder are 8, 5, 10 and 11.

During the round I've initially discovered another induction idea: just placing a new cube on the grid in such a way that it's disconnected from the rest adds 5 to the surface, so I've tried to build a similar solution modulo 5. However, in that case we do run out of space as we can have at most 50 independent cubes on the 10x10 grid, and 50*5 is less than 500.

Thanks for reading, and check back for more!

A 250+ week

The Aug 20 - Aug 26 week was very calm compared to the previous ones, with just the TopCoder Open 2018 Online Wildcard Round on Saturday (problems, results, top 5 on the left, parallel round results, analysis). ACRush, Egor and Stonefeang were the only participants to solve all three problems, but ACRush and Egor were almost twice as fast in solving the hardest one, thus qualifying to the TCO onsite with a 250+ point margin. Well done!

The easy problem in this round was cute. You are given a 10x10 grid and can place at most 150 unit cubes onto it. A cube can be placed onto a cell of the grid, or on top of another cube. Given a number s between 1 and 500, you need to place the cubes in such a way that the surface area of the resulting figure (the total number of sides of the cubes that do not touch the grid or other cubes) is equal to s, or report that it's impossible.

Thanks for reading, and check back for more!

A birdie week

TopCoder SRM 736 started the Aug 13 - Aug 19 week (problems, results, top 5 on the left, my screencast, analysis). This was the first round under the new system in which one can qualify for the last online round and even to the onsite round of TopCoder Open 2019 by placing well in all SRMs in a quarter. rng_58 has claimed the early lead in that leaderboard by winning the SRM by less than one full point!

Codeforces then held two rounds based on VK Cup Finals problems, starting with Round 504 on Friday (problems, results, top 5 on the left, analysis). Just as in the official round, the hardest problem remained unsolved, but this time the winner was determined on challenges. ko_osaga found 9 opportunities and got a clear first place as the result. Well done!

Facebook Hacker Cup Round 3 on Saturday selected the 25 lucky finalists going to Menlo Park (problems, results, top 5 on the left, analysis). Xiao was quite a bit faster than the rest of the pack, qualifying to the onsite finals in style. Congratulations to Xiao and to all finalists!

Finally, another VK Cup-based Codeforces Round 505 wrapped up the week (problems, results, top 5 on the left, analysis). Once again the hardest problem remained unsolved, and once again it took solving all remaining problems plus finding a few challenges to earn a victory — and Swistakk did just that.

Thanks for reading, and check back for more!

A Toronto week

The Aug 6 - Aug 12 week was the Google Code Jam final week, onsite in Toronto. Distributed Code Jam 2018 Finals has opened the event on Thursday (problems, results, top 5 on the left, analysis). The contestants pursued wildly varying sets of problems, but in the end only Radewoosh, kevinsogo, tczajka and fagu could solve more than one full problem. Congratulations to all four, and especially to Radewoosh on the win!

The more traditional Code Jam 2018 Finals followed a day later (problems, results, top 5 on the left, analysis). Once again the sets of problems of the top contestants were very different, but this time only one participant managed to get three full problems: Gennady.Korotkevich. Congratulations on the victory!

Codeforces Round 503 took place on Saturday (problems, results, top 5 on the left, analysis). This time it was top four participants on four problems, with Marcin_smu barely claiming the first plce thanks to having only one pretests failure compared to Radewoosh's five. Well done!

Finally, VK Cup 2018 Final onsite in St Petersburg wrapped up the week on Sunday (problems, results, top 5 on the left). The heavy pre-round favorite "Нижний Магазин SU: BZ" was a lot faster than everybody else to solve the first five problems, but the system test failure meant that they had to settle for third. Team "120 Minutes Adventure" was more careful and thus claimed the victory. Congratulations!

Thanks for reading, and check back for more!

A unit week

The Jul 30 - Aug 5 competitive week started early with Codeforces Round 500 on Monday (problems, results, top 5 on the left, analysis). There were a few strategy options on the table, as the last two problems had the same point value and some people went for E and some for F: E turned out to be the right choice. Congratulations to Um_nik on the win!

Facebook Hacker Cup 2018 Round 2 followed on Saturday (problems, results, top 5 on the left, analysis, my screencast). Getting into the top 200 was the main goal, but there was some competition for the top spots as well, where Alex was a bit faster than everybody else. Well done!

In my previous summary, you are given a program for a drawing robot consisting of at most 250000 commands. Each command is either F "move forward by 1 unit, drawing a line", L "turn left by 90 degrees", or R "turn right by 90 degrees". The drawn polyline splits the plane into multiple regions, some finite, some infinite. Your goal is to return the list of the areas of all finite regions.

There's a somewhat well-known approach to the general problem of finding faces of a planar graph which is described in the official analysis. However, I've used the specifics of the problem and went with a different approach that I found less bug-prone.

Let's imagine the plane as a grid, split the polyline into unit segments, and look at the vertical unit segments for now. Every row of the plane will be split into two infinite blocks plus some finite k times 1 blocks by the vertical unit segments. The overall number of finite blocks is at most 250000.

Now let's put those blocks into a disjoint-set data structure, and merge the blocks that are adjacent vertically. In order to find the latter, we need to iterate over pairs of adjacent rows with two pointers, and not forget to take the horizontal polyline unit segments between those rows into account.

While the general planar graph algorithm is not harder than this one, I found that this approach allows to sidestep all corner cases, for example: what if there is a vertex of degree 1? What if there's more than one connected component of the polyline (not possible in this problem)?

Thanks for reading, and check back for more!