Slope Trick Optimization

Introduction

For a class of two-dimensional DP problems, if the cost function \(f(i,x)\) is a convex function of \(x\) for each fixed \(i\), then treating the entire function \(f(i,\cdot)\) as the state at \(i\) and maintaining its difference (or slope)

\[ \Delta f(i,x) = f(i,x+1)-f(i,x) \]

instead of the function itself can often optimize the transition. This idea of optimizing DP is called Slope Trick.

「Slope」

Since the functions involved in most problems only take values at integer points, calling it difference or slope makes no essential difference. This article uniformly refers to it as slope following the term Slope Trick.

In specific problems, the way slopes are maintained may vary. If the range of slopes is narrow, maintaining the points where the slope changes (i.e., breakpoints) is more convenient; if the domain of the function is narrow, maintaining the slope sequence itself may be more convenient. More complex situations may require maintaining both the slope value and the length of each slope segment. Regardless of the specific maintenance method, the essence of such problems is to simplify transitions by leveraging the fact that the slope sequence changes little during state transitions. Therefore, they can all be called Slope Trick.

Convex Functions

Before discussing specific problems, it is necessary to first understand the basic properties of convex functions and how their slopes change under various transformations.

Convex Functions on the Real Line

The more general definition of convex functions is given on \(\mathbf R\).

Convex Functions on \(\mathbf R\)

A function \(f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}\) is called a convex function if for all \(x,y\in\mathbf R\) and \(\alpha\in(0,1)\),

\[ f(\alpha x+(1-\alpha)y) \le \alpha f(x)+(1-\alpha)f(y), \]

where the arithmetic rules for \(\pm\infty\) are defined as \(\pm\infty\) multiplied by any positive real number or added to any real number equals itself, and for any real number \(x\in\mathbf R\), \(-\infty<x<+\infty\).

Of course, if the inequality sign is replaced with \(\ge\), it is correspondingly called a concave function¹. Since for a concave function \(f\), \(-f\) is always convex, this section only considers convex functions.

This Article Only Considers Proper Convex Functions

To avoid discussing the value of \(\infty-\infty\) and additional complex analysis, when discussing concepts related to convex functions, this article always assumes the function does not take \(-\infty\) and is not always \(+\infty\). Such convex functions are called proper convex functions. This is sufficient for understanding the content covered in algorithmic competitions.

Of course, the function \(f\) often is not defined for all real numbers. If the domain of \(f\) is only a subset of \(\mathbf R\), it can be extended to a function on \(\mathbf R\):

\[ \tilde f(x) = \begin{cases} f(x), & x\in\operatorname{dom}f,\\ +\infty,& x\notin\operatorname{dom}f.\end{cases} \]

Then, \(f\) is said to be convex if and only if the corresponding \(\tilde f\) satisfies the above definition of convex functions. Therefore, unless otherwise specified, the domain of convex functions mentioned in this article is the real set \(\mathbf R\). Clearly, a convex function \(f\) can only take finite values on an interval (i.e., a convex subset of \(\mathbf R\)).

Simple Examples

Common examples of convex functions include:

Constant functions: \(f(x)=c\), where \(c\in\mathbf R\);
Linear functions: \(f(x)=kx+b\), where \(k,b\in\mathbf R\) and \(k\neq 0\);
Absolute value functions: \(f(x)=|x-a|\), where \(a\in\mathbf R\);
Any convex function restricted to some interval, e.g., \(0_{[a,b]}(x)\) (also called the indicator function of \([a,b]\) in convex analysis).

Of course, more complex convex functions can be constructed by combining convexity-preserving transformations mentioned below.

Convex Functions on Discrete Point Sets

In algorithmic competitions, many functions are only defined at some integer points. They are generally not convex functions (as defined above) because their domain is no longer a convex set. To handle this situation, the convexity of functions on discrete point sets needs to be defined separately. Simply put, the function is first linearly interpolated to extend its domain to intervals, and then its convexity is judged.

Convex Functions on Discrete Point Sets

Let \(S\subset\mathbf R\) be a discrete point set, i.e., for any closed interval \([a,b]\), \(S\cap[a,b]\) is a finite set. For a function \(f:S\rightarrow\mathbf R\cup\{\pm\infty\}\), define the function \(\tilde f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}\) such that:

When \(x\in S\), \(\tilde f(x)=f(x)\),
When \(x\in(\inf S,\sup S)\setminus S\), let \(s_-=\max\{s\in S:s\le x\}\), \(s_+=\min\{s\in S:s\ge x\}\), then

