A baursak week

The ICPC World Finals 2024 in Astana was the main event of this week (problems, results, top 12 on the left, broadcast recording, our stream recording). On our stream things did not go very well, as we struggled a lot getting problems accepted (only one + out of 9), so after getting 4 problems in the last 70 minutes including one in the last minute, we arrived at 9 problems with the penalty of 2238, which would give us a clear first place in the contest based on penalty time only :) With the usual scoring, it would only be enough for a silver medal.

Among the people born in the 21st century, the Peking University team was very fast on the easier problems, had very few incorrect attempts, in the end earning the championship title with a huge margin of almost 300 penalty minutes. Big congratulations to them and to all medalists! And of course huge thanks to all #ICPCAstana organizers, you did a great job!

From the 12 medalists, 1 came from the Northern Eurasia division, 2 from the North America division, 4 from the Asia East division and 5 from the Asia Pacific division. Is it the best result ever for the Asia Pacific division?.. Sadly, the ETH Zürich team and other teams from our Europe division stopped at 7 problems solved and therefore just shy of the medal boundary.

Problem D in this round required a nice and somewhat unexpected observation. You are given n segments (n<=200000) on the number line. You need to pick one number from each segment, and then pair up some of those numbers in such a way that two numbers in a pair always add up to the given sum s. What is the maximum number of pairs you can form?

One more thing that I did not mention yet about the ICPC World Finals Astana is the CLI symposium. It is a collection of talks by the people that run various aspects of the competitive programming community, for example this year's speakers were Nikolay Kalinin, Riku Kawasaki, Suhyun Park, Antti Laaksonen, Gennady Korotkevich, Andrey Stankevich, Yonghui Wu, Miguel Revilla Rodriguez, Joshua Andersson, Matt Ellis and Christian Yongwhan Lim. You can watch their talks on the ICPC Live channel as well: 1, 2, 3. They are not necessarily at the level of a TED talk, but I think they can provide interesting insights into the thinking of the speakers and into the functioning of the community.

Thanks for reading, and check back next week!

ICPC Astana mirror stream

Today was the dress rehearsal day at #ICPCAstana, which means even more time for socializing and side events, the most spontaneously designed of which was Mike Mirzayanov's pushup challenge (recording). I was expecting that there'd be a contestant that would easily beat Mike, but it was not even close as Mike still had a lot of strength left when everybody else dropped out (the last 3 pictured on the left). Well done to all participants!

It is finally getting serious tomorrow, with the ICPC World Finals 2024 starting around 11:00 Astana time (official live stream, scoreboard and problems, mirror contest, list of teams 1, list of teams 2). As usual, there are many very strong teams that have been practicing specifically for this event, so it is quite hard to predict tomorrow's standings. We can just relax and enjoy watching the contest. But of course go #ETH!

As the custom goes (2017, 2018, 2019, 2020, 2022), I have teamed up with Kevin and Nikolay to participate in the mirror and stream the proceedings. Here is a link to our stream, and in case something goes wrong, you can look for new instances of the stream on my Youtube channel and/or my Twitch. Tune in tomorrow around 11:00 Astana time (in the past, the round has started both a bit later and a bit earlier)!

ICPC Astana settling in

Most participants arrived in Astana over the weekend, but for me yesterday was the travel day. It started still in the dark (photo on the left), and when I arrived in Astana it was dark again. I also did not meet any other World Finals participants on the way, so it was pretty lonely. Having arrived in Astana though, I was instantly impressed by how smoothly everything goes, both with respect to ICPC and Astana in general, and of course I immediately got to meet some old friends, even at 22:00 on the hotel dinner. 

While I was in the air, the team registration, the talk by ecnerwala and the opening ceremony took place, which were also recorded (1, 2, 3). As part of the registration, team photos were taken, for the history but also for use in the World Finals broadcast on Thursday. On the right you can see the ETH Zürich team which graciously agreed to take me with them to Astana. Go ETH!

