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!

A chess day

Yesterday was the day of the Dress Rehearsal and the Tech Trek at #ICPCBaku. I am planning to solve the mirror contest on Thursday together with Kevin and Mateusz, so we used the Dress Rehearsal time to practice our solving and streaming setup as well (photo on the left). Unfortunately we could not practice the submissions since it seems that the mirror was not available for the Dress Rehearsal, but the rest seems in order. Tune in tomorrow (Thursday) at 11:00 Baku time to my Twitch to watch us compete! You will also be able to look at the official broadcast of the real contest, its scoreboard and problems (you can find more links here), and of course please support the #ETH team!

Today is the ICPC Challenge day, with the results due to be announced in a couple of hours. In the evening the Alumni-hosted events will continue, and I have decided to use my slot for an online chess tournament for the World Finals onsite attendees. Here is how I propose to run it:

• We will run a 5-round Swiss tournament on lichess with 3+0 time control (3 minutes for each side per game, no increment). This yields a ~30-minute duration but if games finish earlier hopefully it will be a bit faster and everybody will be in time for the push-ups :)
• To join the tournament, you need a lichess account and a phone or a laptop to play. If you do not have a lichess account and want to participate, please create it in advance!
• To join the tournament, you also need to join this team on lichess first. I will need to approve everybody who wants to join the team so that it keeps being an onsite event, so you will need to find me in person for that.
• The easiest way to find me in person will be to come to the Chill Zone in the Marriott Blvd today at 17:30 (or a bit earlier).
• The tournament will start at 17:35, so don't be late! If you are late, you should be able to join the tournament late during the first two rounds as well, but then you will miss some games :)

If you have any questions, please ask in comments here or on Codeforces!

An alumni day

The Alumni Talk and the Opening Ceremony were the main events of the ICPC World Finals 2025 today. Among other things, they demonstrated two of the best careers (according to my own perception, of course :)) that the ICPC crowd can choose: the Alumni Talk was about fundamental computer science research, in this case of the core graph shortest path algorithms, while the Opening Ceremony introduced two new sponsors, Google DeepMind and OpenAI, which represent just as cutting-edge but more practical ML/AI research. On a more meta note, it is fascinating how from talking with different ICPC participants and alumni, there are those that consider it an important career step to one of the above fields, there are also those who really want to win it or get a medal, but there are also those who are here to have fun and mingle with like-minded people, and the event works great for all of them. Well done to the organizers!

Another highlight of this year is a series of alumni events which are not on the main schedule, but for me personally look more interesting than many of the main events. If you're onsite in Baku, come chat with us, in particular I will be hosting on Wednesday at 17:30! I am also looking for a topic for my session, even though "Meet and Greet" also works. One topic that flows naturally from this blog is something like "blogging in the age of TikTok and Discord", but I'm not sure if it is the most interesting one :)

The ICPC Quest today asked us to go back to the old photos in the ICPC photo gallery. My photos in the ICPC photo gallery do start with my first participation in 2003 in Beverly Hills, and you can see the one I like the most from that year on the left.

Thanks for reading, and check back tomorrow for more #ICPCBaku updates!