\[ \tilde f(x) = \dfrac{s_+-x}{s_+-s_-}f(s_-)+\dfrac{x-s_-}{s_+-s_-}f(s_+), \]
When \(x\notin[\inf S,\sup S]\), \(\tilde f(x)=+\infty\).

Then, if \(\tilde f(x)\) is a convex function on \(\mathbf R\), \(f(x)\) is called a convex function on \(S\).

Since convex functions on \(\mathbf R\) are more convenient to handle, unless otherwise specified, convex functions mentioned in this article refer to convex functions on \(\mathbf R\). If a function in this article is only given values at some integer points, its values at other real numbers should be determined by \(\tilde f\) in the definition, which is equivalent to directly discussing the corresponding piecewise linear function \(\tilde f\).

Convex functions on the integer set \(\mathbf Z\) have a more intuitive equivalent definition:

Equivalent Definition of Convex Functions on \(\mathbf Z\)

A function \(f:\mathbf Z\rightarrow\mathbf R\cup\{\pm\infty\}\) is convex if and only if

\[ f(x)-f(x-1)\le f(x+1)-f(x) \]

holds for all \(x\in\mathbf Z\).

Proof

This proposition is a simple corollary of the slope characterization of convex functions.

If \(f\) is convex on \(\mathbf Z\), then by weak increase of slopes,

\[ \Delta f(x-1,x)\le \Delta f(x-1,x+1) \le\Delta f(x,x+1). \]

This is exactly the above condition.

Conversely, if the above condition holds, then for any \(x_1<x_2\),

\[ \Delta f(x_1,x_2) = \dfrac{1}{x_2-x_1}\sum_{i=x_1}^{x_2-1}\left(f(i)-f(i-1)\right). \]

This is the arithmetic mean of all differences satisfying \(x_1\le i<x_2\). If \(x_2\) increases by one, it is equivalent to inserting a larger difference; if \(x_1\) increases by one, it is equivalent to removing the smallest difference. Both operations increase the mean. This shows the slope \(\Delta f(x_1,x_2)\) weakly increases, i.e., \(f\) is convex on \(\mathbf Z\).

That is, as long as the slope (difference) is monotonically non-decreasing, this sequence can be regarded as a convex function on \(\mathbf Z\).

Two Characterizations of Convex Functions

In fact, the way of characterizing convex functions by slopes can also be generalized to the general case.

Slope Characterization of Convex Functions

Let \(S\) be \(\mathbf R\) or a discrete subset of it. Then a function \(f:S\rightarrow\mathbf R\cup\{\pm\infty\}\) is convex if and only if the slope

\[ \Delta f(x_1,x_2) = \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \]

is a weakly increasing function of both \(x_1\) and \(x_2\) for any \(x_1,x_2\in S\) with \(x_1<x_2\).

Proof

For a function \(f(x)\) on \(\mathbf R\) and \(x_1<x_2\), for \(\alpha\in(0,1)\), let \(x_3=\alpha x_1+(1-\alpha)x_2\), then

\[ \Delta f(x_1,x_3) \le \Delta f(x_1,x_2) \le \Delta f(x_3,x_2) \]

is equivalent to

\[ \dfrac{f(x_3)-f(x_1)}{1-\alpha} \le f(x_2)-f(x_1) \le \dfrac{f(x_2)-f(x_3)}{\alpha}. \]

Both inequalities are equivalent to \(f(x_3)\le\alpha f(x_1)+(1-\alpha)f(x_2)\), i.e., the convexity of \(f(x)\).

For a function \(f(x)\) on a discrete subset \(S\) of \(\mathbf R\), the necessity of the weak increase condition can be derived from the convexity of \(\tilde f(x)\). Now we prove its sufficiency, for which it suffices to show that \(\Delta\tilde f(x_1,x_2)\) is also weakly increasing. Let \(S=\{s_i\}\) with \(s_i\) strictly increasing in \(i\), and let \(s_{i_1}\le x_1\le s_{i_1+1}\) and \(s_{i_2}\le x_2\le s_{i_2+1}\), naturally \(i_1\le i_2\). Let \(\Delta_i=\Delta f(s_i,s_{i+1})\). Then it can be shown that \(\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}\).

There are two cases. If \(i_1=i_2\), then \(\Delta_{i_1}=\Delta\tilde f(x_1,x_2)=\Delta_{i_2}\), and the inequality obviously holds. Otherwise,

\[ \Delta\tilde f(x_1,x_2) = \dfrac{1}{x_2-x_1}\left((s_{i_1+1}-x_1)\Delta_{i_1}+(x_2-s_{i_2})\Delta_{i_2}+\sum_{j=i_1+1}^{i_2-1}(s_{j+1}-s_j)\Delta_j\right). \]