Today is a pretty chill day, with a few events such as the Tech Trek with another round of team Kotlin coding (recording) and the ICPC challenge (recording), but where most people just hang around in the big hall (a photo from the official gallery on the left) which reminds me a lot about the TopCoder Open onsite arenas back in the days, only it's at least 10x bigger this time: it is right next door to the contest floor, there is food, sponsor booths, but also a lot of space to just talk or play games with your friends. I think it is a perfect setup for an onsite contest!

One other thing already going on for three days is the ICPC Quest, which this post is also part of. There are various challenges aimed at people getting to know one another, and creating more content about the World Finals, and completing those challenges gets one some plush camels. I did not take part in it in the past, but I've decided to give it a go this year, and it's fun! I'm including #ICPCAstana in this post to fulfill one of the quest tasks :)

Thanks for reading, and check back tomorrow!

A family gold week

IOI 2024 was the main event of last week (problems, results, top 5 on the left). This time Kangyang Zhou beat everyone including the problemsetters — huge congratulations! I also lost 3 hall of fame positions this year: congratulations to Daniel Weber, Rain Jiang and Kshitij Sodani on the amazing performance over many years :)

The IC, ISC and HSC (and later the GA, I guess) had to deal with a controversy, and were put into a situation where no matter what they decide, somebody would feel very disappointed. However, I expect that the democratic process by which those decisions were taken (first within the IC, and then when confirming at the GA) helps those unhappy with the decision still accept it. And of course, I'd like to express my great respect to the IC members for navigating this very tricky case. Well done!

Similar to the last year, one author created several problems, which still impresses me a lot even though it is happening for the second year in a row. Well done Pikatan Arya Bramajati!

The 3rd Universal Cup Stage 9: Xi'an on Saturday was likely the last practice for many teams before the upcoming ICPC World Finals 2024 in Astana (problems, results, top 5 on the left). Team HoMaMaOvO have finally got back to the winning ways, wrapping up the contest with more than an hour to spare and with a respectable margin to the second place. Congratulations!

It seems quite hard for me to match this scoreboard with the (incomplete) list of teams coming to Astana, so maybe the readers of this blog can help: what is the highest-placed team in that scoreboard that is going to the World Finals?

There will be no contests this week, but this is just a small break before another huge event, as ICPC World Finals in Astana is already happening next week (website, brochure, some news on the left). So expect this blog to become a travel blog again, and we'll likely be organizing another stream of us solving the round in parallel, even though the meaning of "us" is unclear given that tourist is now a judge.

Thanks for reading, and check back next week for the Astana content!

A 4009 week

Codeforces Round 969 took place on Friday (problems, results, top 5 on the left, analysis, ratings). Edging out jiangly by just 5 points, tourist has finally broken the 4000 rating barrier. Even though one might say that 4000 is just a round number with no special meaning in the rating system, Gennady's recent run of form is simply amazing. He has won 6 out of his last 7 Codeforces contests, something that has not happened since 2015 (and even though I only checked Gennady's rating history, I can confidently say that it never happened for any other contestant), and which is even more impressive now given the much stronger competition in 2024. Congratulations!

The 3rd Universal Cup Stage 8: Cangqian followed on Saturday (problems, results, top 5 on the left). Gennady's team continued very impressive form here as well, winning the 6th stage in a row, and turning what was a very close two-horse race last season into a Max Verstappen-like domination (oh wait!). It was quite close this time, and by the end of the contest team HoMaMaOvO was solving problems faster, but they could not make up the time lost in the beginning. Congratulations to both teams and to the team Polish Mafia for the third full score!

Next week, IOI 2024 in Alexandria, Egypt will take front stage (participants). Together with the ICPC, the IOI is one of the two really big events in the competitive programming world. It is the event defining the year for the high school students who practice for it, and also the event where friendships can be made for the years to come. Good luck to all participants, check back my blog for the results next week (or just find them at the official website), and also check out the Swiss team's blog!

