A mafia week

The Sep 2 - Sep 8 week had two Codeforces rounds, starting with Codeforces Round 583 (problems, results, top 5 on the left, analysis). wxhtxdy solved all problems with just 3 minutes remaining, under pressure from Radewoosh who kept submitting the last problem for the last 20 minutes of the contest but still couldn't make it work. Congratulations to wxhtxdy!

The second Codeforces round was called Kotlin Heroes: Episode 2 (problems, results, top 5 on the left, analysis). tourist, abacabadabacaba and Benq solved everything, but tourist was a whole 40 minutes faster. Well done!

Finally, the 2019-20 season of the Open Cup started with the Grand Prix of Kazan (problems, results, top 5 on the left). Team Polish Mafia showed how to come back as a veteran team in style, winning the contest by a whole problem. Congratulations, and looking forward to competing against you in the future rounds!

Thanks for reading, and check back for more.

A Petrozavodsk week

There were no major public contests during the Aug 26 - Sep 1 week, in part because many top ICPC teams were busy at the Petrozavodsk training camp (overall standings, top 5 on the left), which traditionally kicks off the new ICPC season. The results showed that while NNSU team looks pretty dominant in the renamed Northern Eurasia region, Seoul NU team could pretty much keep up with them, setting us up for an exciting season!

Incidentally, the Northern Eurasia Finals take place tomorrow, tune in to the broadcast, or try your luck at the same problemset in the Codeforces mirror :)

Thanks for reading, and check back for more.

A regular week

The Aug 19 - Aug 25 week had TopCoder SRM 765 (problems, results, top 5 on the left, my screencast). I've spent quite a lot of time on each of the first two problems, but managed to recoup those losses by challenging a lot of solutions to the easy problem, which required a lot of accuracy when coding and ended up having just 20% success rate.

Codeforces hosted a round called "Manthan, Codefest 19" (problems, results, top 5 on the left, analysis). Nobody except tourist could get the hardest problem accepted, and therefore the challenge fight was only for the second place. Congratulations to Gennady on the win!

In the previous summary, I have mentioned an AtCoder problem: you are given a n times m grid (n, m <= 100), containing each number between 1 and nm once. Your goal is to sort the grid in row-major order in three steps. In the first step, you can rearrange the numbers within each row arbitrarily. In the second step, you can rearrange the numbers within each column arbitrarily. In the third step, you can rearrange the numbers within each row again.

Before the third step, we need each row to contain the numbers it should have in the end, in any order. Let's color numbers in n colors, such that all numbers that end up in the same row have the same color. Then before the first step we must have all numbers of one color in the corresponding row.

This means that before the second step, each column must have exactly one number of each color. In the first step, we are rearranging the rows arbitrarily, so let's assume that we're filling columns one by one, so every time we need to take one from the remaining colors in each row in such a way that we get one of each color.

This subproblem is a matching one: we can make a bipartite graph where the left part contains rows, the right part contains colors, and there's an edge for each number in the initial grid. Since this graph is regular, it has a matching, and moreover it keeps being regular after we remove all edges of a matching, so we can just repeat this process m times to split the entire graph into n matchings, which gives us the necessary rearrangement of numbers for the first step.

Thanks for reading, and check back for more!

A dragon week

All contests during the Aug 12 - Aug 18 week took place on the weekend. AtCoder Grand Contest 037 was the first (problems, results, top 5 on the left, my screencast, analysis). I was quite fast in solving the harder problems in this round, but got stuck for 25 minutes in the supposedly easy problem B, allowing apiad and Um_nik to take the first two spots. Well done!

Problem D in this round was very nice: you are given a n times m grid (n, m <= 100), containing each number between 1 and nm once. Your goal is to sort the grid in row-major order in three steps. In the first step, you can rearrange the numbers within each row arbitrarily. In the second step, you can rearrange the numbers within each column arbitrarily. In the third step, you can rearrange the numbers within each row again. Can you see why this is always enough, and how to actually find one way to do it?

Just a couple of hours later, TopCoder hosted the TCO19 Wildcard Round (problems, results, top 5 on the left, parallel round results). Despite failing the hard problem for a not very good reason, xudyh was still much faster than everybody else and qualified to the onsite finals together with uwi. Congratulations to both!

Codeforces Round 580 wrapped up the week (problems, results, top 5 on the left, analysis). TLE went for problem F while skipping some easier problems, and this turned out to be the right approach as he had much more points in the end. Well done!

In the previous summary, I have mentioned my Code Jam problem: there are several kings on an infinite chessboard. You don't know neither the number nor the locations of the kings, only that there are at most 10 and their coordinates are at most a million in absolute value. You can send at most 1000 requests, in each request you choose a cell on the chessboard and are told the sum of distances between this cell and the locations of the kings. The distance between two cells (a,b) and (c,d) for a king is max(abs(a-c),abs(b-d)). Your goal is to learn to answer such requests yourself: after you've done sending requests, the judging system will in turn send you 1000 such requests, and for each request you need to reply with the sum of distances from the locations of the kings to the request location.

