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!

A jiangly week

The qualification round of the MIT Informatics Tournament "M(IT)^2" 2024 Spring Invitational took place last Sunday after I published my summary for the week (problems, results, top 5 on the left, analysis, my screencast). Mingyang Deng was very fast in general, but the final blow was that he could solve P4 a lot faster than other top competitors (25 minutes compared to about 40 for others), leading to a first place with quite significant margin. Congratulations!

More generally, it is awesome to see a new tournament with an onsite round (which was initially USA-only but has since expanded). It's a pity that I will not be able to make it since it was only announced a few weeks in advance. Good luck to all onsite participants, and have fun!

One of the rare TopCoder rounds, SRM 854, took place on Thursday (problems, results, top 5 on the left). This round has once again demonstrated TopCoder's unique format. Being the only competitor to solve the 1000-pointer was only enough for the 3rd place for Nyaan, since nwin and hitonanode accumulated an enormous amount of points during the challenge phase thanks to a corner case in the 350 that was not covered by the sample tests (and TopCoder does not check anything else on submission). Congratulations to all three!

One could argue that it is not very nice to (likely intentionally) exclude this corner case from the sample tests. However, I think it was fair game because there was this phrase in the problem statement: "Only the boxes matter, your final position does not: as soon as all the boxes are at the same coordinate, the task is complete regardless of your position at that moment." This phrase makes no sense if you miss this corner case, and since problemsetters do not write random things in statements, one had to stop and think why this was emphasized.

More generally, I think the TopCoder format with no pretests and therefore many submissions failing system tests often leads to very exciting rounds, allows more people to win from time to time, and also rewards those who can write code with less bugs and/or know which amount of testing is enough. I like all those properties, and therefore it is very sad that this format is slowly fading into the void.

Finally, Codeforces Round 941 wrapped up the week on Saturday (problems, results, top 5 on the left, analysis). The round had a bit fewer strong participants than usual since the Yandex Cup finalists could not participate, but still winning it was no small feat. jiangly was having a very good round, and was the first to solve problem D near the middle of the contest, but then he probably (or maybe not? Actually I have no idea) looked at the scoreboard and realized that people are solving E faster than D, and therefore even his great performance on the first four problems might not be enough to be in first place after five, simply because he chose the wrong order. On the other hand, rainboy had already demonstrated at that point that F is solvable in less than an hour, so going for F was a risky but potentially contest-winning move. And it worked out very nice for jiangly with 7 minutes remaining. Well done!

Some people even retire after achieving the first place in a Codeforces round, but even though for jiangly it is already the 13th first place, and he has also achieved the WTF first place last year and the ICPC first place last week, it feels that the story might be just starting :)

Problem B was a cute constructive one. 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. Can you find a way?

In my previous summary, I have mentioned a World Finals problem (problem T here): 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.

This problem was not very beautiful. In fact, if you're after beautiful geometry problems, you should check out jeroenodb's recent post. But I think the problem was very educational, because it both demonstrated the need to understand one's own solution in detail, and the superiority of ternary search :)

First, we notice that on the suface of each pyramid we must go in a straight line, and the same is true for the plane. So our path will always have three straight segments, and the only choice we have is where the two points where those segments meet lie on the base of each pyramid.

This is where the two main approaches branch. Our approach, and the approach of many other teams who struggled with this problem during the round, went like this: for each base square, we consider 8 options (so 64 options total): the meeting point is either one of the four vertices, or on one of the four sides. If it is one of the vertices, we just need to find the shortest path from that vertex onwards. If it is on one of the sides, things are more complicated: we notice that we can "fold" the side of the pyramid over this side towards the plane, and the path lengths passing through this side will not change. Now we just need to find the shortest path on the plane between the folded locations of the pyramid tips, and the shortest path on the plane is a straight segment. However, for us to be able to "unfold" this segment back to a path in the original problem, we need to make sure that this segment actually intersects the side or two sides that we used for folding. So you spend quite some time implementing all this carefully, submit, and of course get WA.

The reason for the WA (and I was only able to figure this out because Kevin told me, I am not sure I would find this myself during the contest time at all) is that the segment shouldn't just intersect the two sides used for folding, it should intersect them in the correct order! The picture on the left demonstrates two tall pyramids standing next to each other, and how that leads to a segment that does intersect the two sides used for folding, but in the wrong order, and which therefore does not correspond to a valid path in the original problem. You fix this, and then you get OK.

However, there is a much better approach: it is somewhat clear (one can derive a formal proof from the first approach I guess, but one can also submit without proving) that if we fix which two sides of the base squares the two meeting points lie on, the path length is a convex function, so we can just use two nested ternary searches to get a very easy to implement solution with no corner cases. In this approach we don't even need to handle the base square vertices specially, they will be considered as part of the corresonding sides.

Thanks for reading, and check back next week!

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.