A two times two week

There were no contests that I wanted to mention last week, but in the week before that I forgot to mention the 3rd Universal Cup Stage 5: Moscow (problems, results, top 5 on the left). Team HoMaMaOvO was the only one to wrap things up before the last hour, but they still lost out to USA1 because they were a bit slower on the easier problems: this was one of the relatively rare cases where the ICPC and the AtCoder penalty time formulas place different teams in the first place. Congratulations to both teams, to team Polish Mafia who were as fast but had much more incorrect attempts, at to team MIT Isn't Training who were the only remaining team to AK!

What I did not forget to mention were two nice problems. The first one came from the EGOI: There is a sequence of n bits (each 0 or 1) a_i that is unknown to you. In addition, there is a permutation p_j of size n that is known to you. Your goal is to apply this permutation to this sequence, in other words to construct the new sequence b_i=a_pi. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation p_j, print an integer w, and exit. It will then be executed w more times. On the first of those runs, it will read the run number (1) and the permutation p_j again, and then it will read the sequence a_i from left to right, and after reading the i-th bit, it has to write the new value for the i-th bit before reading the next one. After processing the n bits, your program must exit. On the second of those runs, it will read the run number (2) and p_j again, and then read a_i (potentially modified during the first run) from right to left, and it has to write the new value for the i-th bit before reading the previous one. On the third of those runs, it goes left to right again, and so on. After the w-th run is over, we must have b_i=a_pi, where b_i is the final state of the sequence, and a_i is the original state of the sequence.

First, consider the case n=2. If the permutation is an identity permutation, we can just print w=0, and we're done. The only other case is when the permutation is a swap. Even in that case, there is actually not that many options for what we can do on the first pass. First, notice that we must not lose information after the first pass: all 2ⁿ possible sets of values of a_i before and after the first pass must be in a one to one bijective relationship, as otherwise we would have two initial states map to the same state after the first pass, and since our program is then restarted and we have no other memory except the current state of a_i, we would not be able to distinguish those two initial states, but the end results for them must be different.

Therefore after reading a₀ we have only two options: we either do not change it, or we change it to the opposite value a₀+1 (here and below we use addition modulo 2). But note that adding 1 on the first pass makes no difference if we have a second pass, since we could just add 1 on reading in the second pass instead. Therefore, without loss of generality we do not change a₀ on the first pass. For a₁ we have a few more options since we can also take a₀ into account. More specifically, in each of the two cases a₀=0 and a₀=1 we either keep a₁ unchanged or add 1 to it. If we take the same decision in both of those cases, then the whole first pass has been useless, as we can make the same adjustment on reading in the second pass. Therefore we must take different decisions. Which one we take in which case is also irrelevant, since they differ by adding a constant, which can be done in the second pass instead. Therefore once again we can essentially only do one thing: write a₁+a₀ as the new value for a₁.

By the same argument, on the second pass where we go from right to left we keep a₁ unchanged and write a₁+a₀ as the new value for a₀, and so on. After three passes, we actually obtain the well-known algorithm to swap two values without using additional memory (note that + and - are the same thing modulo 2):

• a₁=a₁+a₀
• a₀=a₁-a₀
• a₁=a₁-a₀

This means that we have applied the swap as needed. We could only do one thing for n=2, but this thing turned out to be exactly what we needed when w=3!

Now consider the case of higher n, but when the given permutation is the reverse permutation. The reverse permutation consists of independent swaps: we need to swap the 0th and the (n-1)-th bits, the 1st and the (n-2)-th, and so on. Therefore we can simply apply the above trick for swapping a pair for all of those swaps, and do it in parallel during the same 3 passes, therefore solving this case with w=3 as well.

