A turning red week

The ICPC World Finals in Luxor was the main event of the week. The finals for two years were running in parallel, and our team was solving the mirror of the 2022 season, the 46th World Finals (problems, results, top 12 on the left, official broadcast, our stream). MIT team was dominating the round, solving 8 problems in less than two hours, getting to 9 within 3 hours, and leading by 2 problems for a long time. This reminds me of my own participation in 2005 World Finals (frozen detailed standings, final coarse standings), where we got to 7 problems slightly after the 3 hour mark and were leading 7-5, and with a huge advantage in penalty time, only to get stuck in problem G and have the Shanghai team overtake us thanks to solving 3 problems in the last hour. A very similar thing happened here with another team from China, Peking University, who solved 3 problems in the last 70 minutes and overtook the unlucky MIT team who was stuck with 25 incorrect attempts on problem S. Congratulations to both teams on the amazing performance!

Problem T "Carl's Vacation" was the trademark World Finals geometry problem. You are given two right square pyramids with integer base coordinates, integer height, and non-intersecting (but possibly touching) bases lying on the same plane. What is the shortest path between the tips of the pyramids that always goes either on the surface of one of the pyramids, or on the plane? The coordinates are up to 10⁵, and the output must have relative error of at most 10^-6. Can you see a way to implement this without getting stuck in the details?

The finals of the 2023 season, the 47th World Finals, had 5 shared problems and 6 unique problems (problems, results, top 5 on the left). The Higher School of Economics team took the lead a bit before the 2 hour mark and held it for most of the remaining contest, only allowing the MIPT team to lead briefly for 10 minutes in between. Unlike the first contest, nobody was able to solve the 10th problem and therefore HSE's win stood. Congratulations!

For me, the most amazing part of the Luxor event was meeting so many friends and acquaintances who live all over the world. The ICPC community is amazing by itself, and it also serves as a basis for multiple sub-communities that came together to meet in Luxor, such as the ICPC Live team, or the Universal Cup organizers and participants, or the ICPC alumni who now work for the sponsors, or just came as guests, such as myself. Huge thanks to the organizers, to the sponsors, and to the participants!

Thanks for reading, and check back next week.

ICPC World Finals Luxor mirror stream

The ICPC World Finals in Luxor are happening tomorrow. You can find a lot of useful links here, but of course you should tune in to watch me, Gennady and Kevin solve the mirror round! We will start around noon Egypt time, maybe a bit earlier. To warm up, you can check out the previous streams we did with Mikhail instead of Kevin (2017, 2018, 2019, 2020).

A NWERC week

The 2nd Universal Cup Stage 22: Hangzhou was the only event of last week (problems, results, top 5 on the left, analysis). Team USA1 has returned to the winning ways after a short slump in form, already leading on 12 problems but still finishing everything with an hour to spare. Congratulations!

Team "nwerc is bad" from the Univerity of Oxford also reminded that they are one of the favorites for one of the upcoming World Finals in Luxor by earning an excellent fourth place and being the best ICPC-active team this time. Well done!

Thanks for reading, and check back next week for more meaningful content :)

A Delft week

The 2nd Universal Cup. Stage 21: Delft was the main event of last week (problems, results, top 5 on the left, analysis). Team HoMaMaOvO won the round and continued closing the gap in the overall standings, which is now down to a mere 0.16 points. Winning one more stage (their 9th of the season) would be enough for them to overtake USA1, since it would bring at least 1/4*(3/4)**8*(200-175)~=0.62 points.

