AWTF22 day 1

AtCoder WTF22 onsite day 1 just finished (problems, results, top5 on the left, mirror results, analysis). I was actually able to get a problem accepted after two hours have passed, with the caveat that this was the only problem I got accepted :) I probably spent about an hour on B and about three hours on C, with no success. In C, I passed all samples except the last one. It turns out that I did have the correct "minimal representation" for a tree at the end, but then I tried to merge them to obtain a minimal representation for a forest in the same format, but it turns out that this was not possible at all: when merging trees B->W<-B (W is root) and W->B (B is root), the minimal representation is just B, but if we later merge it with a tree W->B<-W (B is root), we get a non-empty representation, while if we choose B->W<-B for the result of the first merge, then we can cancel everything out on the second merge. This counterexample stems from the correct solution idea, which tells that one of the conditions for being able to cancel everything is having at least two roots of different colors; hence any approach that merges the representations of trees has to be able to tell if we have seen two roots of different colors. I feel that this was pretty hard to come up with without actually coming up with the trick from the editorial directly.

Congratulations to everyone who was able to solve two problems in this round, and especially to ksun48 on the total domination and to hos_lyric for solving E!

Given that tomorrow's round has a 1000-pointer as the first problem, I might have to be content with the points I already have. But I will do my best ;)

AWTF22 taifun

One thing that greeted me on arrival to Tokyo was an unusual notification in Google Maps (see on the left). It looked somewhat scary, but then I remembered the amount of dangerous weather notifications that I get in Zurich that typically do not mean anything too unusual, and relaxed a bit. Imagine how much more relaxed I became when this note greeted me in my hotel room (see on the bottom-right).

So, maybe people with experience of Tokyo winds can share: how bad can it be?

In general, my approach to this trip is to avoid jetlag by living more or less on Swiss time. The contests start at 6:00 Zurich time, which is definitely early, but not outrageously so. Given that I'm here for just 4 days, it seems logical to not bother shifting the schedule by much, and to sleep 20:00-5:00 Swiss time (=3:00-12:00 here).

One of the benefits is that I get to do sightseeing in the evening, when it is much more pleasant outside, and there are less people everywhere. The flip side of this coin is that many places will be closed at night.

One particularly important challenge is getting food. Lunch happens during dinner time here, so it is not really an issue. I will be late for the hotel breakfast, but it will already be lunchtime, which means that I can get some lunch food in one of the cafes near the Shinjuku station (not sure if the lunch in the hotel restaurants will be quick enough to be in time for the contests). However, what to do about dinner? Any suggestions about where to eat in Tokyo at 1am? Bonus points if your suggestion comes in the next 2 hours ;)

AWTF22 arrival

So, an onsite event unfortunately means a couple of long flights :) Can you guess which of the two photos is the Zurich airport, and which is the Tokyo airport?

Surprisingly, there were no signs announcing the AtCoder WTF at the airport — how could the airport forget to greet the participants? ;) Having encountered the Japanese reality both in a good way (the immigration was well-organized, and apparently there's even a way to fill all forms online in advance) and in a not-so-good way (apparently the tickets for some, but not all, trains can only be bought in cash, so I had to wait for the next train because there was no time to run to an ATM), I have almost arrived at the competition hotel. 

The competition itself takes place on Friday and Saturday, with two five-hour rounds currently scheduled. I do not know if those are just placeholders, but if not, that is quite a challenge for an individual event. I have a feeling that recently I do not get any problems accepted after the 2 hour mark in contests that last longer than 2 hours, so I will have to do very well in the first 2 hours of each day :)

There is probably a way to use Codeforces API to get a more grounded assessment of that feeling. Or maybe there is an existing tool that can help answer the questions like "what would my place be in Round X if it was over after 2 hours"?

Thanks for reading, and check back soon for more AWTF updates. And I'm sorry for the low fraction of the actual algorithmic content this week :)

A Yoneda week

The 35th International Olympiad in Informatics in Szeged, Hungary was the main event of this week (problems, results, top 5 on the left, day 1 broadcast, day 2 broadcast). Tingqiang Xu and Siyuan Cheng were miles ahead of everybody else (who still did great :)), and only 1 point ended up deciding the overall winner. Congratulations to them but also to all medalists! My inevitable slide in the Hall of Fame continued, seemingly by just 1 place though.

