Author: Akihito Yoneyama

Subtask 1

We can solve this subtask by calculating all possible ways to remove the weights. The time complexity of this algorithm is ~\mathcal{O}(2^N \operatorname{poly}(N))~.

Subtask 2

We use the Two Pointers Technique. We increase the lower bound of the position of the barycenter. We shall see how the upper bound increases. Let ~(L, R)~ be the state where the weights are remaining in the interval ~[L, R]~. We need to check whether the vertex ~(1, n)~ and the vertex ~(i, i)~ are connected in the grid graph. There are ~\mathcal{O}(N^2)~ possibilities for the upper bounds and the lower bounds. The connectedness of a graph can be checked in ~\mathcal{O}(N^2)~ time. The total time complexity is ~\mathcal{O}(N^4)~.

Subtask 3

In the algorithm for Subtask 2, we consider the change of path from the state ~(1, n)~ to each ~(i, i)~. When the lower bound increases by ~1~, if the vertex ~(L, R)~ of the previous lower bound is contained in the path, we delete it and add a new vertex ~(L+1, R+1)~ to the path. Simulating this process, we solve this subtask in ~\mathcal{O}(N^2 \log N)~ time.

Subtask 4

We can decrease the number of the candidates of paths. More precisely, we need only consider paths between the following two paths.

• A path which greedily deletes the leftmost weights while the barycenter does not become larger than the original barycenter.
• A path which greedily deletes the rightmost weights while the barycenter does not become smaller than the original barycenter.

Since there are only ~\mathcal{O}(N)~ vertices between them, by the same algorithm as Subtask 3, we can solve this subtask in ~\mathcal{O}(N \log N)~ time.