By the increase of slopes on \(S\), \(\Delta_i\) increases with \(i\), so \(\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}\).

Using this result, for \(x_1<x_2\) and \(\alpha\in(0,1)\), let \(x_3=\alpha x_1+(1-\alpha)x_2\), and take \(i_3\) such that \(s_{i_3}\le x_3\le s_{i_3+1}\), then

\[ \Delta\tilde f(x_1,x_3) \le \Delta_{i_3} \le \Delta\tilde f(x_3,x_2). \]

Substituting the expression for \(x_3\) yields the convexity of \(\tilde f(x)\).

Monotonically non-decreasing slopes can be regarded as an equivalent definition of convex functions. Precisely because convex functions have monotonic slopes, when maintaining slopes, data structures such as heaps (priority queues) or balanced trees are usually needed.

This article will also use another equivalent characterization of convex functions. For a function \(f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}\), consider the region above its graph in the plane, i.e.,

\[ \operatorname{epi} f = \{(x,y)\in\mathbf R^2 : y\ge f(x)\}. \]

This region is also called the epigraph of function \(f\). The convexity of a function is equivalent to the convexity of its epigraph:

Epigraph Characterization of Convex Functions

A function \(f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}\) is convex if and only if \(\operatorname{epi}f\) is a convex set in \(\mathbf R^2\).

Proof

If \(f\) is convex, then for \((x_1,y_1),(x_2,y_2)\in\operatorname{epi}f\) and any \(\alpha\in(0,1)\),

\[ \alpha y_1+(1-\alpha)y_2 \ge \alpha f(x_1)+(1-\alpha)f(x_2) \ge f(\alpha x_1+(1-\alpha) x_2). \]

So, \(\alpha(x_1,y_1)+(1-\alpha)(x_2,y_2)\in\operatorname{epi}f\).

Conversely, if \(\operatorname{epi}f\) is convex, then for any \(x_1<x_2\) and \(\alpha\in(0,1)\),

\[ \alpha(x_1,f(x_1))+(1-\alpha)(x_2,f(x_2)) \in \operatorname{epi}f. \]

This is equivalent to \(\alpha f(x_1)+(1-\alpha)f(x_2)\ge f\left(\alpha x_1+(1-\alpha)x_2\right)\), i.e., the convexity of \(f\).

Later we will see that using epigraphs, the infimal convolution of convex functions can be related to the Minkowski sum of convex sets.

Transformations of Convex Functions

Next, this article introduces some convexity-preserving transformations frequently encountered in Slope Trick.

Nonnegative Linear Combination

For convex functions \(f\) and \(g\) and nonnegative real numbers \(\alpha,\beta\ge0\), the function \(\alpha f+\beta g\) is also convex. Moreover,

\[ \Delta(\alpha f+\beta g) = \alpha\Delta f + \beta\Delta g. \]

Therefore, if the slopes of convex functions \(f\) and \(g\) are maintained, to obtain the slope of their nonnegative linear combination \(\alpha f+\beta g\), it suffices to compute piecewise.

In problems maintaining slopes, often one function has a simple form, and lazy tags can be used to reduce modification complexity. In problems maintaining breakpoints, to compute the slope breakpoints of \(f+g\), it suffices to merge the slope breakpoints of \(f\) and \(g\).

Infimal Convolution (Minkowski Sum)

Another common operation on convex functions is infimal convolution. For functions \(f\) and \(g\), the function

\[ h(x) = \inf_{y\in\mathbf R}f(y)+g(x-y) \]

is called the infimal convolution² of \(f\) and \(g\). If \(f\) and \(g\) are both convex, their infimal convolution is also convex.

Explanation of the Diagram

As shown, to find the infimal convolution \(h\) of \(f\) and \(g\), each point on the graph of \(f\) (red dashed line in the third diagram) can be regarded as the origin, and the graph of \(g\) (blue dashed line in the third diagram) is drawn in the corresponding coordinate system. As the coordinate origin moves along the graph of \(f\), the contour (i.e., lower convex hull) of the moving epigraph of \(g\) is the graph of \(h\). It can be seen that each slope segment of \(h\) is either a slope segment of \(f\) or of \(g\), just reordered by slope magnitude. In this process, the roles of \(f\) and \(g\) can be swapped, i.e., moving the graph of \(f\) along that of \(g\) yields the same result.

Geometrically, \(\operatorname{epi}h\) is the Minkowski sum of \(\operatorname{epi}f\) and \(\operatorname{epi}g\). If \(f\) and \(g\) are both piecewise linear functions, then \(h\) is also piecewise linear, and its slope segments can be seen as the result of merging (and reordering) the slope segments of \(f\) and \(g\).

Proof