We can do the same for any permutation that consists of independent swaps — in other words for any permutation of order 2. But how to handle the general case? It turns out that any permutation can be represented as a product of two permutations of order 2! To see how to do it, we can first notice that it suffices to represent a cycle of arbitrary length as such a product, as several cycles can be handled independently. We can then consider what happens when we multiply the following two permutations: the first permutation swaps the 0th and 1st elements, then the 2nd and 3rd elements, and so on; the second permutation keeps the 0th element in place, swaps the 1st and 2nd elements, the 3rd and 4th elements, and so on. It is not hard to see that every swap of the second permutation will swap two elements of different cycles, which means that those cycles will merge, which in turn means that in the end we will have one big cycle. The nodes along this cycle will not come in the order 0, 1, 2, ..., but it does not matter since we can renumber them arbitrarily to obtain a solution for any cycle.

This fact can be used to solve the general case with w=6 by applying each of the two permutations of order 2 using 3 passes. However, we can do one better and achieve w=5 if we notice that the last pass of applying the first permutation and the first pass of applying the second permutation can be merged into one. In order to see this, notice that we can make both of those passes go from left to right, and then each of them would find a new value for a certain bit using the old values of this bit and all previous bits; since our memory is not erased within one pass, we might as well compute the new value for that bit for the first pass of the second permutation using the values that would have been computed by the last pass of the first permutation instead, and write that one directly.

Going from w=5 to the optimal w=3 is a bit more technical, so I will not describe it in detail. To come up with my own solution for w=3 I relied on a more sophisticated version of the argument from the solution for n=2. After the second pass, we must leave the bits in such a state that the final state of each bit depends only on the state of this bit and the previous bits (since the third pass goes from left to right). And there are actually not too many different things that we can do during the first pass if we need to be able to leave the bits in such a state after the second pass. You can also check out alernative approaches in this Codeforces comment, or in the editorial. 

The second problem came from Codeforces: you are given an empty n times m grid (4 <= n, m <= 10). You need to write all integers from 1 to nm exactly once in the grid. You will then play the following game on this grid as the second player and need to always win. The first player takes any cell of the grid for themselves. Then the second player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves. Then the first player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves, and so on until all cells are taken. The second player wins if the sum of the numbers of the cells they have in the end is smaller than the sum of the numbers of the cells of the first player.

I did not solve this problem, but it turned out that I was on the right track :) On the left you can see the picture I had in my notes during the contest, where I placed 1, 2 and 3, and was trying to prove that if the starting player takes one of them, I can always take the remaining two for myself. On the right you can see the picture from the excellent editorial, to which I refer you for the actual solution, as I do not have much to add :)

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

An Eliška week

EGOI 2024 in Veldhoven, the Netherlands was the main event of last week (problems, results, top 5 on the left, analysis). Eliška has won for the second time in a row, this time with an even more commanding margin — huge congratulations! She was one of the four girls (together with Lara, Vivienne and Anja) who has participated in all four EGOIs, but it seems that this was the last year for all of them. Nevertheless, the new stars are already there as well, with so many medalists having several EGOI years ahead of them. It is great to see that this wonderful new community has been built and thrives!

Just like last year, I was onsite as a task author, but my task did not end up being used in the contest. I really need to up my game and submit more and better problems next year :) Of the problems that did end up in the contest, I'd like to highlight problem D from the first day which had the unusual multirun format. There is a sequence of n bits (each 0 or 1) a_i that is unknown to you. In addition, there is a permutation p_j of size n that is known to you. Your goal is to apply this permutation to this sequence, in other words to construct the new sequence b_i=a_pi. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation p_j, print an integer w, and exit. It will then be executed w more times. On the first of those runs, it will read the run number (1) and the permutation p_j again, and then it will read the sequence a_i from left to right, and after reading the i-th bit, it has to write the new value for the i-th bit before reading the next one. After processing the n bits, your program must exit. On the second of those runs, it will read the run number (2) and p_j again, and then read a_i (potentially modified during the first run) from right to left, and it has to write the new value for the i-th bit before reading the previous one. On the third of those runs, it goes left to right again, and so on. After the w-th run is over, we must have b_i=a_pi, where b_i is the final state of the sequence, and a_i is the original state of the sequence.

