Skip to content

Convex Hull Trick (Slope Optimization)

Introductory example

[HNOI2008] Toy Packing

There are \(n\) toys in a row, and the \(i\)-th toy has value \(c_i\). Split the toys into several segments. A segment \([l,r]\) costs \((r-l+\sum_{i=l}^r c_i-L)^2\), where \(L\) is a constant. Find the minimum total cost of a split.

\(1\le n\le 5\times 10^4, 1\le L, c_i\le 10^7\).

Naive DP solution

Let \(f_i\) be the minimum cost of splitting the first \(i\) items into segments.

The recurrence is \(f_i=\min_{j<i}\{f_j+(i-(j+1)+pre_i-pre_j-L)^2\}=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\).

Here \(pre_i\) is the sum of the first \(i\) values, that is, \(\sum_{j=1}^i c_j\).

This takes \(O(n^2)\) time, which is too slow for this problem.

Optimization

We first simplify the recurrence. Let \(s_i=pre_i+i\) and \(L'=L+1\); then \(f_i=\min_{j<i}\{f_j+(s_i-s_j-L')^2\}\).

Moving everything that does not depend on \(j\) out of the minimum, we get

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

Recall the slope-intercept form of a linear function, \(y=kx+b\), which rearranges to \(b=y-kx\). We put what depends on \(j\) into \(y\), what depends on both \(i\) and \(j\) into \(kx\), and the quantity to minimize (which depends on \(i\)) into \(b\), the intercept. Concretely, let

\[ \begin{aligned} x_j&=s_j\\ y_j&=f_j+s_j^2\\ k_i&=-2(L'-s_i)\\ b_i&=f_i-(s_i-L')^2\\ \end{aligned} \]

The recurrence becomes \(b_i = \min_{j<i}\{ y_j-k_ix_j \}\). Treat each \((x_j,y_j)\) as a point in the plane. Then \(k_i\) is the slope of a line, and \(b_i\) is the intercept of the line with slope \(k_i\) through \((x_j,y_j)\). The problem is now to choose \(j\) (\(1\le j<i\)) so that this intercept is as small as possible.

slope_optimization

As the figure shows, we slide the line with slope \(k_i\) upward from below until some point \((x_p,y_p)\) lies on it. At that moment \(b_i=y_p-k_ix_p\), and \(b_i\) is at its minimum. Once \(f_i\) is computed, we add the point \((x_i,y_i)\) to the point set as a new decision for the DP. How should we maintain this set?

Any point that can minimize \(b_i\) lies on the lower hull. So when looking for \(p\) we do not need to enumerate all \(i-1\) points: the points on the convex hull are enough. In this problem \(k_i\) also increases with \(i\), so we can maintain the convex hull with a monotonic queue.

Concretely, let \(K(a,b)\) be the slope of the line through \((x_a,y_a)\) and \((x_b,y_b)\). The queue \(q_l,q_{l+1},\ldots,q_r\) holds the points of the lower hull. In other words, \(K(q_{i-1},q_i) < K(q_i,q_{i+1})\) holds for every \(l<i<r\) at all times.

To compute the minimum of \(b_i\) we maintain a pointer \(e\). We need the \(e\) with \(K(q_{e-1},q_e)\le k_i< K(q_e,q_{e+1})\) (the cases \(e=l\) and \(e=r\) need special handling). Then \(p=q_e\), that is, \(q_e\) is the optimal decision point for \(i\). Since \(k_i\) is increasing, the number of times \(e\) moves is amortized \(O(1)\).

To insert a point \((x_i,y_i)\), check whether \(K(q_{r-1},q_r)<K(q_r,i)\). While the inequality fails, pop \(q_r\). Then append \(i\) to the back of \(q\).

This brings the DP down to \(O(n)\).

To summarize, the algorithm for this convex hull trick template problem is:

  1. Push the initial state into the queue.
  2. For each \(i\), take a line \(f(i)\) that depends on \(i\), find where it touches the maintained convex hull to get the optimal decision, and update \(dp_i\).
  3. Add the state \(dp_i\). If a state (that is, a point on the convex hull) is no longer on the convex hull once \(dp_i\) is added, remove it before adding \(dp_i\).

