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!