Sunday, July 14, 2024

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.

Saturday, July 13, 2024

AWTF24 contest

AtCoder World Tour Finals 2024 took place today (problems, results, top 5 on the left, broadcast recordinganalysis). This was my first 5-hour commentating experience, and I enjoyed it a lot! How did it look from your side? Please share your improvement suggestions, just for the remote chance that I do not qualify again :)

This time the contestants had an opportunity to share their thoughts on stream (similar to the "confession booth" concept from some chess tournaments recently), and while not everybody used it, it was great fun and great insight to listen to those who did (for example; did somebody maybe gather all timestamps?). I hope this practice gets expanded and improved at future contests!

ecnerwala also tried to share his thoughts before the contest even started, but unfortunately the stream had not started as well at that point and therefore his words were not recorded. Nevertheless, maybe this helped him get into the right mood and solve problem E quickly, which was key to his win. Congratulations to him and to zhoukangyang and ksun48 who also won prizes!

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

Thursday, July 11, 2024

AWTF24 pre-contest

On Wednesday, the contestants were gathering in the hotel. The contestants from Europe and America hat some very long flights behind them, so there was not much appetite for activities. Therefore we played some board games in the hotel lobby in between short excursions to get some Japanese food. We did not actually meet most of the contestants from Asia — maybe the reason was that they actually had more energy for exploring Tokyo and did not hang around in the hotel :)

The games of choice (well, those were the only ones I brought so there was not that much choice...) were Cascadia and (Level 1 H-Group) Hanabi. It turns out that the synergies of the H-Group conventions are not so obvious at level 1, so probably next time we introduce somebody to them we should start at least with level 3.

We also got to witness the AtCoder admins printing the logos on the official t-shirts, as it turned out that the shop where one can print arbitrary content on a t-shirt in a self-service manner happened to be on the lower floors of the hotel building. Even though this is not much different from a normal printer, seeing how one can slightly adjust the image and then get an actual t-shirt with this image in a couple of minutes was quite impressive.

Today was a free day for the contestants, who have ventured a bit more into the city having rested from their travels. It was still funny with the timezone differences and jetlag, as the same meal was breakfast for me, lunch for the locals, and dinner for the contestants from America. Some contestants warmed up their problem solving capabilities by doing escape rooms, while others opted for actually solving old competitive programming problems for some last-ditch practice.

Tomorrow is the big day! The overall setup is similar to the last year, but with just one contest: 5 problems for 5 hours, the penalty time is computed as the time of the last successful submission (not the usual ICPC sum) plus 5 minutes for each incorrect submission. You can find more details in Riku's post. And of course tune in to see my and Riku's commentary on the live broadcast which will start at the same time as the contest, 12:30 Tokyo time, and last for 5 hours.

All 12 finalists are very strong, so it is hard to predict who will come out on top. zhoukangyang won 4 out of the last 6 AGCs, tourist has a lot of experience winning those contests, and jiangly has won the AWTF last year  — I guess we can keep an eye for those three, but anything can happen really.

Thanks for reading, and tune in tomorrow!

UPD: the live broadcast link has been updated.

Tuesday, July 9, 2024

A 熱中症予防 week

There were no contests that I'd like to mention last week, so I can get straight to the new format of this blog for the coming week: a travel blog! I am going to the AtCoder World Tour Finals 2024 in Tokyo. I did not manage to qualify this time, placing 14th when I needed to be in top 12, so I am going as a spectator and as a co-commentator for the stream, together with Riku, the main admin of AtCoder.

For a second year running, Tokyo welcomes the participants with an extreme weather warning in Japanese, this time for extreme heat. Please all take care, and focus on playing board games in the air conditioned hotel!

Speaking for 5 hours while 12 contestants are facing, to put it mildly, challenging problems is also not a walk in the park. Please help us by suggesting topics that we should discuss or things we should do on stream in comments!

In my previous summary, I have mentioned a Universal Cup problem: first, we draw the vertices of a regular n-gon (n<=10000) on the plane. Then we repeat the following process m times (m<=30000): take any 3 already drawn points (either the original n-gon vertices, or ones drawn during the previous steps) Ai, Bi, Ci, and draw the point Ai+Bi-Ci (the fourth vertex of a parallelogram). Finally, we need to handle multiple queries of the form: given k drawn points (the sum of k over all queries <=30000), do they form the vertices of a regular k-gon in some order?

We can get points that are really close to a regular k-gon but not exactly one in this problem, and no feasible floating point precision is enough. Therefore we need to solve it using only integer computations. Nevertheless, let us first consider how a floating-point solution might work.

We can imagine that the points lie on the complex plane, and the initial n points are ei/n. Drawing a new point corresponds to computing Ai+Bi-Ci using the complex number arithmetic. There are many ways to check if k computed points form a regular k-gon, here is one: we need to check that the k points, in some order, can be represented as x, xy, xy2, ..., xyk-1, where y is such that yk=1 and no smaller power of y is equal to 1. Note that this order does not have to be the clockwise/counter-clockwise order of the vertices: multiplying by y can also represent a jump by any coprime number of edges, and this criterion will still be valid. Also note that we can actually pick any of the vertices as x and such y will exist, moreover there will be φ(k) different values of y that work for each vertex. So one way to find y is to just try a few other vertices z of the polygon, let y=z/x, and check if the criterion is satisfied. Since φ(k) is not too small compared to k, we should find a valid y after a few attempts, let's say at most 50. Of course, we could've just said that y=ei/k, but you will see below that the y=z/x approach leads to an interesting question that I want to discuss.

