A polar week

ICPC World Finals 2025 #ICPCBaku was the main event of the week, and for many the main event of the year (problems, results, top 12 on the left, official stream, our stream). The St Petersburg State University team was always among the leaders, but they collected too many incorrect attempts and therefore the almost flawless University of Tokyo team was leading with a better penalty time on 10 problems just two minutes before the end. However, the St Petersburg State University has managed to get the very difficult problem G accepted as well, and the university became the world champion for the 5th time. Congratulations!

For the University of Tokyo this means that they have earned their 13th medal and 6th gold, but will unfortunately need to wait to lift the cup for a bit longer. I expect them to do it soon, given the flourishing programming contest community in the university and in Tokyo in general. In any case, well done to them and to all medalists!

We have solved the mirror contest together with Kevin and Mateusz. It started reasonably well, but then initally Mateusz and then myself got stuck in problem B, spending a lot of thinking time and computer time on it, but never getting it accepted.

At the end of the contest, we tried to add some heuristics to speed up our matching code in B, but it was still too slow. The way that many teams used to work around it is to have a separate solution for "large enough" values of n, either a direct mathematical one or one obtained by looking for patterns in the outputs in the matching solution for small values of n.

However (it is always somehow easier to think after the contest ends...) today I have tried another approach that seems obvious in retrospect: since we just need to find an even number that is not covered by some matching, and in the normal bipartite matching algorithm (usually called Kuhn's in the programming contest circles) as soon as we're unable to find an augmenting path from a certain vertex of the first part, we know that it will not be covered by the final matching, we can stop the matching algorithm as soon as a search starting from an even number is unsuccessful. On my laptop, it makes the code run in 0.6s for n=10⁷. I could not find any working upsolving to test this properly, please share a link if you know one!

Another problem that I found very nice was problem E: you are given a graph with 2n vertices and m edges (n<=2*10⁵, m<=4*10⁵), the vertices are split into n pairs that we will call blocks, let us call one vertex in a block red and another blue. Every edge connects a red vertex with a blue vertex. The m edges are added to the initially empty graph one by one. After each edge is added, you need to print the number of pairs of blocks (out of n*(n-1)/2 possibilities) that are connected (there exists a path connecting one of the four possiblities: between the red or the blue vertex in the first block and the red or the blue vertex in the second block). If not for the complication with the blocks, it would be a simple union-find application, but can you see how to deal with the blocks?

Thanks for reading, and check back next week!