A grand week

After a bit of a summer lull the contests are starting to gain steam again. Last week started with the Codeforces Round 1053 on Wednesday (problems, results, top 5 on the left, analysis). I got stuck in the implementation details of problem D for almost a full hour, then spent some time implementing a local tester for E2 to see how far my solution for E1 was from solving E2 (quite far) and trying to improve it by replacing binary search with ternary (only made it worse), and therefore when I opened problem F and got the right idea almost immediately (use length 2 in the first step, consider the diameter in the second step to reduce the problem to one on the line) I could not finish the implementation in time, even though 15 minutes were added to the contest duration. Some quite usual scenes for me these days :)

It was usual scenes for Kevin as well, only for him it meant solving F much faster than everybody else and getting the first place by a margin. Congratulations!

I would like to highlight the interactive problem E (E1, E2) from this round: there is a hidden array of size 2n-1, where each number between 1 and n appears twice, except one which only appears once, and you need to find out which one. To do that, you can only ask queries of the following form: choose a collection of indices in the array, and a number between 1 and n, and you will be told if this number appears at at least one of those indices in the array. In E1, we have n<=300 and you need to find the answer using at most 4n+2*ceil(log₂n) queries. In E2, we have n=300 exactly and you need to find the answer using at most 925 queries. What do those differences in constraints tell you?

AtCoder Grand Contest 073 on Sunday brought another AI story (problems, results, top 5 on the left, analysis). I got off to a good start by solving A faster than everyone in the screenshot on the left, but the remaining 2.5 hours of the round were not very productive. I felt that I was quite close on B and I kept updating my solution to handle yet another counterexample found by the stress test, but I failed to generalize and to notice that one of the corner cases in my wrong solution could be made into a correct solution.

tour1st has solved that same B in just over 8 minutes, and got the three solvable problems done almost half an hour before everybody else. Congratulations on the win!

The big story of this round was of course this announcement (some reactions), which was followed up by this rule change. AtCoder Grand Contest was the last place where using AI was explicitly allowed and even encouraged, hoping to discover new creative ways to use AI to improve the humans' problem solving ability. However, in this round it turned out that AI can solve problem C without human help, and this was the last straw that made AtCoder admins disallow the use of AI in AGC going forward, to avoid the contest turning into a prompting competition, and into a "who has money to pay for access to a better model" competition.

Here is that fateful problem C: you are given a tree with n<=5000 vertices. We choose a real weight a_i for each vertex i from the range [-n+1,1] independently and unformly at random. Now, for each vertex i we compute x_i as the highest sum of weights in a connected subtree containing vertex i. Now we define the score of the tree as follows: if for all i we have 0<=x_i<=1, then the score is equal to the product of all x_i, otherwise it is 0. You need to find the expected value of the score. Can you keep up with AI here?

Thanks for reading, and check back later for this week's summary!