To get the full score on this problem you must always have w<=3, but I find that solving for w<=5 (which would give 95 points out of 100) is more approachable and potentially more fun. As another hint, two of the subtasks in the problem were as follows:

• n=2
• the given permutation is a reverse permutation

Can you see how to move from those subtasks to a general solution with w<=5? 

Codeforces ran Pinely Round 4 on Sunday (problems, results, top 5 on the left, analysis). As Um_nik rightly points out, tourist has continued his amazing run of form, and is potentially one more win away from crossing the magical boundary of 4000. Very well done!

I also share Yui's sentiment: it is very cool and quite surprising that problems H and I can in fact be solved. During the contest, I did not manage to make any significant progress in both of them in about 1 hour and 15 minutes I had left after solving the first 7. On the other hand, the (nicely written!) editorial almost makes them look easy :)

If you have not checked out the editorial yet, you can try crack problem I yourself. The statement is quite simple and beautiful: you are given an empty n times m grid (4 <= n, m <= 10). You need to write all integers from 1 to nm exactly once in the grid. You will then play the following game on this grid as the second player and need to always win. The first player takes any cell of the grid for themselves. Then the second player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves. Then the first player takes any cell that is not taken yet, but is adjacent (shares a side) to a taken cell, for themselves, and so on until all cells are taken. The second player wins if the sum of the numbers of the cells they have in the end is smaller than the sum of the numbers of the cells of the first player.

Given that the first player can choose the starting cell arbitrarily, it seems quite hard to believe that the second player can have any advantage. Can you see the way?

A 39 vs 17 week

Codeforces Round 959 sponsored by NEAR was the main event of last week (problems, results, top 5 on the left, analysis). AWTF participants have probably already returned home and were ready to fill the top five places in this round, but Egor has managed to solve everything and squeeze in the middle of their party. Congratulations to Egor on doing this and to tourist on winning the round!

In my previous summary, I have mentioned two problems. The first one came from AWTF: 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?

Even though the problem does not ask for it, it is actually super helpful to think where will the final big slime be located. For me, this would have probably been the hardest part of solving this problem. Why should one think about the final position if the problem only asks about the final time?..

After studying a few examples, one can notice that the final position is always equal to the average of the starting positions of the slimes. Having noticed this, it is relatively easy to prove: consider the function sum(a_i*w_i) where a_i is the position of the i-th slime, and w_i is its weight, and consider two slimes (a_i,w_i) and (a_j,w_j). The first one contributes -w_i to the velocity of the second one, while the second one contributes w_j to the velocity of the first one. Therefore together they contribute -w_i*wj+w_j*w_i=0 to the velocity of value sum(a_i*w_i), therefore that sum stays constant. And it also does not change when two slimes merge, therefore it is always constant and has the same value for the final big slime.

Now is the time for the next cool observation, this one is a bit more logical though. Consider the last two slimes that merge. They split the original slimes into two parts. What happens to the weighted averages of the positions of those two parts sum(a_i*w_i)/sum(w_i)? By the same argument as above, influences within each of the parts on that average cancel out. The influences of the parts on each other do not cancel out though, but we can easily compute them and find out that those two averages are moving towards each other with constant velocity equal to the total weight, in other words k.

Therefore if we know which two parts form the two final slimes we can find the answer using a simple formula: (sum(a_i*w_i)/sum(w_i)-sum(a_j*w_j)/sum(w_j))/k, where j iterates over the slimes in the first part, and i iterates over the slimes in the second part.

And here comes the final leap of faith, also quite logical: the answer can actually be found by finding the maximum of that amount over all ways to choose a prefix and a suffix as the two parts. This can be proven by noticing that the difference between averages starts decreasing slower than k if some slimes merge across the part boundary, therefore the number we compute is both a lower bound and an upper bound on the actual answer.

