An almost Rapid week

Last week was relatively calm, with just two competitions that I want to mention, both on Saturday. First, TopCoder Open 2017 Round 2A has significantly raised the stakes compared to Round 1, with just 40 top finishers qualifying (problems, results, top 5 on the left, my screencast). I have enjoyed the medium problem of this round the most, as it is quite rewarding to come up with an easy-to-code beautiful solution after wasting some time coding a very tricky one that comes to one's mind first. Especially rewarding step is removing all code written for the tricky solution (screencast position) :)

Here's what the problem was about: you are given the distances from two vertices to all others in an unknown undirected graph with 50 vertices. You need to construct any graph with such distances from the first two vertices.

With just a few minutes break, Codeforces hosted its Round 415 (problems, results, top 5 on the left). With the only successful solution to problem E coming from a contestant with no other solved problems, it was the speed that decided the winner, and Radewoosh was almost half an hour faster than the rest. Congratulations!

In my previous summary, I have mentioned a Codeforces problem: you are given a connected undirected graph with at most 300000 edges. You suspect that this graph was constructed in the following manner: we started with a graph with no edges and assigned each vertex an integer label, then connected all pairs of vertices for which labels differed by at most one. Your goal is to return a set of labels that could have been used to construct the given graph, or report that there isn't any.

First of all, shifting all labels by a constant does not change the answer, so let's pick a vertex A and say that its label is 0. Now, the labels for all other vertices are almost uniquely determined: it's not hard to see that for all vertices labeled not 0, the absolute value of the label is equal to the shortest distance from A. So, we just need to determine which sign will each label have, and which vertices (out of those at distance 1) will have label 0.

Here we can see that vertices at distance 1 from A are the most tricky part, so let's concentrate on them. We can assign three labels to them: let's say those with label 1 are set X, with label 0 are set Y, and with label -1 are set Z. By the problem statement, all those sets must be cliques, and additionally we must have all edges between X and Y, and between Y and Z, but no edges between X and Z.

Let's assume we have a representative B from X, and a representative C from Z. Then the label of each vertex can be determined trivially: if it's connected only to B, it's 1, only to C, then -1, to both, then 0.

It doesn't matter which representatives we pick - in fact, it's not hard to see that we need to pick any two vertices B and C that are connected to A but not between themselves. If we remember that A can also be picked freely, our goal now is to find a chain of two edges such that its endpoints are not connected.

And this, in turn, can be done like this: first, let's find any missing edge. The graph is connected, so there's a path between its ends. If this path is of length 2, we're found what we need. If it's longer, consider its next-to-last vertex. If it's connected to its first vertex, we've found what we need. If not, then we can remove the last vertex and obtain a shorter path such that its ends are not connected. By repeating the process, we will eventually find the required path of length 2.

Now we have solved the problem for vertices with labels -1, 0 and 1, but how do we determine the sign of the label for the remaining vertices? Well, for vertices with label 2/-2, we can use connectivity to any vertex with label 1 as the differentiating factor, and so on.

Finally, having determined all labels, we need to check if our graph does in fact correspond to those labels. The simplest way to do that seems to be: let's check that for all edges in our graph the difference between the labels of the ends is at most one, and also check that the total number of edges in our graph matches the total number of pairs of vertices with labels differing by at most 1. After the first check, the only way we can have an incorrect graph would be having not all required edges, and the second check takes care of that.

Thanks for reading, and check back here and in my Twitter for news from ACM ICPC World Finals this week!