A 17107 week

TopCoder SRM 851 was their first round after a long while (problems, results, top 5 on the left). Only three contestants got the 1000 right. Out of those, snuke had a small lead after the coding phase despite a resubmit on the 1000, and he managed to extend the lead with an active challenge phase (+2-2). Well done!

Meta Hacker Cup 2023 Final Round was the last but also the most important event of the week (problems, results, top 5 on the left, analysis). The scoreboard was quite exciting to watch during the round, as different people went for completely different orders of tackling the problems (and also for creative ways to avoid thinking too much about cacti!). The order did not matter in the end as only Gennady managed to solve all problems, which was actually necessary for him to claim the first place from Benq who had a better penalty time. Congratulations Gennady on winning the 5th Hacker Cup title!

As I saw the point values for the problems, the optimal strategy seemed obvious: problem A with its 19 total points effectively has weight 2 for the penalty purposes, so assuming the 19 points accurately reflect its difficulty, it is much better to solve it in the beginning. Combine this with the fact that it was a constructive problem, the type I typically enjoy solving, and you can guess what I did for the first 2 hours of the 4-hour round :) I think the main reason it took so long was that I was constantly quite close to a working solution, and therefore it always seemed that I need just one more small trick, so I went for small tricks instead of rethinking the approach. I ended up accumulating a lot of those small tricks: in addition to k->2k and k->2k+1 steps that everyone likely used, my solution also used k->4k-1, k->8k-1, ... (therefore using the A=A-1 primitive that the official analysis dismissed so easily :), and also k->3k and k->3k+2; to accommodate such a wide variety of possible steps, I chose the cells to include into the labyrinth outside of the main path dynamically based on the type of the next primitive I needed.

Even though spending 2 hours on this problem ruined my (mostly theoretical anyway) chances for a good result, I am still grateful to the organizers for not setting the tightest possible constraints and therefore allowing alternative approaches like mine.

One of the problems that I could not crack in the remaining time even though I was very close, and that I think is quite educational despite having a very ugly statement, is Problem E: two players are playing a nim-like game, starting with two piles of stones. In one move, a player first chooses one of the remaining non-empty piles, let's say this pile has k stones. Then they can take between A_k and B_k stones from this pile, and they also must create a new pile with C_k stones (1 <= A_k <= B_k <= k, 0 <= C_k < k). Since 1 <= A_k and C_k < k, this game will eventually terminate, and the player unable to make a move loses the game. Your goal is to find for each size (between 1 and n) of the first of the two initial piles the smallest size of the second initial pile that leads to a losing position, and print the sum of those n sizes. n is up to 2 million.

Thanks for reading, and check back next week for the results of the most important round of December, the last AGC of the year! Thanks to Um_nik now I know that 12 people (up from 8) qualify to the WTF, which means that even the second place will probably do ;)