Let \(f,g\) be convex functions, and \(h\) their infimal convolution. Let \(x_1<x_2\), and \(\alpha\in(0,1)\). By the definition of infimal convolution, for any \(\varepsilon>0\), there exist \(y_i,z_i\in\mathbf R\) such that \(y_i+z_i=x_i\) and

\[ h(x_i) + \varepsilon > f(y_i) + g(z_i). \]

Hence, combining the convexity of \(f,g\) and the definition of \(h\),

\[ \begin{aligned} \alpha h(x_1)+(1-\alpha)h(x_2) + \varepsilon &> \alpha f(y_1) + (1-\alpha) f(y_2) + \alpha g(z_1) + (1-\alpha) g(z_2)\\ &\ge f\left(\alpha y_1+(1-\alpha)y_2\right) + g\left(\alpha z_1+(1-\alpha)z_2\right)\\ &\ge h(\alpha x_1+(1-\alpha)x_2). \end{aligned} \]

Since \(\varepsilon>0\) is arbitrary,

\[ \alpha h(x_1)+(1-\alpha)h(x_2) \ge h(\alpha x_1+(1-\alpha)x_2). \]

This yields the convexity of \(h\).

As for the geometric intuition, strictly speaking, we can only prove:

\[ \operatorname{epi} f + \operatorname{epi} g\subseteq \operatorname{epi}h \subseteq \operatorname{cl}(\operatorname{epi} f + \operatorname{epi} g). \]

where \(\operatorname{cl}\) denotes closure.

For any \((x,y)\in\operatorname{epi} f + \operatorname{epi} g\), there exist \((x_1,y_1)\in\operatorname{epi} f\) and \((x_2,y_2)\in\operatorname{epi} g\) such that \(x=x_1+x_2\) and

\[ y = y_1+y_2 \ge f(x_1)+g(x_2) \ge h(x_1+x_2)=h(x). \]

Hence, \((x,y)\in\operatorname{epi}h\). This shows \(\operatorname{epi} f + \operatorname{epi} g\subseteq \operatorname{epi}h\).

Conversely, for any \((x,y)\in\operatorname{epi}h\), \(y\ge h(x)\). By the definition of \(h\), for any \(\varepsilon>0\), there exists \(x_1+x_2=x\) such that

\[ y + \varepsilon > f(x_1) + g(x_2). \]

Let \(y_1=f(x_1)\) and \(y_2=g(x_2)\), then \(y+\varepsilon>y_1+y_2\). This shows that for any \(\varepsilon>0\), \((x_1,y_1)+(x_2,y_2)\in\operatorname{epi} f + \operatorname{epi} g\) lies on the line segment between \((x,y)\) and \((x,y+\varepsilon)\). Taking \(\varepsilon\rightarrow 0\), we have \(\operatorname{epi}h \subseteq \operatorname{cl}(\operatorname{epi} f + \operatorname{epi} g)\).

Therefore, \(\operatorname{epi} f + \operatorname{epi} g = \operatorname{epi}h\) if and only if it is a closed convex set. A sufficient condition is that \(f\) and \(g\) are proper convex functions and lower semicontinuous. For algorithmic competition applications, this is sufficient; for example, piecewise linear functions always satisfy these conditions.

In practical problems, if one of \(f\) and \(g\) has few slope segments, the fewer segments can be directly inserted into the more segments; otherwise, methods like heuristic merging or mergeable heaps may be needed to reduce overall merging complexity, or specific problem-dependent approaches should be sought.

Maximum Operation

The maximum of two convex functions is still convex, but the minimum of two convex functions is not necessarily convex.

Many common minimum operations can be transformed into infimal convolution:

Examples

\(f(x)=\min_{y\in [x+a,x+b]}g(y)\) is still convex because it can be seen as infimal convolution:

\[ f(x) = \min_{y\in\mathbf R}g(y) + 0_{[-b,-a]}(x-y). \]
\(f(x)=\min\{g(x-a_i)+b_i\}\) is convex on \(\mathbf Z\) as long as \(g(x)\) is convex on \(\mathbf Z\), and the function \(h:a_i\mapsto b_i\) defined on the finite set \(\{a_i\}\subset\mathbf Z\) is also convex on that discrete set. This is because the extended function \(\tilde f(x)\) can be seen as infimal convolution:

\[ \tilde f(x) = \min_{y\in\mathbf R}\tilde h(y)+\tilde g(x-y). \]

Hence, the original function \(f(x)\) is also convex.

But not all minimum operations preserve convexity.

Counterexample

Let \(g(x)\) be convex. The function \(f(x)=\min\{g(x-1)+kx,g(x)\}\) is not necessarily convex.

