Sunday, April 28, 2024

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 106, 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 105, 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!

Friday, April 19, 2024

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 105, 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.

Thursday, April 18, 2024

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