Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

I have to bring you the bad news that it solved both A and C :(

It is unfortunate that we lost our last AI-allowed contest.

Anyways, thanks for the contest and thank you for updating the rules so quickly.

Is there an easier/more intuitive solution to A (other than the editorial)?

I’ve always hoped that humans would remain stronger than AI on creative problems, and I saw AGC as one of the last contests where problems felt truly new and unconventional. It would be sad if AIs were officially banned from AGC, because to me that would mean:

1. We’re admitting humans are already worse than AI, and
2. No one in the community will even try to design AI-proof problems anymore.

That possibility makes me feel a kind of existential crisis ...

(As an aside: I actually think it’s fine if problems can’t be solved directly by AI. For example, take GPT-5 Pro, feed the problem to it in four separate threads, with one query each. If it doesn’t solve it in any thread, I’d consider that acceptable. The current instances of AI-solvable problems won't pass this test. )

Welcome to post AI era! I am so pessimistic about the future of online programming contest. Rating is just a meaningless number from now on.

AI may be a problem but man oh man the problems from atcoder are next level. Top notch alchemy of mathematics and algorithms.

I bet AI will even help create the most mind numbing problems even if it might not invent new algorithms.

Problem B shares very similar ideas to HugeGraph from topcoder SRM 600.5. Jiangly wrote a solution for it which is extendable to the AGC problem: https://www.luogu.com/article/qacbujm3

In the Problem B, how to prove it's always exist a $$$f(A_1, A_2, \dots, A_n)$$$ jump that corresponds the optimal jump of $$$f(A_1, A_2 - A_1, \dots, A_n - A_1) + A_1$$$ without violating the third condition(Never jump consecutively the same distance in different directions.)?

I think there's an approach for Problem B with a time complexity of $$$O(n\log n + \log\max(A)\log n)$$$.

Let's continue using the definition of $$$f$$$ from this editorial. Then, the process of calculating $$$f$$$ is similar to the Euclidean algorithm.

Each time we calculate, except for $$$a_1$$$, all the other numbers are subtracted by the same value $$$x$$$. It's similar to adding $$$x$$$ to $$$a_1$$$ and then subtracting $$$x$$$ uniformly. The relative order of $$$a_2$$$ to $$$a_n$$$ remains unchanged. We just need to restore the $$$a$$$ values to be used before the calculation.

I use a priority queue to maintain $$$a$$$. Initially, inserting elements takes $$$n\log n$$$ time. The number of calculation rounds is $$$O(\log\max(A))$$$. In each round, we only insert and delete $$$O(1)$$$ numbers in the priority queue. The time complexity of the operations is $$$O(\log\max(A)\log n)$$$.

Therefore, the total time complexity is $$$O(n\log n+\log\max(A)\log n)$$$. (There should only be a constant-level difference in the implementation.)

I tried to prove some conclusions of problem B. (maybe) helps when reading the editorial (?)

Keyword: first consider how to handle $$$n=2$$$; reduce the size of the original problem.

First consider how to handle $$$n=2$$$: Let the answer be $$$F(a,b)$$$. When $$$a=b$$$, $$$F(a,a)=a$$$; when $$$a \lt b$$$, we can write $$$b=qa+r$$$ using division. We move once with distance $$$b$$$, then we can move $$$a$$$ a total of $$$q$$$ times, reaching position $$$r$$$. If $$$r=0$$$, the answer is $$$b$$$; if $$$r\neq 0$$$, we can convert to a subproblem $$$F(r,a)$$$. But note that when we implement $$$F(r,a)$$$, the actual maximum right endpoint needs to move right by $$$qa$$$, because the step length $$$r$$$ is obtained by first moving right by $$$b$$$ and then moving left by $$$qa$$$.

Arranging this, we get:

We record $$$r$$$ and $$$q$$$ during the whole process. Let $$$r_{-1}=b,r_0=a$$$. For $$$i\ge 1$$$ we obviously have:

Suppose $$$F$$$ recurses $$$m$$$ times (including the final return to $$$0$$$), obviously $$$r_m=0,r_{m-1}=g=\gcd(a,b)$$$.

We record the summation process of $$$F$$$:

The latter has many repetitions. After cancellation we can easily derive the formula for the answer:

Warm up complete. At the same time we obtain an important conclusion: the answer does not exceed $$$a_1+a_2-\gcd(a_1,a_2)$$$ ($$$a$$$ is sorted). In fact we can view it as the answer cannot be greater than or equal to $$$a_1+a_2$$$, which also explains why the problem does not require taking modulo. It is easy to see the above process resembles the Euclidean algorithm; try to derive it to the full solution.

Because the Euclidean algorithm requires recursion, let’s try to reduce the size of the original problem. Let $$$f(a_1,a_2,\cdots,a_n)$$$ be the answer for array $$$a$$$. Give the conclusion first: $$$f(a_1,a_2,\cdots,a_n)=a_1+f(a_1,a_2-a_1,\cdots,a_n-a_1)$$$. Next we try to prove it.

First prove $$$f(a_1,a_2,\cdots,a_n)\ge a_1+f(a_1,a_2-a_1,\cdots,a_n-a_1)$$$, i.e. given a construction of the original problem, derive a construction of the new problem.

We can merge multiple moves in the same direction into a set $$$S$$$, since the answer cannot be greater than or equal to $$$a_1+a_2$$$, so obviously $$$S={a_1,a_2,\cdots,a_n,2a_1,3a_1,4a_1,\cdots}$$$.

Now we choose a value from $$$S$$$ and move that much, and we cannot move in the same direction twice in a row. Because we cannot move in the same direction twice in a row, the moves must be: R L R L R L … R L R L(more clearly: R | L R | L … R | L R | L). It is easy to see that after each R operation, our position is at least $$$a_1$$$.

For the first “R”, suppose it is $$$+a_x$$$, express it in the new problem as $$$+(a_x-a_1)$$$; for the last “L”, suppose it is $$$-a_y$$$, express it in the subproblem as $$$-(a_y-a_1)$$$. Obviously the subproblem’s answer decreases by $$$a_1$$$, so we add it back. But we find that during the middle “R L” operations, after executing “L” in the original problem, the position may be less than $$$a_1$$$, which corresponds to $$$ \lt 0$$$ in the new problem, violating the second rule. Such a middle “R L” operation is written as $$$-a_x +a_y$$$, we can view it as $$$-(a_x-a_1)+(a_y-a_1)$$$. Because in the original problem all positions are $$$\ge 0$$$, after this simplification it is valid.

Then note that we still keep $$$a_1$$$ in the new problem, because the original problem may contain operations of several $$$a_1$$$, so we must keep it in the new problem. But don’t worry about violating the third rule, because the original problem did not violate the third rule, meaning $$$a_1$$$ was used in only one direction, so the new problem will not violate it.

Next prove $$$f(a_1,a_2,\cdots,a_n)\le a_1+f(a_1,a_2-a_1,\cdots,a_n-a_1)$$$, i.e. given a construction of the new problem, derive a construction of the original problem. From the above analysis, similarly we can get that the moves must be “R | L R | L … R | L R | L”, add $$$a_1$$$ to the leftmost “L”, also add $$$a_1$$$ to the rightmost “L” operation, and also add $$$a_1$$$ in the middle "L R", we can likewise reconstruct the original problem without violating the conditions. QED.

In summary, according to the editorial, using the Euclidean algorithm we can achieve $$$O(n\log A)$$$, or use data structures for an even better result.