Solution

We assume that \(A_1, \dots, A_N\) are sorted in the increasing order. Let \(A' = (A'_1, \dots. A'_N)\) be the final sequence after arbitrary number of operations. Then, we can assume that for any \(1 \leq i \lt j \leq N\), \(A'_i \leq A'_j\).

Proof

Assume that there exists \((i, j)\) such that \(1 \leq i \lt j \leq N\) and \(A'_i \gt A'_j\). We can assume that \(A'_i = A'_j\) without increasing the number of different values but while decreasing the cost. Moreover, since \(A'_j \geq A_j \geq A_i\), it is always possible to increment \(A_i\) until it becomes \(A'_j\). Therefore, we can assume that there does not exist any \((i, j)\) such that \(A'_i \gt A'_j\).

Since the number of different values affect to the cost, let us split \(A'\) into the group of the same value. Since \(A'_1, \dots, A'_N\) is sorted in the increasing order, there exists a sequence \(P = (P_0, \dots, P_K), Q = (Q_1, \dots, Q_K)\) such that:

• \(0 = P_0 \lt P_1 \lt \dots \lt P_K = N\);
• \(Q_1 \lt \dots \lt Q_K\);
• if \(P_{k - 1} \lt i \leq P_k\), then \(A'_i = Q_i\).

Moreover, we can assume that \(Q_k = A_{P_k}\) in the optimal solution.

Proof

If \(Q_k \gt A_{P_k}\), then we can decrement \(Q_k\) by one without increasing the number of different values but while decreasing the cost. Moreover, for any \(P_{k - 1} \lt i \leq P_k\), \(Q_k - 1 \geq A_i\), so it is always possible to increment \(A_i\) until it becomes \(Q_k - 1\). By repeating “decrementing \(Q_k\) if \(Q_k \gt A_{P_k}\),” we can assume that for any \(k\), \(Q_k = A_{P_k}\).

The number of different values in \(A'\) is \(K\). Denoting by \(S\) the total cost to pay, we have

\(\begin{aligned} \displaystyle S &= \sum_{k = 1}^K \left(X + \sum_{i = P_{k - 1} + 1}^{P_k} (Q_k - A_i)C_i \right) \\ &= \sum_{k = 1}^K \left(X + \sum_{i = P_{k - 1} + 1}^{P_k} (A_{P_k} - A_i)C_i \right) \\ &= \sum_{k = 1}^K \left(X + A_{P_k} \sum_{i = P_{k - 1} + 1}^{P_k} C_i \right) - \sum_{i = 1}^N A_i C_i, \end{aligned}\)

so, defining \(R_i = \sum_{j \leq i} C_j\) for \(0 \leq i \leq N\), \(\displaystyle S = \sum_{k = 1}^K (X + (R_{P_k} - R_{P_{k - 1}})A_{P_k} ) - \sum_{i = 1}^N A_iC_i\).

Therefore, the minimum value of \(S\) is the shortest distance on the graph defined below from Vertex \(0\) to Vertex \(N\), subtracted by \(\displaystyle \sum_{i = 1}^N A_iC_i\):

• There are \(N+1\) vertices, numbered \(0, 1, \dots, N\).
• For any \(0 \leq l \lt r \leq N\), there exists an edge from Vertex \(l\) to Vertex \(r\) with cost \(X + (R_r - R_l)A_r\).

Let \(D_u\) be the shortest distance from Vertex \(0\) to Vertex \(u\). Let us compute \(D_u\) in the increasing order of \(u\). First and obviously, \(D_0 = 0\). When \(D_i\) for every \(0 \leq i \lt r\) is known, \(D_r\) can be computed as follows.

\(\begin{aligned} D_r &= \min_{0 \leq l \lt r} (D_l + X + (R_r - R_l)A_r) \\ &= \min_{0 \leq l \lt r} (-R_lA_r + D_l) + R_rA_r + X \end{aligned}\)

Notice \(\min_{0 \leq l \lt r} (-R_lA_r + D_l)\); the \(R_l\) and \(D_l\) part is independent of \(r\). We can regard this as a linear (or constant) function \(R_lx + D_l\) where \(x = A_r\), so we can solve this problem with the following process:

• We manage the set \(F\) of linear (or constant) functions. First, let \(F \leftarrow \empty\) and \(D_0 \leftarrow 0\).
• For each \(i = 1, 2, \dots, N\), do the following process.
  • First, let \(\displaystyle F \leftarrow F \cup \{-R_{i - 1}x + D_{i - 1} \}\).
  • Then, let \(\displaystyle D_i \leftarrow \min_{f(x) \in S} f(A_i)\).

\(-R_i\) is (strictly) monotonically decreasing over \(i\), and \(A_i\) is (weakly) monotonically increasing over \(i\). Therefore, adding a function to \(F\) and obtaining the minimum value can be done by the technique called Convex Hull Trick in an amortized \(O(1)\) time each.

In summary, the problem has been solved in a total of \(O(N \log N)\) time, where sorting \(A_i\) is the bottleneck.

Sample code (C++)

Convex Hull Trick

As described in the “Solution” part, we want to do the following two operation fast for a set of linear (or constant) function of \(x\):

• add \(ax + b\) to \(F\);
• find \(\displaystyle \min_{f(x) \in F} f(p)\).

Each element of \(F\) correspond to a tilted line on an \(xy\)-plane. Here is an example.

For a line \(l : y = ax + b\) and another line \(m : y = cx + d\) such that \(a > c\), let \(\displaystyle g(l, m) = \frac{d - b}{a - c}\); then \(ax + b \leq cx +d\) if \(x \leq g(l, m)\) and \(ax + b \gt cx +d\) if \(x \gt g(l, m)\).

Among each line corresponding to each element of \(F\), let \(l_i : y = a_i x + b_i\) be the line with the \(i\)-th largest slope. When \(g(l_{i - 1}, l_i) \gt g(l_{i}, l_{i + 1})\), then it is impossible that \(a_i x + b_i\) gives the minimum value. Therefore, we can assume that \(g(l_i, l_{i + 1})\) is monotonically increasing.

For some three lines lines \(l : y = ax + b, m : y = cx + d, n : ex + f\) such that \(a \gt c \gt e\), suppose that \(g(l, m) \leq g(m, n)\). Then

\(\begin{aligned} \frac{d - b}{a - c} &\leq \frac{f - d}{c - e} \\ (c -e)(d - b) &\leq (a - c)(f - d) \\ (c - e)(d - b) + (a - c)(d - b) &\leq (a - c)(f - d) + (a - c)(d -b) \\ (a - e)(d - b) &\leq (a - c)(f - b) \\ \frac{d - b}{a - c} & \leq \frac{f - b}{a - e}, \end{aligned}\)

so \(g(l, m) \leq g(l, n)\). Therefore, if \(g(l_i, l_{i + 1})\) is monotonically increasing and \(a_i p + b_i \leq a_{i + 1}p + b_{i + 1}\), then for any \(j \gt i\), it holds that \(a_ip + b_i \leq a_jp + b_j\).

We consider how to add \(l : y = ax + b\) to \(F\). In this problem, the slope of the added lines are strictly monotonically decreasing, so we can assume that \(a_n \gt a\). If \(g(l_{n - 1}, l_n) \gt g(l_n, l)\), then it is never possible that \(a_nx + b_n\), so we may remove \(l_n\) from \(F\). After repeating removing \(l_n\) from \(F\) while \(g(l_{n - 1}, l_n) \gt g(l_n, l)\) and then adding \(l\) to \(F\), we can keep the condition that \(g(l_i, l_{i + 1})\) is monotonically increasing.

We now consider how to find the minimum value at \(x = p\). Since \(a_1 \gt a_2\), if \(a_1p + b_1 \gt a_2p + b_2\) then \(a_1p' + b_1 \gt a_2p' + b_2\) for any \(p' \geq p\). Since \(p\) is weakly monotonically increasing as the queries are consumed, if \(a_1p + b_1 \gt a_2p + b_2\) then removing \(l_1\) from \(F\) does not change the answer. Therefore, after repeating removing \(l_1\) from \(F\) while \(a_1p + b_1 \gt a_2p + b_2\), \(a_1p + b_1\) is the desired answer.

By managing the elements of \(F\) with a data structure like double-ended queue, adding lines and obtaining the minimum value can be done in an amortized \(O(1)\) time each.

Convex Hull Trick (Another solution)

In this problem, our purpose was to find \(\min_{0 \leq l \lt r} (-R_lA_r + D_l)\) for each \(r\) in order. This corresponds to the queries, on an initially empty set of points to which points \((-R_l, D_l)\) are added, of finding the point that minimizes \(A_r x + y\) at arbitrary timing. Generally, consider the following problem.

Manage an initially empty set \(S\) of points while responding to the following queries.

• Add a given point \((x, y)\) to \(S\). It is guaranteed that points are given in the (strictly) increasing order.
• Given is a parameter \(t\). Find the minimum value \(tx + y\) for the points in the set.

Notice that we are only interested in those points belonging to the lower convex hull, so let us manage the points forming the lower convex hull as \(P_1, ..., P_k\) in the increasing order of \(x\) coordinates.

We process each point-adding query as follows. Let \(Q\) be the given point. By the constraint of the query, this point is in the left of any points in \(S\). Then, we may update the lower convex hull as follows.

Take three points: $P_{k-1}$, $P_k$, and $Q$.  If these are concave, then remove $P_k$ from the back (decrementing $k$ by one) and repeat the same operation.
When $P_{k-1}$, $P_k$, and $Q$ are convex, terminate the operation and append $Q$ to the back.

The query of finding the minimum value of \(tx + y\) can be generally done by trinary search. This time, parameter \(t\) are always given in the increasing order, so it never happens that the point which minimizes \(tx + y\) does not move left. Therefore, we may record which point optimizes \(tx + y\) and update it just as sliding windows.