The solution has two main parts. First, we need to notice that the distance metric used in this problem, the Chebyshev distance, is actually equivalent to the Manhattan distance if we make a substitution x'=x+y, y'=x-y, so it is enough to solve the problem for the Manhattan distance function: abs(a-c)+abs(b-d).

Now, suppose we send two requests: (a,b) and (a+1,b). The difference between the answers will tell us the difference between the number of points to with x>=a+1 and the number of points with x<=a. If we also know the total number of points, this allows us to tell how many points have x<=a, and we can find the total number of points by using this with a very large value of a.

We can then use the binary search on a using the "the number of points that have x<=a is at least i" predicate to find the i-th x-coordinate, and by repeating this for each i we can find all x-coordinates. We can find all y-coordinates in the same fashion.

However, we don't actually know how do the x-coordinates correspond to the y-coordinates, what are we going to do about that? It turns out that we don't need to know: the coordinates are summed independently in the abs(a-c)+abs(b-d) formula, so just knowing all coordinates is enough to be able to answer the requests! Moreover, the same argument shows that it's actually impossible to determine how the x-coordinates match the y-coordinates from such requests :)

There is one more technical complication arising from the fact that after rotating by 45 degrees we can no longer send arbitrary requests in the new coordinate system, only those where x and y have the same parity, so we can't actually send (a,b) and (a+1,b). However, we can fix that by using a very large b and sending (a,b) and (a+1,b+1) instead. The contribution from y to this difference will always be equal to the total number of points, and we can just subtract that.

I have also mentioned a TopCoder problem: given four squares that sum to an even number, find four squares that sum to half that number.

My approach to solving this problem was googling, as it seemed like it should be some well-known trick. And indeed after playing with keywords a bit I stumbled upon Euler's four-square identity. Substituting a₁=1, a₂=1, a₃=0, a₄=0 we get a very simple system of equations to solve.

Thanks for reading, and check back for more!

A six-in-a-row week

Google Code Jam 2019 Final Round was the main event of the Aug 5 - Aug 11 week (problems, results, top 5 on the left). There was a lot of movement at the top of the scoreboard during the round, since we did not know which submissions were solving just the visible input, and which tried to get both. After the dust had settled, things were much less suprising :) Gennady has won it for the 6th time in a row, incredible!

I have prepared the easiest problem in this round, Board Meeting: there are several kings on an infinite chessboard. You don't know neither the number nor the locations of the kings, only that there are at most 10 and their coordinates are at most a million in absolute value. You can send at most 1000 requests, in each request you choose a cell on the chessboard and are told the sum of distances between this cell and the locations of the kings. The distance between two cells (a,b) and (c,d) for a king is max(abs(a-c),abs(b-d)). Your goal is to learn to answer such requests yourself: after you've done sending requests, the judging system will in turn send you 1000 such requests, and for each request you need to reply with the sum of distances from the locations of the kings to the request location.

Can you see how to solve the problem, and why did we use such elaborate two-phase process instead of just asking to determine the locations of the kings?

TopCoder SRM 764 took place on the weekend (problems, results, top 5 on the left, my screencast, analysis). There were five problems instead of the usual three, and the divisions were combined. I can't say I enjoyed this format too much, but I did enjoy solving the cute mathematical puzzle that was the 500-point problem: given four squares that sum to an even number, find four squares that sum to half that number. Can you find a way to do it?

Thanks for reading, and check back for more!

A challenge week

Codeforces Round 576 was the first event of the Jul 29 - Aug 4 week (problems, results, top 5 on the left, analysis). Radewoosh and tourist had a great fight: first Radewoosh finished solving them problems a bit faster, then tourist found 3 successful challenges to move into the first place, but then Radewoosh found 3 challenges of his own and reclaimed the top spot. Congratulations to both!

TopCoder Open 2019 Round 4 then selected 10 more finalists (problems, results, top 10 on the left, parallel round results). Even though each problem has been solved, nobody was able to get all three, which led to quite dense standings and contestants had a lot to gain (or to lose) during the challenge phase. Egor has jumped into the top 10 after noticing a solution that never returns large answers in the easy problem. Congratulations to ACRush on the win, and to everybody who qualified!

Thanks for reading, and check back for more!

A Johnson's week

Facebook Hacker Cup 2019 Round 3 was the main event of the Jul 22 - Jul 28 week (problems, results, top 5 on the left, analysis). The problems ended up a bit on the easy side, as 45 contestants solved everything and only 25 of them qualified to the onsite finals. Radewoosh was quite a bit faster in doing so, claiming the first place. Well done!

