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!