We have not yet dealt to the fact that we have to choose k slimes out of n, but seeing the above formula it is pretty clear that we should simply take a prefix of all available slimes for the sum over j, and a suffix of all available slimes for the sum over i. Now all pieces of the puzzle fit together very well, and we have a full solution.

The second problem I mentioned came from Universal Cup: 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?

A natural question to ask is: how can two such strings be the same? If we align two different ways to erase a substring of the same length that lead to the same result, we get the following two representations of the same string:

abcd=aebd

where in one case we delete the substring c, and in the other case we delete the substring e to obtain the result abd. We can notice that such pairs of equal prefix+suffix concatenations are in a 1:1 correspondence with pairs of equal substrings within the string (two occurrences of the substring b in the above example). It is not true though that our answer is simply the number of distinct substrings, as we have merely proven that the sum of c*(c-1)/2 over all repeat quantities c of equal substrings is the same as the sum of d*(d-1)/2 over all repeat quantities d of equal prefix+suffix, but that does not mean that the sum of c is the same as the sum of d.

However, this makes one think that probably the suffix data structures, such as the suffix tree, array or automaton, will help solve this problem in the same way they help count the number of distinct substrings. This turns out to be a false path, as the actual solution is much simpler!

Consider the middle part of the above equation (bc=eb), and let us write out an example with longer strings for clarity:

abacaba
abacaba

We can notice that the following are also valid ways to obtain the same string:

abacaba
abacaba
abacaba
abacaba

So the structure here is simpler than in counting distinct substrings. In order to count only distinct prefix+suffix strings, let us count only canonical respresentations, for example those where the prefix is the longest. The criteria for when we cannot make the prefix even longer is evident from the above example: the next character after the prefix (the one that is removed) must be different from the first character of the suffix, if any. Therefore the answer is simply equal to the number of pairs of characters in the given string that differ, plus n to account for the representations where the suffix is completely empty. 

Thanks for reading, and check back next week!

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.

AWTF24 contest