In some special problems, although the DP transition equation can be written as the minimum of two convex functions and is difficult to transform into infimal convolution form, the cost function can still remain convex. In practice, reasonable slope transition methods for such problems are often found through tabulation and guessing.

After understanding convex functions and their common transformations, we can comprehend the method of Slope Trick for optimizing DP through specific problems. The examples in this article are roughly divided into two groups: maintaining breakpoints and maintaining slopes, to understand the common operations and implementation details of these two maintenance methods. However, as emphasized earlier, the maintenance method is not the essence of Slope Trick; the appropriate slope segment maintenance method should be chosen according to the specific problem needs.

Maintaining Breakpoints

Such problems typically appear when minimizing sums of absolute values. Because in such problems, the absolute value of the slope of the cost function is not large, maintaining breakpoints where the slope changes is more convenient.

Maintaining breakpoints means maintaining the points where the slope changes in a piecewise linear function. This is equivalent to maintaining only the endpoint information for each slope segment \([l_i,r_i]\) with slope \(k_i\), while the slope itself does not need separate maintenance; therefore, in such problems, the slope should only change by a fixed amount each time it changes. For example, if the breakpoint set \(\xi_{-s}\le\cdots\le\xi_{-1}\le\xi_{1}\le\cdots\le\xi_{t}\) is maintained, it means: the slope is \(0\) in the interval \([\xi_{-1},\xi_1]\); moving left past each breakpoint decreases the slope by one; moving right past each breakpoint increases the slope by one; thus, in interval \([\xi_2,\xi_3]\), the slope is \(2\), in \([\xi_{-3},\xi_{-2}]\), the slope is \(-2\), and so on. Formally, the function can be written using slope breakpoints as

\[ f(x) = f(\xi_1) + \sum_{i=-s}^{-1}\max\{\xi_i-x,0\} + \sum_{i=1}^{\ell}\max\{x-\xi_i,0\}. \]

Its minimum is \(f(\xi_{-1})=f(\xi_1)\), attained at any point in \([\xi_{-1},\xi_1]\).

Example: Minimum Cost Increasing Sequence

[BalticOI 2004] Sequence 数字序列

Given a sequence \(\{a_i\}\) of length \(n\), find a strictly increasing sequence \(\{b_i\}\) that minimizes \(\sum_i|a_i-b_i|\), output the minimum value and any optimal solution \(\{b_i\}\).

Solution