According to the problem page, three out of six problems were created by the amazing team of square1001 and E869120. Creating just one IOI-quality problem is an amazing achievement requiring great ideas and weeks (if not months) of work, so it is hard for me to even imagine creating three in the same year. Well done!

Codeforces ran Pinely Round 2 just a few hours after the first IOI day was over (problems, results, top 5 on the left, my screencast, discussion, analysis). I wonder who is the highest-placed participant who took part in both :) Among the participants well past their IOI days, tourist got his first place using just under an hour out of the three hours available. It could all change at the end of the round, as both last problems were not completely unsolvable and saw a lot of last-minute submissions, but nobody was able to get all details exactly right. Congratulations to tourist!

Problem F did not require one to come up with complicated ideas, but instead required some accuracy "unwrapping the present" to arrive at the solution, and it was nice that the solution turned out quite easy to implement: you are given an array of at most 10000 integers, each between 0 and 2⁶⁰. In one operation, you split the array in the middle into two parts, compute the bitwise xor of each part, and discard the part where the bitwise xor is smaller. In case they are equal, you may discard either part. After doing this operation several times, you have just one number remaining. Which positions in the initial array could this number correspond to?

You might have noticed that the address of this blog has changed to https://blog.mitrichev.ch/. I am going to use this address going forward, even though the old address will keep redirecting to the new one for the foreseeable future. So, welcome to the new home!

It is also a good opportunity to write about my online presence in general. I do not have accounts in the common social networks, such as Facebook, Twitter/X, LinkedIn, TikTok, Instagram, etc. Of the social network-like things I mainly have this blog, my Youtube channel, and my Codeforces account.

Thanks for reading, and check back soon! I will try to post updates about the AWTF during the week.

An onsite week

Harbour.Space Scholarship Contest 2023-2024 on Codeforces was the main event of the week (problems, results, top 5 on the left, discussion, analysis). Radewoosh solved the first eight problems 20 minutes faster than everybody else, and therefore had all but guaranteed himself first place by the middle of the contest. Still, he kept his focus and managed to get problem I accepted as well with just 3 minutes to go. Huge congratulations!

I skipped this round and therefore cannot tell you much about its problems. Therefore, I'd like to use this post to talk about the upcoming onsite event that you might not be aware of :) I'm not referring to the IOI, which takes place next week in Szeged, Hungary, since I expect everybody interested in it to know where to find more information. Instead, I'd like to talk about the AtCoder WTF that takes place on September 8-9 in Tokyo, Japan.

When AtCoder announced its own onsite competition, the World Tour Finals, back in 2017, the world of onsite algorithmic competitions was quite packed. They have managed to host one edition of the WTF before the pandemic hit. All onsite competitions were cancelled or moved online during the pandemic, but instead of returning after global travel became relevant again, most were cancelled completely: Google Code Jam, TopCoder Open, likely Meta Hacker Cup. There were a few more Russia-based onsite competitions that are of course no longer a thing. ACM ICPC and high school olympiads such as the IOI are back in the onsite mode, but they have age upper bounds for participation.

AtCoder did not move the WTF online, instead they kept running the yearly qualification cycle, promising to invite the top 8 from each year to the onsite round in Japan when it becomes possible again. This is finally happening in two weeks! 18 finalists out of the maximum of 32 from the four qualification cycles will compete on the same problems over two competition days. This approach lies in contrast to the ACM ICPC approach where the finals for the 2022 and 2023 seasons are happening together in Egypt but the actual competitions will be kept separate. Which one do you think makes more sense?

I am really excited both for the competition (where to be honest I no longer stand a chance), and for the onsite event atmosphere. As an added twist, AtCoder have announced the online participation option for the future WTFs; I can't predict how this will work out, but when TopCoder did the same for TCO22, so few people decided to come onsite that they decided to cancel the onsite event altogether. Therefore this might be the last onsite event without the age upper bound ever :)

Thanks for reading, and check back next week!

An arborescence week

