Archeologists#12835

Archeologists (Editorial)

Author: Lucian Bicsi

Solved by:

First to solve: KhNU_OtVinta

This problem can be approached in many ways. Quite possibly the shortest description would be "just slope trick on prefix sums"; however, we will try to describe some various approaches.

Let's consider the following minimum cost flow problem, with vertices \{ 0, 1, 2, \ldots, n \} \cup \{ S, T \}, and the following arcs:

  • i \rightarrow i + 1 with capacity and cost , for 0 \leq i < n;

  • S \rightarrow i with capacity and cost p_1 + ... + p_i, for 0 \leq i \leq n;

  • i \rightarrow T with capacity and cost -(p_1 + ... + p_i), for 0 \leq i \leq n.

Naturally, any valid flow corresponds to a valid solution, and the minimum cost flow corresponds with the answer (up to negation). One may solve the problem now by adapting the successive shortest paths algorithm on the particular network, by using, for example, a segment tree. The maximum flow is guaranteed to be exactly n+1, due to the specifics of the network.

More easily, a minimum cost flow can be obtained by greedily going from right to left, matching the current position with some position to the right with maximum prefix sum, and then add the two residual edges that the current vertex exposed in the network. It can be shown that such a procedure never produces any negative cost cycles, therefore the flow is of minimum cost. Such solution can be easily implemented with a priority queue.

Another possible solution to the problem would be to start with the quadratic dynamic programming approach dp(i, j) = maximum profit that you can obtain such that the depth at the -th level is , and optimize it by noticing that the function f_i(j) = dp(i, j) is concave for all possible . This fact can be proven (among other ways) by noticing that dp(i, j) can also be expressed in terms of the minimum cost flow problem above, where is the flow going along edge (i \rightarrow i+1).

Then, transitioning from f_i(\cdot) to f_{i+1}(\cdot) can be optimized using segment trees. This solution is, however, considerably more complex than using priority queues to simulate the minimum cost flow problem.

Bonus: An experienced coder may notice the strange connection between the priority queue solution and the implementation for a technique popularly known as "slope trick". Indeed, the two problems are tightly connected to each other (in a very non-trivial way).

One may see such a connection by formulating the current problem as a linear program:

[ max_x _i=1^n p_i x_i   s.t. { : x_i - x_i-1 1  x_i+1-x_i 1  x_0 0  x 0 : } ]

One may then dualize the linear program, and, after some substitutions, the exact linear program for the "slope trick" problem would show up:

[ min_y,d _i=1^n+1 d_i   s.t. { : y_i - s_i d_i  s_i - y_i d_i  y_i - y_i+1 0 : } ] where we denode s_i = p_1 + p_2 + \ldots + p_{i-1}.

We leave the proof as an exercise for the (experienced) readers.