A 7-time week

ACM ICPC 2017 World Finals headlined the last week (problems, results, top 12 on the left, our stream, text analysis, video analysis). The ITMO team was leading for quite some time, but they did not manage to solve problem J in time, which gave a chance to the other teams. They did not take advantage of that chance, however, and ITMO became 7-time world champions. Congratulations!

Problem D, while being a bit on the "professional" side, was quite cute. You are given 500000 top-left corners and 500000 bottom-right corners on the plane, and need to pick one of each to obtain a valid rectangle with maximum possible area.

Here's its analysis video, in case you give up :)

AtCoder Grand Contest 015 took place on Saturday, when most World Finals contestants should have already got back home (problems, results, top 5 on the left, my screencast with commentary, analysis). When just two last problems remained, I went for the harder one, and almost got it (got accepted in upsolving after about 5 more minutes) - but not quite. sky58, on the other hand, chose the right strategy and won - congratulations!

Problem C allowed multiple different solutions, each with a non-trivial observation and thus quite exciting to get. You are given a set of blue cells on the 2000x2000 grid that forms a forest with regard to 4-connectivity, and 200000 queries. Each query asks: if we take a certain sub-rectangle of our grid, how many connected components of blue cells are there if we look just at that sub-rectangle?

A few hours later, Yandex.Algorithm 2017 Round 2 provided another chance to score place points towards qualification for the final round (problems, results, top 5 on the left, my screencast, analysis). Tourist threw all strategy considerations out of the window by solving all problems with 15 minutes remaining, while others have barely managed solve solve 5 out of 6. Amazing performance!

The solution to problem E relied on a standard idea which I forgot, so maybe explaining the solution in my blog will help me remember :) Here's what it was about: consider all sequences of balls of k<=15 colors, with exactly a_i<=15 balls of i-th color, and no two adjacent balls of the same color. Let's arrange them in lexicographical order. What is the number of the given sequence in this order?

Finally, Codeforces held the online mirror of Helvetic Coding Contest 2017 which I have mentioned earlier (problems, onsite results, online results, online top 5 on the left, analysis). Congratulations to the sweet team on the victory (and their penalty time is better than ours from the onsite contest, too)!

In my previous summary, I have mentioned a TopCoder problem: 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.

Consider an arbitrary pair of vertices. If their distances to vertex 1 differ by at least 2, then we can't have an edge between them. The same is true for their distances to vertex 2. This is relatively easy to spot, but here comes the hard part: if neither of the above is true, in other words if both pairs of distances differ by at most 1, then we can assume to always have this edge in our graph. Because if we don't have it, we can add it and distances to vertices 1 and 2 will not be affected for the vertices we just connected, and thus for all other vertices as well.

Now, since for each edge we can determine whether we have it in our graph or not, all that remains is to construct the graph, and check if the distances to vertices 1 and 2 come out as expected.

Thanks for reading, and check back next week!