In my previous summary, I have mentioned an AtCoder problem: consider a complete directed graph on n vertices (n<=500), with the cost of the arc from i to j (i ≠ j) equal to -1 if i < j, and to 1 if i > j. Let's add n-1 more arcs with weight 0, going from i to i+1 to each i (those arcs will be parallel to the corresponding -1 arcs). For each arc with weight -1 or 1 we are given the cost of removing it from the graph, and arcs with weight 0 are not removable. What is the minimum total cost to remove some arcs in such a way that there are no cycles of negative weight remaining?

The key solution idea is borrowed from the Johnson's algorithm: the absence of negative weight cycles is equivalent to the existence of a set of vertex weights p_i, such that for every arc i->j with weight w_ij its adjusted weight w_ij+p_j-p_i is non-negative.

Applying w_ij+p_j-p_i>=0 to the non-removable zero-weight edges, we see that p_i+1>=p_i, in other words the sequence of vertex weights is non-decreasing. Let's split all weights into groups of consecutive equal weights, without loss of generality we'll first have a group of weights equal to 0, then a group of weight equal to 1, then a group of weights equal to 2, and so on.

For arcs with weight -1, w_ij+p_j-p_i>=0 means that all such arcs that are within one group must be removed, but there are no other restrictions since for such arcs i<j.

For arcs with weight 1, w_ij+p_j-p_i>=0 means that all such arcs that go two or more groups to the left must be removed, and those within the same group or going one group to the left can be kept.

This allows to implement a dynamic programming solution with O(n²) states: what is the smallest total cost of "already decided" removed arcs if we have already assigned the weights to the first i vertices and the last group of equal weights encompasses the vertices from j to i? Our transitions go from state (i,j) to state (k,i+1), and since we know two consecutive groups in a transition, we can correctly decide which additional arcs need to be removed because of that. We have O(n³) transitions, and the running time can also be O(n³) if we keep some running sums to quickly recompute the total cost of arcs that must be removed.

Thanks for reading, and check back for more!

A week that blows minds

TopCoder SRM 763 has started the Jul 15 - Jul 21 competitive week (problems, results, top 5 on the left, analysis). ecnerwal has won the round, bringing his TCO point total for this stage to the respectable 4n, and thus qualifying for the onsite finals which takes place this week in Houston. Congratulations!

With the list of Round 4 and onsite qualifiers through the stage system decided, TopCoder Open 2019 Round 3B a day later offered the last chance to advance for many (problems, results, top 5 on the left, parallel round results). Only rickytheta was able to solve the hard problem successfully, even though their solution looks deceptively short. Congratulations on the well-deserved victory!

Codeforces Global Round 4 took place on Saturday (problems, results, top 5 on the left, analysis). ainta was 10 minutes faster than his competitors, but his 7 incorrect attempts on pretests meant that Radewoosh was still very close. ainta ended up in first place anyway, but Radewoosh has proven his point as well by "up-hacking" ainta's solution for G a few hours later. Well done to both!

AtCoder Grand Contest 036 was the last round of the week (problems, results, top 5 on the left, analysis). Um_nik was very fast in solving five out of six problems, but got stuck in the sixth, allowing snuke to overtake him with a couple of minutes remaining. Congratulations on the win!

Problem D received quite some praise: consider a complete directed graph on n vertices (n<=500), with the cost of the arc from i to j (i ≠ j) equal to -1 if i < j, and to 1 if i > j. Let's add n-1 more arcs with weight 0, going from i to i+1 to each i (those arcs will be parallel to the corresponding -1 arcs). For each arc with weight -1 or 1 we are given the cost of removing it from the graph, and arcs with weight 0 are not removable. What is the minimum total cost to remove some arcs in such a way that there are no cycles of negative weight remaining?

Quite unusually for this blog, I don't know the solution at the time of posting this, so I'm looking forward to trying to solve it myself!

Thanks for reading, and check back for the solution discussion!

A Develop week

Codeforces Round 573 was the first event of the Jul 8 - Jul 14 week (problems, results, top 5 on the left, analysis). Um_nik's solution for the last problem failed the system testing, but it did not matter in the end as he was good 16 minutes faster to solve the first five. Congratulations on the win!

Facebook Hacker Cup Online Round 2 followed a day later (problems, results, top 5 on the left, analysis). Um_nik was faster that everybody else once again, this time by 10 minutes, and Benq also collected his second top 5 appearance in two days. Well done to both!

Finally, AtCoder Grand Contest 035 wrapped up the week on Sunday (problems, results, top 5 on the left, my screencast, analysis). Only tourist and yutaka1999 could solve all problems, and apiad jumped to the third place submitting all his solutions after tourist was already done :) Congratulations!

I'm sorry for the second bare-bones summary in a row, but still check back for more!