Thanks for the quick reading, and check back next week.
Algorithms Weekly by Petr Mitrichev
Wednesday, May 15, 2024
A busy beaver week
Sunday, May 5, 2024
A notorious week
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 106, 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, ..., 2i, such that 2i<k<=2i+1, but then in order to not overshoot k we should replace 2i with k-2i: 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!
Sunday, April 28, 2024
A jiangly week
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!
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!
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 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!
Thursday, April 18, 2024
ICPC World Finals Luxor mirror stream
Thursday, February 15, 2024
A NWERC week
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 :)