AtCoder World Tour Finals 2024 took place today (problems, results, top 5 on the left, broadcast recording, analysis). 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.

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.

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) A_i, B_i, C_i, and draw the point A_i+B_i-C_i (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 e^2πi/n. Drawing a new point corresponds to computing A_i+B_i-C_i 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, xy², ..., xy^k-1, where y is such that y^k=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=e^2πi/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=e^2π/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=e^2π/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 u^t-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 uⁿ-1=Φ_n(u)*g_n(u) (where g_n(u) is just the result of dividing uⁿ-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 g_n(u) must be 0. However, from the structure of the cyclotomic polynomials we know that g_n(u) is a product of cyclotomic polynomials of smaller order, so if it was equal to 0, it would mean that the identity u^t-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!

A code week

Universal Cup started its 3rd season this Saturday with Stage 1: St Petersburg (problems, results, top 5 on the left, analysis). Team 03 Slimes was in the lead for a long time, then paused a bit and gave everyone a chance to catch up, only to solve 3 more problems in the last hour and claim the clear first place. And all that even though our team stole one of their usual team members and they had to participate with just 2. Well done!

Solving problem B was very satisfying, and I think describing its solution next week will help me understand the underlying math better, so here is the problem statement: 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) A_i, B_i, C_i, and draw the point A_i+B_i-C_i (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?

Initially the problem seems quite straightforward as we can just simulate the process and check the required condition using some simple geometric formulas. However, it turns out that 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. So how to solve this using only integer computations?

Codeforces Global Round 26 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). One of the highlights of the round was an amazing successful experiment, but there was also a pretty close fight for the first place, to the point that jiangly needed just one successful hack to win, which he unsuccessfully attempted. I wanted to check if he had a chance, in other words if there were any failed system tests in jiangly's room, but I could not find a way to find which of the 646 available rooms is it. Does anybody know how to find the room of another contestant? Apparently this link was staring me in the face, it is shown at the top of the user's submission history, which appears after a double-click in the corresponding standings cell. And it turns out that there were no failed system tests in jiangly's room, which means that his only chance for the required +100 could lie in some anti-hash tech.

In any case, tourist held on to his first place, and increased the gap at the top of the rating list. Interestingly, the top 3 in this round coincided with the top 3 by rating after Benq did find his successful hack. Congratulations to tourist, jiangly and Benq!

Thanks for reading, and check back next week.

A return@week

Kotlin Heroes Episode 10 on Codeforces was the main event of last week (problems, results, top 5 on the left, analysis). Only solutions in Kotlin programming language could be submitted. Long gone are the days of IDEA's Java-to-Kotlin converter, at least nobody in the top 20 seems to use it, and I think the Kotlin Heroes series is quite a success in introducing people to Kotlin and getting them to like it. At the same time, Kotlin knowledge is still not at 100% in the community, so other translation tools are on the rise :)

The top 2 were the same as in the previous edition, and they were the only participants to solve all problems. However, this time arvindf232 was faster and earned a well-deserved victory. Congratulations to arvindf232 and tourist on the great performance!

Tourist's wrong submissions on E and F have seriously damaged his winning chances. The wrong submission on E (link, compare to correct) stems from a wrong understanding of an advanced language feature, return@repeat, which turned out to mean continue and not break :) And the wrong submission on F (link, compare to correct) stems from not using a prewritten code library, more specifically a modint class. The winner's submission to the same problem does use prewritten code to deal with modular arithmetics, but interestingly it is not done through operator overloading, but rather through defining new infix operations that also refer to a global variable, leading to weird-looking code like ret[paths] = ret[paths] mp (count mm FACT.choose(options, k-1)), where "mp" and "mm" stand for modular addition and multiplication. arvindf232 or others reading this, what is the reason for this approach?

Thanks for reading, and check back next week!

A busy beaver week

The final round of the MIT Informatics Tournament "M(IT)^2" 2024 Spring Invitational took place in Boston last week (problems, results are not published yet, top 5 on the left, online mirror results). Even though the competition was open to everybody who is willing to travel to Boston, the top 4 places were occupied by those who have won ICPC gold medals for the MIT team in the past :) Adam Gąsienica-Samek in the fifth place, to the best of my knowledge, is still a high school student in Warsaw (even though the last name does bring some ICPC memories; is it a coincidence or are they related?). Maybe he will win ICPC gold medals for MIT in the future :) Congratulations to the winners, and also to the organizers! Looking at how most of them are not graduating for at least a couple more years, I hope for more tournaments to come.

Thanks for the quick reading, and check back next week.

A notorious week

Codeforces Round 942 was the first event of this week (problems, results, top 5 on the left, analysis). tourist has returned to the top of the scoreboard, and also to the top of the rating list — congratulations! It is also great to see that jqdai0815 keeps participating actively and getting great results after going for a long break during the pandemic. Who knows, maybe even I still have a chance to return to the top 10 :)

On Saturday, we hosted the online mirror of the Helvetic Coding Contest 2024 (problems, results, top 5 on the left, onsite results, analysis). This is originally an onsite competition that took place in Lausanne in April, it is ran completely by a group of student volunteers at the EPFL, who take care of all tasks such as finding sponsors, advertising the event, planning the onsite events, setting up the onsite competition environment, organizing meals, and of course preparing the problems. Seeing this volunteer-driven contest appear out of nowhere after a five-year hiatus really inspires and makes me proud of the competitive programming community. Therefore I have submitted two problems this year (A and D), I hope you liked them!