There was no contest that I'd like to mention this week, so let us come back to the AtCoder problem from the previous summary: you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any.

The first step is to notice that all edges are of three types: type 2 are the edges where both ends have the same color as the edge, type 1 are the edges where one end has the same color as the edge, and type 0 are the edges where no end has the same color as the edge. We will also direct the type 1 edges from the vertex of the correct color to the vertex of the wrong color.

Clearly type 2 edges are the most useful for reaching our goal. In fact, if every vertex has at least one type 2 edge adjacent to it, then we can simply find the spanning forest among the type 2 edges. If it is a spanning tree, then we have solved the problem. If it is not connected, since we have already satisfied the color constraints, we can augment the forest to a tree using the remaining edges in any way.

What if there are some vertices that do not have type 2 edges adjacent to them? If there is a vertex with no outgoing type 1 edges, or in other words a vertex where all adjacent edges have the wrong color, then there is clearly no solution. So we only have to consider the case where some vertices have type 2 edges adjacent to them, and all remaining vertices have at least 1 outgoing type 1 edge. We will call the vertices with type 2 edges adjacent to them type 2 vertices, and the ones without them type 1 vertices.

The key remaining observation is that we cannot solve the problem using only type 1 edges. Each type 1 edge satisfies the color constraint for 1 vertex, but overall we have n vertices but only n-1 edges. So a logical idea is to start with the spanning forest of the type 2 edges that will cover all type 2 vertices, and then repeatedly try to find a type 1 edge that goes from a yet uncovered vertex to an already covered vertex (building something similar to an arborescence). If we manage to cover all vertices this way, then we can once again augment the resulting forest to a tree using the remaining edges. If we get stuck at some point, then there is no solution.

But why is this correct? We have proven that we need at least one type 2 edge, but why is it always correct to take ~all of them? This is a very typical situation for problems involving the spanning trees, as they all usually end up relying on some kind of greedy argument, so one could just bet on intuition here in my opinion. Still, here is the formal proof: consider the situation where our solution gets stuck. At this moment, the set S of uncoverted vertices contains only type 1 vertices, and there is no type 1 edge going from this set to the set of covered vertices. But then how could S be covered in any other solution? Since we have at most |S|-1 edges within S, and only edges within S can cover its vertices, one of them will have to remain uncovered in any tree.

Thanks for reading, and check back next week!

An apiad week

AtCoder Grand Contest 064 was the main event of the week (problems, results, top 5 on the left, analysis, my screencast, race standings). apiad's usual strategy worked spectacularly well this time, as after spending two hours on E he was able to solve just enough easier problems to win the round, while those who started with the four easier problems did not have two hours remaining for E and could not figure out all details. Congratulatons on the victory!

I was one of those starting with the four easier problems. Somewhat unexpectedly, I did not get stuck in them and did actually have a bit more than an hour remaining for E, and made some significant progress on paper: I realized that if the sum of all a_i is zero, and the sum of all b_j is zero, and we can place the n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j, then the sum of the 2n-1 cells in a cross, which is the sum of the row plus the sum of the column minus the middle cell, will be exactly a_i+b_j. I've then realized that if the sum of all a_i plus the sum of all b_j is divisible by 2n-1, then we can get both of those sums equal to zero with some constant shifts. Finally, I've correctly hypothesized that in case it's not divisible by 2n-1, then we can only achieve score n²-1, and figured out how to do so with some more constant shifts for the first row and the first column.

Therefore the only remaining step was to place the n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j. This does not depend on the values of a and b, so this simply needs to be done once for every n. It seemed quite doable as it felt like a more advanced derangement, and derangements are quite dense. I've tried some random placements and noticed that I can find such a placement for odd n, but not for even n. And this is pretty much how far I've got in an hour :)

Judging from the editorial (which I do not understand), it seems that for even n we need to use more degrees of freedom, therefore while I enjoyed coming up with my approach, I needed another huge step to finish the solution, and therefore needed at least another hour.

I found problem B to be a cute test of how well one understands the spanning tree mechanics (it is amazing how many nice problems can be derived from a relatively simple concept of a spanning tree, and the fact that it can be found greedily!): you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any. Can you see a way to do it?

Thanks for reading, and check back next week!