Friday, September 20, 2024

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!

Wednesday, September 18, 2024

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)!

Tuesday, September 17, 2024

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!

Wednesday, September 11, 2024

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!

Sunday, September 1, 2024

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!

Sunday, August 11, 2024

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) ai that is unknown to you. In addition, there is a permutation pj 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 bi=api. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation pj, 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 pj again, and then it will read the sequence ai 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 pj again, and then read ai (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 bi=api, where bi is the final state of the sequence, and ai 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 2n possible sets of values of ai 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 ai, we would not be able to distinguish those two initial states, but the end results for them must be different.

Therefore after reading a0 we have only two options: we either do not change it, or we change it to the opposite value a0+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 a0 on the first pass. For a1 we have a few more options since we can also take a0 into account. More specifically, in each of the two cases a0=0 and a0=1 we either keep a1 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 a1+a0 as the new value for a1.

By the same argument, on the second pass where we go from right to left we keep a1 unchanged and write a1+a0 as the new value for a0, 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):

  • a1=a1+a0
  • a0=a1-a0
  • a1=a1-a0

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!

Monday, July 29, 2024

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) ai that is unknown to you. In addition, there is a permutation pj 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 bi=api. Your solution will be invoked as follows. On the first run, it will read the run number (0) and the permutation pj, 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 pj again, and then it will read the sequence ai 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 pj again, and then read ai (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 bi=api, where bi is the final state of the sequence, and ai 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?