An ecnerwala week

AWTF24 was the main event of this week. I have mentioned its results in the previous post, so I want to use this one to discuss its problems briefly.

Problems A and B both had short solutions and were quick to implement, but required one to come up with a beautiful idea somehow. When Riku was explaining their solutions during the broadcast, I was amazed but could not understand how to come up with them :) One way to do it, at least for problem A, was to actually start by assuming the problem is beautiful, and to try coming up with some beautiful lower or upper bound for the answer, which can turn out to be the answer.

To test if you can walk this path, here is the problem statement: you are given n<=250000 slimes on a number line, each with weight 1. You need to choose k of them, all others will be removed. Then, they will start moving: at each moment in time, every slime moves with velocity r-l, where r is the total weight of all slimes to the right of it, and l is the total weight of all slimes to the left of it. When r-l is positive, it moves to the right, and when it is negative, it moves to the left. Since this rule pushes the slimes towards each other, sometimes they will meet. When two or more slimes meet, they merge into one slime with weight equal to their total weight, which continues to move according to the above rule. Eventually, all slimes will merge into one stationary slime, suppose this happens at time t. What is the maximum value of t, given that you can choose the k slimes to use freely?

Problem D turned out to be equivalent to an old Codeforces problem applied to the inverse permutation. Most of this week's finalists have participated in that round or upsolved it, so it was not too unfair. The top two contestants ecnerwala and zhoukangyang did solve the Codeforces problem back in 2022, but did not remember it, and implemented the solution to D from scratch (even though of course having solved the old problem might have helped come up with the correct idea here). ksun48 and heno239 in places 3 and 4 did copy-paste their code from 2022.

Problems C and E involved a bit more code and effort to figure out all details, but one could make gradual progress towards a solution when solving them, instead of having to pull a beautiful idea out of thin air. Were I actually participating in this round, I would most likely spend the most time on, and maybe even solve those two problems.

Overall, this was a very nice round, and I'm looking forward to more AGCs in 2024 to try my hand at more amazing problems!

On the next day after the AWTF, the 3rd Universal Cup Stage 4: Hongō took place (problems, results, top 5 on the left). 8 out of 9 participants from the first three teams (congrats!), which coincidentally are also the first three teams in the season ranking, were in Tokyo, so Riku and Makoto have organized an onsite version of this stage at the AtCoder office. Solving a 5-hour contest with your team in person instead of online is already much more fun, but having other teams in the room and discussing the problems with them right after the round is even better. I guess I'm still yearning for the Open Cup days :)

I was solving this round together with Mikhail and Makoto. Thanks a lot Makoto for briefly coming out of retirement to participate, it was great fun solving this round together, and I can confirm that you're still very strong! Maybe we can have another go next year.

Problem N was not very difficult (I spent at least half an hour without any success, explained the problem to Makoto and he solved it almost immediately), but still enjoyable: you are given a string of length n<=500000. We choose one its arbitrary non-empty substring and erase it from this string, in other words we concatenate a prefix and a suffix of this string with total length less than n. There are n*(n+1)/2 ways to do it, but some of them may lead to equal strings. How many distinct strings can we get?

Thanks for reading, and check back next week.