As both teams solved everything this time, the key advantage for HoMaMaOvO seems to have come from solving a tricky geometry problem B (and one can't complain that tricky geometry problems were unexpected) very fast from the first attempt. Well done!

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

A stable denominator week

TopCoder returned last week from another long break with SRM 852 (problems, results, top 5 on the left). The 1000-pointer was about counting k-th roots of a specific permutation, and it took the winner SSRS_ just 3.5 minutes since they reused their submission for a more general problem about counting k-th roots of any permutation. More generally this problem did not present as much of a challenge for the top participants as the 500-pointer, which saw many solutions fail and therefore offered a lot of challenge opportunities. Of the three contestants who managed to solve everything, kotatsugame was behind after the coding phase but managed to recover to the second place thanks to 200 challenge points. Congratulations to all three on the great performance!

The 2nd Universal Cup. Stage 20: Ōokayama followed, as usual, on Saturday (problems, results, top 5 on the left, analysis). 16 problems in a round is still a lot even by today's standards, but this still did not stop team HoMaMaOvO from solving all of them with 6 minutes to spare :) Well done! This is their 7th win of the season compared to 9 for USA1, and they are definitely still in contention for the overall first place.

Finally, Codeforces Round 921 wrapped up the competitive week also on Saturday (problems, results, top 5 on the left, analysis). Having dealt with the four easier problems in the first hour, I've decided to focus on problem F since there it seemed that we just need to solve the n=3 case and the rest will easily follow, while problem E gave some generating function vibes :) Unfortunately even the n=3 case in F turned out too hard for me. I have even implemented a brute force that tried different random strategies and it still could not solve n=3. The reason for that was probably the fact that the strategies I tried were non-adaptive: they asked the same questions irrespective of the answers.

Implementing a brute force over adaptive strategies seemed harder, so I've decided to give E another chance. I've realized it feels difficult because the number of choices we have always changes, therefore we are multplying probabilities with different denominators and it's not clear how to do the summation over different trajectories nicely. But then I remembered I already had this feeling in the past, and writing about this in my blog :) So I tried searching for [divide by the sum site:blog.mitrichev.ch], and for some reason this search returned what I was looking for on the first page. I've re-read that solution, and remembered the key trick: even if the overall number of choices is different every time, since all choices have the same probability at each step, the relative probability for a particular subset of choices of fixed size will always be the same. In the linked problem it was just 2 options each with probability 50%, while in problem E this time, if we focus on whether we visit a particular pair (x,y) or not, the number of choices affecting this outcome is always x+y, no matter the current state, so we can compute the probability of such visit happening very nicely.

There was still some work to do to improve the complexity from O(n²) to O(n*logn), and luckily I managed to do it before the end of the round. This was of course still not enough to compete with jiangly and others who focused on problem E earlier. Congratulations on the win!

Thanks for reading, and check back next week.

A Frobenius week

The 2nd Universal Cup Stage 19: Estonia was the only event of this week (problems, results, top 5 on the left, analysis). Team 03 Slimes, who are a distant third in the overall standings, won their second stage of the season in an impressive fashion, beating the top two teams in the overall standings by two problems. Judging by the +32, some squeezing was involved, potentially of an approach that was not intended to pass — but that is also an important skill in algorthmic competitions, so well done! I am also not sure who actually was on the team this time, as Mingyang Deng is also listed as part of MIT CopyPaste on the same scoreboard.

Possibly rejuvenated by the news that the 2022 ICPC World Finals seem to be finally happening in April, Harbour.Space P+P+P followed in second place — congratulations as well! (jk, they actually wrote this contest as part of the Osijek camp back in September, so they were still practicing towards the original dates).

Finally, this week an anonymous LGM published a very nice result that drops a logarithmic factor from matrix exponentiation. Of course, theoretically we already know ways to drop much more from the asymptotic complexity, but all of those are not really beneficial in practice on the time limits prevalent in the algorithmic competitions. This result, however, did allow to slash the fastest time to find a power of a 200x200 matrix roughly 3x (compared to the straightforward binary exponentiation method; the judge also has some fast submissions from November 2023 that start with "vector<ll> f=a.poly();", so possibly some other version or precursor of this result?..

I guess now it will be a bit harder to separate wrong submissions when preparing problems, on the other hand the squeezing toolkit just got a bump :)

Thanks for reading, and check back next week!

A HoMaMaOvO week

The 2nd Universal Cup. Stage 18: Dolgoprudny was the only event of last week (problems, results, top 5 on the left, analysis). Team Hailiang FLS + RDFZ: Anonymous were the first to 6 problems at 1:58 into the contest, followed by Team HoMaMaOvO at 2:15. The remaining problems were much harder, and the teams were probably faced with tough choices between pursuing multiple problems in parallel and focusing on one problem to get it accepted. Both teams submitted 3 problems in the remaining time, and Anonymous were the first to get one of them accepted, but then HoMaMaOvO overtook them by getting two in the last hour. Congratulations to both teams!

In my previous summary, I have mentioned a Codeforces problem: consider a rooted tree where each node either has a leaf, or has exactly two children. For each node with two children, one of the edges to the children has weight 0, while the other has weight 1. We run a depth-first traversal of this tree starting from the root, and for each leaf we print the sum of weights on the path from the root to this leaf. Now we are given just the printed sequence and not the tree, and need to answer if there exists a tree as described above that could lead to this sequence being printed? For example, 2 1 0 1 1 can be printed, but 1 0 2 1 3 can't. The length of the given sequence is up to 2*10⁵.

The key observation in this problem is to imagine that we are building our tree step by step. Initially, we have only the root, which is also a leaf, so the sequence printed will be just 0. Now we add two children to the root, using edges with weights 0 and 1, and the depth-first search traverses them in some order. Depending on this order, the sequence we get will become either 0 1 or 1 0. We continue by repeatedly taking a leaf and adding two children to it, and the sequence always changes in the following manner: if the number corresponding to this leaf was x, then we insert x+1 into this sequence either directly to the left or directly to the right of it. And we can apply this operation to any number in the sequence, so we just need to check if the sequence we are given can be obtained starting from just the number 0 using this operation repeatedly.

Now let us look at the process in reverse, in other words we will repeatedly remove numbers that are adjacent to a number smaller by 1 until only 0 is left. What should we remove first? All numbers in this sequence that are adjacent to a number smaller by 1 are candidates. Now consider what happens when we remove number x that was adjacent to x-1: now x-1 becomes adjacent to some other number y. When y=x-2, the number x-1 become a candidate. When y=x, the number y becomes a candidate. In all other cases, no new candidates appear. This means that the new appearing candidates are never bigger than the number being removed.

Therefore we can safely remove any of the candidates with the highest value: we will never get candidates with even higher value in the future because of the previous argument, therefore those numbers themselves will never be useful to support removal of another number. So we can just keep removing one of the remaining highest values while it is possible, and we either reach a single 0, in which case we have found a solution, or we get stuck when all remaining highest values cannot be removed, in which case there is no solution.

Thanks for reading, and check back for more!