Thursday, November 14, 2019

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 a1=1, a2=1, a3=0, a4=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!

Wednesday, November 13, 2019

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 pi, such that for every arc i->j with weight wij its adjusted weight wij+pj-pi is non-negative.

Applying wij+pj-pi>=0 to the non-removable zero-weight edges, we see that pi+1>=pi, 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, wij+pj-pi>=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, wij+pj-pi>=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(n2) 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(n3) transitions, and the running time can also be O(n3) 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 screencastanalysis). 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!

Monday, October 28, 2019

A congratulations week

TopCoder SRM 762 was the first contest of Jul 1 - Jul 7 week (problems, results, top 5 on the left). There were only three correct submissions for the hard problem, and tourist has spent just 35 minutes on it compared to Egor's and uwi's 50, therefore his first place was clear. Well done to all three!

Codeforces Round 572 followed on Friday (problems, results, top 5 on the left, analysis). Um_nik has completely dominated the field, completing all problems with half an hour remaining. Congratulations on the great performance!

Finally, TopCoder Open 2019 Round 3A wrapped up the week on Saturday (problems, results, top 5 on the left, parallel round resultsmy screencast). yutaka1999's times on all problems were quite good but not the fastest after the coding phase, but many other high-scoring competitors have failed either the challenge or the system test phase, and Yuta emerged in clear first place. Well done!

Thanks for reading, and check back for more :)