A week when tourist becomes retired (not really)

ACM ICPC 2015 World Finals was the event of this week (problems, results, top 5 on the left, my twitter commentary, full video recording). Congratulations to ITMO on the amazing victory and 13 solved problems, and to all other medalists for outstanding results! Both Moscow State University and University of Tokyo looked to be leading the contest at times, but ITMO solved three in the last hour to finish in a clear first.

Here's one of the trickiest problems of the finals - problem K: you're given an undirected graph, and need to find all numbers k such that it's possible to color all of the edges in the graph with k colors in such a way that every simple cycle in the graph is colored evenly: has equal amount of edges of every color. It's mostly a mathematical problem, but has both a very nice statement and a very nice solution, which you can find in my twitter. The video recording also contains analysis for all problems, here are the direct pointers.

Top three teams are not eligible to compete next year (except maybe one person from University of Tokyo?..), please share any details about other medalists returning or other upcoming strong teams! Anyway, the competition is wide open, and the finals will take place in Phuket, Thailand.

Yandex.Algorithm.2015 Round 1 happened on the weekend (problems requiring login, results, top 5 on the left). The problemset was quite unusual with 5 problems of roughly the same difficulty, and one easier problem (problem F), thus paving the way for very diverse results at the top. I've taken great care not to submit incorrect solutions, writing a stress-test in 3 problems out of 5 I've solved. I was lucky nobody managed to solve all six without those precautions.

One of the more standard problems was problem B, where you were given 1000 points on the plane with weights, and asked to separate all points with a straight line into two halves with as close total weights as possible. The stress-test I've implemented here was a bit non-standard, so I want to share it with you. The O(N²logN) solution for this problem involves iterating over one of the points that will be "very close" to the dividing line, then rotating the line around this point keeping track which points are on one side and which points are on the other side. I've made my solution rotate the line three full circles around each point instead of one full circle, and assert that we get the same result after rotations that differ by a full circle, and then just ran it on randomly generated testcases - finding a bug in the code that manifested as inconsistencies between two rotations that are essentially the same (the bug was using the unsorted array of points instead of the sorted one), and submitting the correct solution afterwards.

Thanks for reading, and check back next week!

Tweet