Link to the problem: click here

Summary. Given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. In one operation, we can move one unit from $$$a_i$$$ to an adjacent position. We need to find the minimum number of operations such that $$$a_i \geq b_i$$$ for all $$$i$$$. It is guaranteed that a solution always exists.

Constraints. $$$n \leq 5\cdot 10^5; a_i, b_i \leq 10^6$$$.

I have already come up an approach for the subtasks with $$$\sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i$$$, when the target become to make $$$a_i = b_i$$$ for all $$$i$$$.

Let $$$pref_i = \sum_{i = 1}^n (a_i - b_i)$$$. If $$$pref_i \gt 0$$$, it means that the left side has $$$pref_i$$$ extra units, so we have to move them to the right side. Otherwise, the left side is missing of units, so we have to move $$$-pref_i$$$ units from the right side to the left side. In both cases, exactly $$$|pref_i|$$$ units will cross the gap between positions $$$i$$$ and $$$i + 1$$$. This implies that the answer will be $$$\sum_{i = 1}^n |pref_i|$$$.

However, I am stuck on how to generalize this to the full problem and also could not understand the accepted submissions. Any hints or explanations would be appreciated. Thanks!

During Codeforces Round 1099 (Div. 2),, I noticed that Problem E appears to be very similar to an old problem from the Vietnamese Olympiad in Informatics 2021 (VOI 2021).

The statement of Problem E can be summarized as follows:

Given a tree with $$$n$$$ vertices, count the number of triples $$$(a, b, c)$$$ such that $$$a \lt b \lt c$$$ and the number of vertices in the Steiner tree connecting $$$a$$$, $$$b$$$, and $$$c$$$ is exactly $$$d$$$.

Note. Here, the Steiner tree of a set of vertices in a tree simply means the smallest connected subgraph containing all chosen vertices.

Constraints. $$$3 \leq d \leq n \leq 2000$$$.

However, in VOI 2021, Problem 2 had an almost identical idea. The original Vietnamese statement can be found here. Its statement can be summarized as follows:

Given a tree with $$$n$$$ vertices, count the number of ways to choose $$$k$$$ vertices such that the number of edges in the Steiner tree connecting these $$$k$$$ vertices lies in the interval $$$[L, R]$$$.

Constraints. $$$1 \leq n \leq 1000; k \leq 4$$$.

It is not hard to see that the VOI 2021 problem is a more general version of the Codeforces problem. In particular, when $$$k = 3$$$, the two problems become very close. The main differences are that Codeforces counts vertices instead of edges and asks for the size to be exactly $$$d$$$, while the VOI problem asks for the number of edges to lie in an interval $$$[L, R]$$$.

This similarity is quite concerning, especially because Problem E had a relatively high score in the contest, and the intended idea involving knapsack on tree is not an easy one. Contestants who had already seen or solved the VOI problem could have had a noticeable advantage. Of course, this might still be an unintentional coincidence. However, the overlap in the core idea seems strong enough that I think it is worth pointing out and discussing.

I hope the coordinators can take a closer look at this case. Thanks to ChatGPT for fixing my bad English.