If we denote the "base" point as u=e2π/n, then all other initial points are powers of u, all computed points are polynomials of u, and the checks we are making boil down to whether a certain polynomial of u with integer coefficients is equal to 0 or not (even though we also use division, checking if poly1(u)/poly2(u)=poly3(u)/poly4(u) is the same as checking if poly1(u)*poly4(u)-poly2(u)*poly3(u)=0). We could try to maintain said polynomials with integer coefficients, but since the degrees would be on the order of n, and the coefficients themselves could be huge, this is not really feasible within the time limit. 

Here comes the key idea: instead of complex numbers and u=e2π/n, let us do the same computations using integers modulo a prime p and using such u that the order of u modulo p is equal to n. Such u exists if and only if p=sn+1 for some s, so we can search for a random big prime number of this form, which can be found quickly since all arithmetic progressions with coprime first element and difference have a lot of prime numbers.

This actually works very nicely and allowed us to get this problem accepted. However, why does this actually work? The order of u is the same in our two models (complex numbers and modulo p), so every polynomial of the form ut-1 is equal to 0 in both or in neither model. However, this does not guarantee the same for an arbitrary polynomial with integer coefficients, or does it?

Of course it is not true for an arbitrary polynomial. For example, the polynomial p is equal to 0 modulo p, but not equal to 0 in complex numbers. However, we can deal with this by picking the modulo p at random, and potentially also checking several moduli in case the judges actually create testcases against many potential moduli. So the real question is: are there polynomials for which being equal to 0 differs between the complex numbers and computations modulo p for all or a significant fraction of all possible values of p?

Here we need to bring in some maths. When two polynomials with rational coefficients are equal to 0 for the given u their greatest common divisor also has rational coefficients and is also equal to 0 for the given u, which means that there must exist a minimal polynomial such that a polynomial with rational coefficients is equal to 0 for the given u if an only if the minimal polynomial divides it. Such minimal polynomial for our u is called the n-th cyclotomic polynomial Φn(u).

Now, consider the equality un-1=Φn(u)*gn(u) (where gn(u) is just the result of dividing un-1 by Φn(u)). This equality is true in rational numbers, so it is also true modulo p where there is no division by p in it, so for almost all p. The left-hand side is 0 modulo p because of our choice of u, so either Φn(u) or gn(u) must be 0. However, from the structure of the cyclotomic polynomials we know that gn(u) is a product of cyclotomic polynomials of smaller order, so if it was equal to 0, it would mean that the identity ut-1=0 would hold for some t<n, which contradicts our choice of u. So we know that Φn(u)=0 modulo p, which means that every polynomial with integer coefficients that is equal to 0 for the given complex u will also be equal to 0 for the given u modulo p. So we have proven one of the two required implications.

Now let us tackle the the opposite implication. Consider a polynomial h(u) with integer coefficients that is equal to 0 for all or a significant fraction of all possible values of p (with the corresponding u). If Φn(u) divides this polynomial (as a polynomial with rational coefficients), then it is also equal to 0 for the given complex u, as needed. If Φn(u) does not divide it, then we can find the greatest common divisor of Φn(u) and h(u), again doing computations using polynomials with rational coefficients. Since Φn(u) is irreducible over polynomials with rational coefficients, this greatest common divisor will be 1, so we have 1=Φn(u)*a(u)+h(u)*b(u). The right side involves a finite number of different integers in denominators, so this equality will also hold modulo p for all p except those dividing one of the denominators, in other words for almost all p. But since both Φn(u) and h(u) are equal to 0 for all or a significant fraction of all possible values of p, this means that 1 is equal to 0 for all or a significant fraction of all possible values of p, which is a contradiction. Therefore we have also proven the opposite implication and this solution does in fact work.

There are still a few things I do not fully understand about this setup. One is the following: it turns out that when n is odd, we can actually construct a regular 2n-gon (roughly speaking using the fact that -1 helps generate the other n points; there was such example in the samples for n=3, k=6), so k does not have to divide n. In this case, the number y that we find as part of solving the problem must have order 2n modulo p. However, note that in general it is not even guaranteed that there is any number with order 2n modulo p, as we only choose p in such a way that there is a number with order n. Since we compute y=z/x, we can do this computation for any p where we can compute z and x. So it seems that the above also proves that for almost all primes p if there is a number of odd order n modulo p, there is also a number of order 2n modulo p. This observation is in fact true for a straightforward reason: almost all primes are odd, so there is an even number p-1 of nonzero remainders, therefore there is a number of order 2, and we can multiply the number of odd order n by the number of order 2 to get a number of order 2n. Still, I can't get rid of the feeling that I might be missing something here. Any comments?

The second thing I don't fully understand is whether we truly need a full understanding of the structure of cyclotomic polynomials to prove that Φn(u)=0 modulo p. It feels that maybe there is an easier way to explain this that does not require so much knowledge?

Thanks for reading, and check back for more AWTF updates!