First, \(\{b_i\}\) strictly increasing is equivalent to \(\{b'_i\}=\{b_i-i\}\) being weakly increasing. Therefore, we can find the weakly increasing sequence \(\{b'_i\}=\{b_i-i\}\) with minimum difference for \(\{a'_i\}=\{a_i-i\}\), then recover \(\{b_i\}\).

Consider a naive DP solution. Let \(f_i(x)\) be the minimum difference between the first \(i\) numbers chosen for \(\{b'_i\}\) and the first \(i\) numbers of \(\{a'_i\}\), given that the \(i\)-th number does not exceed \(x\):

\[ f_i(x) = \min\sum_{j=1}^i|a'_j-b'_j|\text{ s.t. }b'_1\le b'_2\le\cdots\le b'_i\le x. \]

The state transition equation is easily obtained as

\[ f_i(x) = \min_{y\le x}f_{i-1}(y)+|a'_i-y|. \]

The initial state is \(f_0(x)\equiv 0\), and the final answer is \(\min_xf_n(x)\). Using the convex function transformations mentioned earlier, from \(f_{i-1}(x)\) to \(f_i(x)\), two transformations are needed:

First, add \(|a'_i-x|\), which is equivalent to adding \(-1\) to all slope segments in \((-\infty,a'_i]\) and adding \(1\) to all slope segments in \([a'_i,+\infty)\);
Take the minimum of the resulting function, turning \(g(x)=f_{i-1}(x)+|a'_i-x|\) into \(f_i(x)=\min_{y\le x}g(y)\). According to previous analysis, this is equivalent to taking the infimal convolution of \(g(x)\) and \(0_{[0,+\infty)}\). Since the latter has only one slope segment with slope \(0\) extending infinitely to the right, inserting it into the slope segments of \(g(x)\) is equivalent to deleting all positive slope segments.

After clarifying these operations, we could directly maintain all slope segments with a balanced tree, but the code would be complex. Note that in this problem, the slope changes by at most \(1\) each time, so the absolute values of all slope segments do not exceed \(n\). Instead of directly maintaining slope segments, maintaining slope breakpoints is more convenient.

Let the breakpoint set of \(f_{-1}(x)\) be \(\xi_{-k}\le\cdots\le\xi_{-1}\le\xi_{1}\le\cdots\le\xi_{\ell}\). Then the two operations correspond to:

Add a negative slope breakpoint \(a'_i\) and a positive slope breakpoint \(a'_i\);
Pop all positive slope breakpoints \(\xi_1,\cdots,\xi_{\ell}\).

In actual maintenance, since after each operation there are no positive slope breakpoints, the slope breakpoints have the form \(\xi_{-k}\le\cdots\le\xi_{-1}\), and operations always occur at the junction of positive and negative slope segments, so a max-heap storing all breakpoints suffices. The two operations correspond to:

Insert \(a'_i\) twice;
Pop the heap top.

Of course, the current function's minimum value needs to be maintained after each operation. Since after the operation there are no positive slope segments, the function's minimum is its value at the heap top. Let the heap top before each operation be \(\xi_{-1}\), and the minimum be \(f_{i-1}(\xi_{-1})\). Since the popped heap top is the smallest breakpoint of the positive slope segments, the function's minimum equals its value at that point, so we can directly compute the function's value at the heap top before popping, i.e.,

\[ f_{i-1}(\max\{a'_i,\xi_{-1}\})+|\max\{a'_i,\xi_{-1}\}-a'_i|=f_{i-1}(\xi_{-1})+\max\{0,\xi_{-1}-a'_i\}. \]

The first equality holds because \(f_{i-1}(x)\) has no positive slope segments. Therefore, each step only needs to accumulate \(\max\{0,\xi_{-1}-a'_i\}\) to the minimum value.

This problem also requires outputting an optimal solution. Since at the end, the optimal solution is the heap top, \(b'_n\) can be directly determined. If the \(i\)-th optimal solution \(b'_i\) is known, to find the optimal \(f_{i-1}(x)\) satisfying \(x\le b'\), note that since \(f_{i-1}(x)\) is convex, the closer to its global minimum point, the better the solution. So just record the global minimum point of \(f_{i-1}(x)\) and take the minimum with \(b'_i\) to get the optimal \(b'_{i-1}\).

Time complexity is \(O(n\log n)\).

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n), b(n);
  for (int& x : a) std::cin >> x;
  for (int i = 0; i < n; ++i) a[i] -= i;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int i = 0; i < n; ++i) {
    max_heap.emplace(a[i]);
    max_heap.emplace(a[i]);
    res += max_heap.top() - a[i];
    max_heap.pop();
    b[i] = max_heap.top();
  }
  std::cout << res << '\n';
  for (int i = n - 2; i >= 0; --i) b[i] = std::min(b[i], b[i + 1]);
  for (int i = 0; i < n; ++i)
    std::cout << (b[i] + i) << (i == n - 1 ? '\n' : ' ');
  return 0;
}

Template problems:

Example: Transitions with Constraints

[NOISG 2018 Finals] Safety

Given a sequence \(\{a_i\}\) of length \(n\), find a sequence \(\{b_i\}\) satisfying \(|b_i-b_{i-1}|\le h\) for all \(1<i\le n\), minimizing \(\sum_i|a_i-b_i|\), output the minimum value.

Solution

The content is similar to the previous problem, but the constraint on \(\{b_i\}\) changes. Similarly, let \(f_i(x)\) be the minimum difference for the first \(i\) numbers when the \(i\)-th number is \(x\):

\[ f_i(x) = \min\sum_{j=1}^i|a_j-b_j|\text{ s.t. }|b_{j-1}-b_j|\le h,\forall 1<j\le i,~b_i=x. \]

Thus, the state transition equation is

\[ f_i(x) = |a_i-x| + \min_{|y-x|\le h} f_{i-1}(y). \]

The initial condition is \(f_0(x)\equiv 0\). The final answer is still \(\min_xf_n(x)\).

The state transition decomposes into operations on convex functions in two steps:

First take the minimum of \(f_{i-1}(x)\) to get \(\min_{|y-x|\le h} f_{i-1}(y)\), which is equivalent to the infimal convolution of \(f_{i-1}(x)\) and \(0_{[-h,h]}(x)\);
Then add \(|a_i-x|\) to the resulting function.

Again, since the slope changes by at most one each time, consider maintaining breakpoints. These two steps can be described as:

Shift all negative slope segments left by \(h\), and all positive slope segments right by \(h\);
Insert \(a_i\) twice.

Clearly, for this problem, maintaining negative and positive slope segments separately is more convenient. Since operations are concentrated near the zero-slope segment, consider using a two-heap technique, i.e., a max-heap for negative slope breakpoints and a min-heap for positive slope breakpoints. The overall shift operation is done with lazy tags. The second step requires inserting an \(a_i\) into each heap. After insertion, the top of the max-heap may not be less than or equal to the top of the min-heap. Then swap the tops until the size relation is satisfied.

Finally, consider how to update the minimum value during operations. Since the first shift operation does not change the minimum, only the heap top swaps need consideration. Let \(\xi_{-1}>\xi_1\). When swapping tops \(\xi_{-1}\) and \(\xi_1\), the function changes from

\[ \max\{0,x-\xi_{-1}\}+\max\{0,x-\xi_1\} \]

to

\[ \max\{0,x-\xi_{1}\}+\max\{0,x-\xi_{-1}\}. \]

During this, the function shape remains the same but is shifted downward by \(|\xi_{-1}-\xi_1|\). Therefore, to keep the function unchanged before and after swapping, it suffices to accumulate \(|\xi_{-1}-\xi_1|\) to the minimum value.

The algorithm's time complexity remains \(O(n\log n)\), because after each addition, the heap top swap is performed at most once.

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  long long h;
  std::cin >> n >> h;
  std::priority_queue<long long> max_heap;
  std::priority_queue<long long, std::vector<long long>, std::greater<>>
      min_heap;
  long long lt = 0, rt = 0;
  long long res = 0;
  for (; n; --n) {
    long long x;
    std::cin >> x;
    lt += h;
    rt += h;
    max_heap.emplace(x + lt);
    min_heap.emplace(x - rt);
    auto l = max_heap.top() - lt;
    auto r = min_heap.top() + rt;
    while (l > r) {
      max_heap.pop();
      min_heap.pop();
      res += l - r;
      max_heap.emplace(r + lt);
      min_heap.emplace(l - rt);
      l = max_heap.top() - lt;
      r = min_heap.top() + rt;
    }
  }
  std::cout << res << std::endl;
  return 0;
}

Template problems:

Maintaining Slopes

Some problems are more convenient to handle by maintaining slopes. Such problems can also often be solved using ideas of regretful greedy or simulated cost flow. In cost flow models, the minimum cost is often a convex function of flow, providing a basis for using Slope Trick.

Example: Stock Trading Problem

Codeforces 865 D. Buy Low Sell High

Given a stock price sequence \(\{p_i\}\) for \(n\) days (all positive), initial holdings are \(0\), each day you can buy one share, sell one share, or do nothing. Find the maximum profit after \(n\) days.

Solution

First consider a naive DP solution. Let \(f_i(x)\) be the maximum profit at the end of day \(i\) with \(x\ge 0\) shares held. Then

\[ f_i(x) = \max\{f_{i-1}(x-1)-p_i,f_{i-1}(x),f_{i-1}(x+1)+p_i\}. \]

Initial state: \(f_0(0)=0\), and \(f_0(x)=-\infty\) for all \(x\neq 0\). The answer is \(f_n(0)\).

From \(f_{i-1}(x)\) to \(f_i(x)\), two transformations are needed:

Take the supremum convolution of \(f_{i-1}(x)\) with the function

\[ h_i(x) = \begin{cases}p_i,&x=-1,\\0,&x=0,\\-p_i,&x=1\end{cases} \]

corresponding piecewise linear function \(\tilde h(x)\) (obviously concave);
This would give finite values in \([-1,0)\), contradicting the requirement \(x\ge 0\), so truncate the function to \([0,+\infty)\).

Transforming these into slope segment changes yields two steps:

Insert a slope segment of length \(2\) with slope \(-p_i\);
Delete the slope segment with the largest slope and length \(1\) among finite slope segments.

Since slope segment lengths are natural numbers, we can maintain several length-one slope segments, thus only needing to record each segment's slope. Since only insertion and max access are needed, a max-heap suffices. The steps are:

Insert \(-p_i\) twice;
Pop the heap top.

Also need to maintain \(f_i(0)\). After the first step, the function's value at \(x=-1\) is \(f_{i-1}(0)+p_i\), so its value at \(x=0\) is that plus the heap top about to be popped—which is the slope on \([-1,0]\). Since truncation does not change the value at \(x=0\), this is \(f_i(0)\).

Comparing this algorithm's implementation with the code for Minimum Cost Increasing Sequence shows it is equivalent to finding the minimum cost to turn stock prices into a weakly decreasing sequence.

Time complexity is \(O(n\log n)\).

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int& x : a) std::cin >> x;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int x : a) {
    max_heap.emplace(-x);
    max_heap.emplace(-x);
    res += x + max_heap.top();
    max_heap.pop();
  }
  std::cout << res << '\n';
  return 0;
}

Template problem:

Codeforces 865 D. Buy Low Sell High

Example: Earth Moving Problem

[USACO16OPEN] Landscaping P

Given sequences \(\{a_i\}\) and \(\{b_i\}\) of length \(n\), representing the current and required amounts of dirt in the \(i\)-th garden (cannot be more or less). Buying one unit of dirt and placing it in any garden costs \(X\), removing one unit from any garden costs \(Y\), transporting one unit from garden \(i\) to \(j\) costs \(Z|i-j|\). Find the minimum cost to satisfy all gardens. (\(a_i,b_i\le 10\))

Solution

Consider a naive DP solution. Let \(f_i(x)\) be the minimum cost to satisfy the first \(i\) gardens with a net surplus of \(x\) units of dirt to be sent to later gardens. If \(x<0\), it means a net deficit of \(|x|\) units needs to be brought from later gardens. Then the state transition equation can be written as

\[ f_i(x) = \min_{y\in\mathbf R} f_{i-1}(y) + |y|Z + h((x-y)+(b_i-a_i)). \]

Here, \(h(\delta)\) is the cost when the net purchase of dirt for the current garden is \(\delta\), i.e.,

\[ h(\delta) = \max\{0,\delta\}X + \max\{0,-\delta\}Y = \max\{\delta X,-\delta Y\}. \]

It is clearly convex. The meaning of the transition equation is:

When the net surplus from the first \(i-1\) gardens is \(y\), the minimum cost is \(f_{i-1}(y)\);
The cost to transport the net surplus (deficit) between \(i\) and \(i-1\) is \(|y|Z\);
Through buying/selling, adjust the dirt amount in garden \(i\) from \(a_i\) to \(b_i\) and adjust net surplus from \(y\) to \(x\), with minimum cost \(h((x-y)+(b_i-a_i))\).

Initial state: \(f_0(0)=0\), and \(f_0(x)=+\infty\) for all \(x\neq 0\). The answer is \(f_n(0)\).

Transforming \(f_{i-1}(x)\) to \(f_i(x)\) involves three steps:

First, add \(|x|Z\), yielding \(f_{i-1}(x)+|x|Z\);
Then, take infimal convolution with \(h(x)\), yielding \(\min_{y\in\mathbf R}f_{i-1}(y)+|y|Z+h(x-y)\);
Finally, shift the function left by \((b_i-a_i)\) units.

Transforming into operations on slope segments, also three steps:

Add \(-Z\) to all slope segments left of the origin, and add \(Z\) to all right of the origin;
Replace all slope segments less than \(-Y\) with \(-Y\), and all greater than \(X\) with \(X\);
Shift all slope segments left by \((b_i-a_i)\) units.

In the original problem, \(a_i\) and \(b_i\) are small, so maintaining several length-one slope segments suffices. Although there are infinitely many slope segments, they are bounded above by \(X\) and below by \(-Y\), and the number strictly between them is not large. Since insertion is not involved, two stacks can maintain slope segments on both sides of the origin, with range add and range max/min operations done via lazy tags. The three steps correspond to:

Add lazy tags to left and right stacks: left add \(-Z\), right add \(Z\);
Each time an element is popped from a stack, take max with \(-Y\) and min with \(X\). If the left stack is empty, pop \(-Y\). If the right stack is empty, pop \(X\);
Pop the top \((b_i-a_i)\) elements from the left stack and push them to the right stack; if \(b_i-a_i<0\), do the opposite.

When swapping stack tops, update the answer: moving left subtracts the current slope, moving right adds the current slope.

Algorithm complexity is \(O(n\max\{a_i,b_i\})\).

#include <iostream>
#include <stack>

int main() {
  int n;
  long long x, y, z;
  std::cin >> n >> x >> y >> z;
  std::stack<long long> neg, pos;
  long long lt = 0, rt = 0;
  long long res = 0;
  for (; n; --n) {
    int a, b;
    std::cin >> a >> b;
    lt -= z;
    rt += z;
    for (; b < a; ++b) {
      auto l = -y;
      if (!neg.empty()) {
        l = std::max(l, neg.top() + lt);
        neg.pop();
      }
      pos.emplace(l - rt);
      res -= l;
    }
    for (; b > a; --b) {
      auto r = x;
      if (!pos.empty()) {
        r = std::min(r, pos.top() + rt);
        pos.pop();
      }
      neg.emplace(r - lt);
      res += r;
    }
  }
  std::cout << res << std::endl;
  return 0;
}

Template problems:

Exercises

Finally, this article provides some problems from various algorithmic competitions that can be solved using Slope Trick, for practice.

References and Notes

Different textbooks may use different terms for convex functions. ↩
Also often called \(\min\) convolution, \(\inf\) convolution, or \((\min,+)\) convolution. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用