Next we turn to more advanced uses of the convex hull trick: combining it with binary search, divide and conquer, or data structures to handle DP recurrences that are less well behaved (that lack some of the monotonicity properties).

Optimizing DP with binary search, CDQ, or a balanced tree

To find the optimal decision for \(i\), we take a line \(f(i)\) that depends on \(i\) and find where it touches the convex hull we maintain. The point it touches is the optimal decision.

In the example above, the slope of the line changes monotonically with \(i\), but in some problems it does not. We then have to keep every point of the convex hull and query the hull with the current line each time. Binary search does this, because the slopes between adjacent points of the convex hull are monotonic.

Toy Packing, modified

There are \(n\) toys in a row, and the \(i\)-th toy has value \(c_i\). Split the toys into several segments. A segment \([l,r]\) costs \((r-l+\sum_{i=l}^r c_i-L)^2\), where \(L\) is a constant. Find the minimum total cost of a split.

\(1\le n\le 5\times 10^4,1\le L\le 10^7,-10^7\le c_i\le 10^7\).

The only difference from Toy Packing is that a toy's value may be negative. As before, let \(f_i\) be the minimum cost of splitting the first \(i\) items into segments.

The recurrence is \(f_i=\min_{j<i}\{f_j+(pre_i-pre_j+i-j-1-L)^2\}\).

Here \(pre_i = \sum_{j=1}^i c_j\).

Transforming the recurrence in the same way gives

\[ f_i - (s_i-L')^2=\min_{j<i}\{f_j+s_j^2 + 2s_j(L'-s_i) \} \]

But two conditions no longer hold:

  1. the slopes of the lines are no longer monotonic;
  2. the x-coordinates of the decision points we add are no longer monotonic.

We still want to maintain the hull.

To find the optimal decision point, that is, the point where the line touches the hull, we no longer take the front of a monotonic queue: we binary search on the hull. The search finds the hull edge whose slope is closest to the slope of the line, and that gives the optimal decision.

There are two ways to handle adding a decision point, that is, adding a point to the hull.

The first is to keep the hull in a balanced tree. The binary search for the decision point becomes a binary search on the balanced tree, and inserting a decision point becomes inserting a node into the tree and deleting the points that this pushes off the hull. The idea is simple, but the implementation is tedious.

Below we describe a solution based on CDQ divide and conquer.

Let \(\text{CDQ}(l,r)\) stand for computing \(f_i\) for \(i\in [l,r]\). Consider \(\text{CDQ}(1,n)\):

  • First call \(\text{CDQ}(1,mid)\) to compute \(f_i\) for \(i\in[1,mid]\). Then build the hull of the decision points in the range \([1,mid]\) and use it to update \(f_i\) for \(i\in [mid+1,n]\). The set of decision points is now fixed: we are no longer adding decision points while computing DP values, as we did before. So we can sort the \(f_i\) with \(i \in [mid+1,n]\) by the slope \(k_i\) of their lines and then compute the DP values with a monotonic queue. Binary searching on the static hull works too.

  • Every point in \([mid+1,n]\) whose optimal decision lies in the range \([1,mid]\) gets its optimal answer in this step. Once the step is done, the points in \([1,mid]\) have nothing more to contribute: whether they are still in the hull no longer affects later updates. So we discard the decision points of this range and call \(\text{CDQ}(mid+1,n)\) to solve what remains of the right half.

This takes \(O(n\log^2 n)\) time.

Comparing Toy Packing with its modified version, we can draw two conclusions:

  • Binary search, CDQ divide and conquer, balanced trees and the like speed up the evaluation of a DP recurrence and lower the complexity to some extent, but they cannot change the recurrence itself.
  • The properties of a DP recurrence depend on the characteristics of the data, but the recurrence itself depends on the mathematical model in the problem.

Summary

The convex hull trick has to be applied flexibly. Its essence is to turn an optimization problem into finding the minimum or maximum intercept over a convex hull in the plane. A recurrence with less convenient properties sometimes needs a data structure as well; what to use depends on the problem at hand.

Practice problems