But I also need to mention that this year one of the problems unfortunately was the same as Problem 5 of the November Lunchtime 2021 at Codechef. As you can see, there were quite a few competitors that took part both in that round and in this week's mirror, and there could be much more who have upsolved it or heard about it from a friend, which of course made the contest worse, even though it was unrated. Below I am trying to share my understanding of what happened, but note that my goal is not to absolve myself from the responsibility — I think it was a failure, and I apologize for it.

As it is often the case, the reason for this seems to be bad communication along a chain of people operating with good intent. The original author (by the way, nice problem!) clearly knew that this problem was used for the Lunchtime when sending it to one of the HC2 organizers, but expected the HC2 organizers to make their own judgement about how appropriate it is to use it in the onsite event, they likely did not even know that a mirror might happen.

But then as the information about this problem propagated from one HC2 organizer to another through a couple of more hops, this fact was lost, with various people thinking that this problem was only used for a private contest with a few participants, or that this problem was prepared but rejected and not used at all in the past.

What probably made the matter worse is that different people have different perceptions of what is OK (should we never give the same problem to two contests? Or maybe it is OK if the set of participants is not intersecting and it was not available publicly after the first one? Or maybe it is OK if the first occurrence happened long ago? Or maybe it is OK if the second round is unrated?), and this perception affects what information about the problem they decide to communicate to other people.

Moreover, people often expect other people to have the same perception of the situation, and therefore treat the lack of communication as information as well. As a result, the people organizing the mirror (such as myself) did not try to figure out more information about the origins of this problem even though we knew from Polygon that it was prepared a bit earlier, assuming that other organizers who are closer to the beginning of this communication chain know the problem better and therefore are in a better position to judge if it is appropriate to use, so if they say nothing, all is good. But this line of reasoning fails to account for the fact that the people closer to the beginning of the communication chain have a different context (might not even be aware that there's a public mirror, for example) and different perceptions of what is OK.

So here is my takeaway from all this: more communication is always better when preparing a contest! I will try to keep this in mind when preparing future rounds, hopefully including the Helvetic Coding Contest 2025.

In my previous summary, I have mentioned a Codeforces problem. You are given two integers n and k. Your goal is to create a (multi-)set of positive integers such that among its sub(-multi-)sets we can find ones which sum to any integer between 1 and n, except k. n is at most 10⁶, and the set you create must have at most 25 elements.

The first part of the solution is somewhat clear/standard: we need to be able to represent all numbers between 1 and k-1, but not the number k. For this, we can take all powers of two less than k: 1, 2, 4, ..., 2ⁱ, such that 2ⁱ<k<=2ⁱ⁺¹, but then in order to not overshoot k we should replace 2ⁱ with k-2ⁱ: then the sum of all numbers is k-1, and clearly all numbers between 1 and k-1 are still representable.

Then, as long as all other numbers that we take into our set are at least k+1, k will still not be representable. But how do we cover all numbers between k+1 and n? After trying to come up with something concrete on paper unsuccessfully for some time, I've decided to just run a dynamic programming that remembers which numbers are representable, and repeatedly take the smallest non-representable number. It is not obvious why this will have at most 25 elements, but it is very easy to try.

Here is the output of this approach for n=1000000, k=5:
21
1 2 1 6 11 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288

And for n=1000000, k=6:
21
1 2 2 7 13 19 38 76 152 304 608 1216 2432 4864 9728 19456 38912 77824 155648 311296 622592

Now we can notice a pattern: the numbers we add in the second phase are k+1, 2k+1, 3k+1, 2(3k+1), 4(3k+1), 8(3k+1), ...  We can now both be more confident that it will always fit under 25 elements, and also try to prove that this pattern always works. Or just submit. 

My submission in the actual contest is more complex than that, and even includes some randomization :) The reason for that is that I had a bug in the implementation of the simple dynamic programming which made me think it produces more than 25 elements sometimes, adding randomization helped fit under 25 but did not fix the bug, and after fixing the bug I did not check if randomization was still needed.

Thanks for reading, and check back next week!