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!

A universal week

Last week, the main round was the 3rd Universal Cup Semifinals (problems, results, top 5 on the left, analysis, contest stream, closing ceremony stream). For those not familiar with the Universal Cup, this announcement has some links for more information, but in short, it is a competition with many online stages throughout the year (40 in the 3rd season, but the organizers plan to reduce the number significantly for the 4th season to reduce the pressure on the teams trying to qualify for the Finals), each stage being a 5-hour contest with ICPC rules, usually with the problems from a regional or another previous non-public contest. The results over all stages are then aggregated into a rating (the formula will also be changed for the 4th season), and the top teams from this rating are invited into the Finals, which took place onsite in China for the 2nd season, and it's not yet clear if it will be onsite or online for the 3rd season that just finished. Recognizing the fact that some strong teams do not have the time to participate regularly, the organizers also host a Semifinals competition online, where every team can enter, and a few more spots for the Finals are won.

Team USA1 has continued their domination of the Universal Cup — congratulations! Since they and a few other teams at the top have already qualified for the Finals by the virtue of their regular season result (also 1st), the first team who advanced to the Finals from this round was team arvin and errogame, and maybe even more importantly, the last team who advanced to the Finals from this round (future cancellations notwithstanding) was team Dvoe protiv vetra. Well done to all finalists!

I and my team were also looking forward to participating in this round, but unfortunately a last-minute conflict interfered with my plans. Now I think we need to do at least one and hopefully more stages of the 4th season instead!

This week Codeforces Round 1046 led the way (problems, results, top 5 on the left, analysis). Each problem was solved by at least 4 contestants, but only jiangly managed to put all of them together, with just 3 minutes remaining in the round. Congratulations on the convincing victory!

And next week, it's all about #ICPCBaku. I will be there as well and try to share some tidbits in this blog, so check back soon!

A byte week

There was no contest that I wanted to mention last week. Since I am getting such empty weeks quite often now, I've decided to check unfiltered clist in case I have missed something. And indeed, there seems to be an onsite round of a competition called Wincent DragonByte coming up in September which I only discovered today, and therefore missed my chance to qualify for the onsite finals in Bratislava :) It is a pity but in the grand scheme of things there are of course so many contests I already took part in and hopefully even more that I will take part in.

Nevertheless, this raises a logical question: what would be a good strategy to avoid missing such nice competitions? Reading all Codeforces posts does not seem to work, and neither does checking clist regularly enough. Is there a way to get notified when new contest websites are added to clist maybe (for example, maybe one can achieve that by excluding less relevant resources via "hide" rules in the filters, as opposed to choosing the relevant resources as "show", which I am doing now)? Or should I create an AI bot that checks unfiltered clist or unfiltered Codeforces and decides if I should be notified? What is your strategy? And of course, what other cool contests am I already missing? :)

Thanks for reading, and check back for this week's summary!

A thesis week

Atto Round 1, also known as Codeforces Round 1041, was the main event of the week (problems, results, top 5 on the left, analysis). With problem H turning out way easier than the problemsetters have expected, the top places were decided on problem G concerning permutations and their compositions, which for me was just very hard to load into RAM to even think about it :) At the end of the contest I came up with a randomized solution that takes 15 random permutations and asks all their cyclic shifts. It actually passed G1 in upsolving, but during the round I did not manage to find all off-by-one and permutation-instead-of-inverse bugs. But even in upsolving it seemed hopeless for G2 where we only get to take 10 such permutations.

It turns out that Kevin has won the round with exactly the same solution. To pass G2, he tried 1000 different random sets of 10 permutations before starting to ask questions, and chose the set that gives the least collisions. This turned out to be borderline good enough, and 4 submissions that differed only in the random seed (diff on the right) sealed the deal. Well done Kevin, and also well done Jiangly on solving G2 in the "on paper" way :)

I got my share of successful randomized solving in problem H, where after being stuck for a while I decided to submit a solution that took edges that can definitely be taken, and when there is no such edge, took a more or less random edge and continued, and then repeated this process until the time runs out. This should be roughly the same as backtracking but even simpler to implement, and I expected that with n=30 it has a high change of passing, and indeed it did from the first attempt in which I fixed all bugs.

It is curious that neither problemsetters nor myself were able to see:

1) the relatively standard dynamic programming solution for the problem that takes advantage of the fact that from every subtree of the DFS tree we have at most 5 backward edges, and therefore can just add the state of all those edges to the dynamic programming state.

2) the non-bipartite matching solution that does not even rely on the additional "at most 5" property from the problem statement: the problem statement essentially asks for maximum matching, but where each vertex can be used twice instead of once, so we can just duplicate the vertices and be done.

Point 2 is even more bizarre in my case, since my masters thesis 18 years ago was on a more general version of exactly this problem, 2-path-packings. The thesis was in Russian and I don't think it is published anywhere, but it is roughly equivalent to chapter 3 "O(mn)-time algorithm" in this paper. So the matching interpretation should really have been obvious to me, even after 18 years :)

Thanks for reading, and check back next week!

An open week

The 37th International Olympiad in Informatics took place this week in Sucre, Bolivia (problems, results, top 5 on the left). It was a bit more tricky than usual to get to, but I'm sure the contestants, the leaders and the organizers also gathered quite a few good memories for a lifetime :) Congratulations to Hengxi Liu on a quite convincing win!

I continue to be amazed about many things IOI:

• the repeat participants who keep pushing me down the hall of fame even further, this year Ryan Bai and István Ádám Molnár. 
• the repeat problemsetters that keep coming up with amazing problems, setting three out of six problems just like two years ago: square1001 and E869120.
• the amazing openness of the organizers who publish both the GA minutes (2024, all, this year's minutes will probably appear a bit later?) and the IC minutes (March 2025, all). I am learning a lot about organizing those great events, and about democratic processes in general, from reading those.

Keep up the good work!

Codeforces hosted its Round 1040 between the IOI competition days (problems, results, top 5 on the left, analysis). Kevin114514, who as I understand was too young to qualify for China's IOI team (please correct me if I'm wrong!), instead had to settle with AKing this round and overtaking jiangly for the second place in the overall rating. Well done!

Thanks for reading, and check back next week.