A DP Optimization for Constructing Monotonic Sequence Problems (Slope Trick)

A DP problem from 《算阶》 (Computational Steps) by the Blue Book with the characteristic of “extremely high conceptual difficulty, extremely short implementation code”.

This article records a little-known technique called slope trick for solving this problem.

The problem is numbered P2893 on Luogu:

Given a sequence $A_i$ of length $n$, construct a sequence $B_i$ of length $n$ that is non-strictly monotonic (non-decreasing or non-increasing), such that the value of $S=\sum^{n}_{i=1} |A_i-B_i|$ is minimized, and output this minimum $S$.

The meaning of this problem is, as shown in the figure below, to construct a sequence $B$ that is either non-strictly increasing or non-strictly decreasing, such that the sum of the distances between its terms and the corresponding elements of $A$ is minimized. There are also two similar variations of this problem on Luogu^{[1] [2]}.

This article first explains the $O(n^2)$ linear DP solution, and then focuses on the $O(n\log{n})$ slope trick method.

The problem requires both non-decreasing and non-increasing cases, which can be solved separately, and then take the minimum answer. The following only considers the case of constructing a non-decreasing sequence.

$O(n^2)$ Linear DP Solution ¶

Let $f(i, x)$ represent the minimum value of $S$ when the construction of the first $i$ numbers is completed and ends with the value $B_i=x$, It is easy to write the transfer equation (note that we are now looking for the non-decreasing case):

The pseudo-code implementation is roughly as follows:

memset(f, 0x3f, sizeof f);     // +inf, because we want the minimum
memset(f[0], 0, sizeof f[0]);  // i=0, take 0
int m = *max_element(A + 1, A + n + 1); // Maximum element value of A
for (int i = 1; i <= n; i++) {
  for (int x = 0; x <= m; x++) {
    for (int k = 0; k <= x; k++) {
      f[i][x] = min(f[i][x], f[i - 1][k] + abs(x - A[i]));
    }
  }
}
// The answer is the minimum value that can be taken when i=n
return *min_element(f[n], f[n] + m + 1);

According to the lemma, you can first discretize the values of the $A$ sequence, Assuming $a$ is the discretized sequence, it is ordered and deduplicated, the transfer equation can be expressed with subscripts:

After discretization, the 2nd and 3rd loops can be reduced to $O(n)$:

// Discretization: a is ordered and deduplicated
for (int i = 1; i <= n; i++) a[i] = A[i];
sort(a + 1, a + n + 1);
int m = unique(a + 1, a + n + 1) - (a + 1);

// DP solving, and use index instead of value x
memset(f, 0x3f, sizeof f);     // inf
memset(f[0], 0, sizeof f[0]);  // i=0
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= j; k++) {
            // a is ordered, k only needs to be <=j at this time
            f[i][j] = min(f[i][j], f[i - 1][k] + abs(a[j] - A[i]));
        }
    }
}
// The answer is the minimum value that can be taken when i=n
return *min_element(f[n], f[n] + n + 1);

Furthermore, the inner two loops can use similar optimization methods as the LCIS problem, and the overall can be further optimized to $O(n^2)$.

The idea is to regard the derivation process of $f(i, j)$ as a DP table filling process with $i$ as rows and $j$ as columns. You only need to maintain a variable $mi$, to synchronously follow up the dp minimum value in the previous row $f_{i-1}$ that satisfies $\leq j$. The root cause of this transfer optimization is that the innermost taking of the maximum value can linearly go hand in hand with the second layer. In this way, the 2nd and 3rd loops can be merged into 1 layer.

for (int i = 1; i <= n; i++) {
    int mi = 0x3f3f3f3f;
    for (int j = 1; j <= m; j++) {
        // mi synchronously follows up the minimum value of <=j in the previous row f[i-1]
        mi = min(mi, f[i - 1][j]);
        f[i][j] = mi + abs(a[j] - A[i]);
    }
}

So far, the $O(n^2)$ linear DP solution is explained.

Luogu P2893’s $O(n^2)$ Complete C++ Code Implementation - github

In addition, there is also a method of “mergeable heap”^[4] for this problem, but I also failed to understand its correctness.

Slope trick $O(n\log{n})$ Solution ¶

This solution will be explained for a relatively long time, divided into five parts:

1. Concept of slope trickable
2. Describing a slope trickable concave function with heaps
3. The $f_i(x)$ in the problem is a slope trickable concave function
4. Tracking changes in the answer
5. Extension - output a non-decreasing sequence $B$

Concept of slope trickable ¶

The slope trick technique may have originated from the problem codeforces 713C. The following description refers to this article on codeforces.

In short, it is a method that can use a priority queue/heap to maintain the inflection points and slope changes in the merging process of piecewise convex functions.

It sounds very tongue-twisting. To put it simply, it is “dynamic heap describes slope changes”.

If a function satisfies the following properties, it is considered to be describable by slope trick:

1. The function is continuous.
2. The function is piecewise, and each segment is a linear function with an integer slope.
3. It is a convex function or a concave function. In other words, the slope of the function is monotonically non-increasing or monotonically non-decreasing.

This kind of function can be called a slope trickable function. This kind of function has a very good property about merging:

1. The merged function $h(x) = f(x) + g(x)$ of two slope trickable functions $f(x)$ and $g(x)$ with the same concavity and convexity directions is also slope trickable.
2. The set of inflection points after merging is the union of the sets of inflection points of $f$ and $g$.

This property is also easy to understand. According to the derivation rule ^[5], we can know that $h’ = f’ + g’$, plus proof.

Since the characteristic of this problem is to find the minimum value, the following mainly studies concave functions. The principle should be similar for convex functions.

For example, the functions $f=|x-2|$ and $g=|x-4|$ are both slope trickable concave functions, and the merged $h = f + g$ is also a concave function. Moreover, it can be seen that the inflection point $\{2,4\}$ after merging is formed by merging the inflection points of $f$ and $g$ (the inflection point refers to the value of the abscissa $x$).

Describing a slope trickable concave function with heaps ¶

In fact, the $f$ function of this problem is a prefix minimum concave function (that is, there is only a downward slope on the left and no upward slope on the right), but for the sake of general explanation, This section first considers a more general concave function with slopes on both sides as an example, and will explain that a heap can be used to describe a slope trickable concave function.

Consider a continuously evolving example function $g_i(x)$, where $g_0(x) = 0$ :

Let’s examine the evolution process of the minimum value $\min{g_i(x)}$ of this function.

First of all, it can be argued by mathematical induction that each function $g_i(x)$ is a concave function that satisfies the definition of slope trickable, and its set of inflection points is $\{A_1,A_2,…,A_i\}$, proof omitted.

As $i$ progresses, let’s see what kind of changes will occur in the $g_i(x)$ function. Note that the derivative of the sum of functions is the sum of the derivatives ^[5]:

1. When $x \leq A_i$, the change in slope is $-1$.

   \[\begin{split} g_i(x) &= g_{i-1}(x) + A_i - x \\ \rightarrow g_i' &= g_{i-1}' -1 \end{split}\]

2. When $x > A_i$, the change in slope is $+1$.

   \[\begin{split} g_i(x) &= g_{i-1}(x) + x - A_i \\ \rightarrow g_i' &= g_{i-1}' +1 \end{split}\]

The following is an example diagram showing the change in the function $g_{i-1}$ evolving to $g_i$. According to the positional relationship between the newly added inflection point $A_i$ and the original optimal point $opt$, it is divided into two graphs on the left and right. It can be found that:

1. The falling section on the left of $A_i$ has a slope of $-1$ and will become steeper.
2. The rising section on the right of $A_i$ has a slope of $+1$ and will become steeper.
3. When $A_i \leq opt$, the point on the right side of it with the original slope of $-1$ will become the new optimal point.
4. When $A_i > opt$, the point on the left side of it with the original slope of $+1$ will become the new optimal point.

Next, try to use a data structure to describe this change.

You can use an ordered table, or more precisely, you can use two heaps to store the inflection points.

Specifically:

1. Max heap L to store inflection points with $slope \leq 0$ (referring to abscissa $x$), the slope is expressed as the opposite number of its depth in the heap.
2. Min heap R to store inflection points with $slope > 0$ (referring to abscissa $x$), the slope is expressed as its depth in the heap.
3. Since the depth of the heap is used to represent the slope, if the difference between the slopes of two inflection points is $>1$, then insert multiple copies of the inflection point to ensure that the difference between the slopes of adjacent elements in the heap is exactly $1$.

We can know that:

1. The optimal point $opt$ is at the top of the L heap, with a slope of $0$.
2. From the bottom of the L heap to the bottom of the R heap, the slope strictly increases in steps of $1$.

Now consider, when inserting a new inflection point $A_i$, how should the two heaps be maintained?

Because the slope change of the function $|x-A_i|$ at the inflection point $A_i$ is a change of $2$ from $-1$ to $+1$, So consider adding two $A_i$ to the heap to ensure that the difference between the slopes of adjacent elements in the heap is exactly $1$.

First consider the case where $A_i <= opt$, at this time, two $A_i$ should be placed in the L heap, and verify the changes in the slope of each segment:

1. The slope of the original optimal point $opt$ changes from $0$ to $+1$, it should be popped and placed in R.
2. Furthermore, the slope in R will all be $+1$, as expected.
3. In the L heap, the top element is popped out to the right of $A_i$:

   1. The depth of the inflection point to the right of $A_i$ in the heap will decrease, and the slope will all be $+1$, as expected.

      In particular, the element that was originally the second heap top will become the new optimal point.

   2. But at the same time, two $A_i$ are inserted, so the depth to the left of $A_i$ will be $+1$, which means the slope will be $-1$, which is also as expected.

The case for $A_i > opt$ is similar and will not be discussed further.

The $f_i(x)$ in the problem is a slope trickable concave function ¶

Now we finally return to the DP equation at the very beginning of the problem, that is, $f(i, x)$ represents the minimum value of $S$ when the construction of the first $i$ numbers is completed and ends with the value $B_i=x$:

For each $i$, construct a function $q_i(x)$:

And the DP function $f_i(x)$ is actually: $\min_{0 \leq k \leq x} \{ q_{i}(k) \}$, that is, $f_i(x)$ is the prefix minimum function of $q_i(x)$.

According to the previous discussion, the situation of $f_i(x)$ will be simpler, and only the max heap L on the left needs to be maintained:

1. Max heap L to maintain the inflection points and slope changes of the $f_i(x)$ function.
2. The optimal decision point is maintained at the top of the L heap.
3. The maintenance operation of the heap L is: add two $A_i$ each time, and pop the heap top once to discard it.

Tracking Changes in the Answer ¶

Consider the change in the answer in the question. Assume that the optimal point at the time of $i-1$ is at $x=opt_{i-1}$:

1. When $A_i > opt_{i-1}$, the optimal point is $A_i$, and $ans$ does not change at this time.

   The corresponding operation in the L heap is: push 2 $A_i$ and become the new heap top, and then pop the heap top.

   The effect is equivalent to only pushing 1 $A_i$. The depth of the inflection point to the left of $A_i$ in the heap is $+1$, and the slope will be $-1$, and the slope line will become steeper.

   

2. When $A_i \leq opt_{i-1}$, consider the case of $i$:

   

   The point with the original slope of $-1$ (the element of the second heap top) will become the new optimal point $opt_{i}$, which is the nearest inflection point to the left of $opt_{i-1}$.

   Moreover, it can be known that the value of the original optimal point $opt_{i-1}$ in the current new function $f_i(x)$ is also the current minimum function value:

   \[\begin{split} f_i(opt_i) &= f_i(opt_{i-1}) \\ &= \min{f_{i-1}(opt_{i-1})} + |opt_{i-1} - A_i| \\ &= f_{i-1}(opt_{i-1}) + opt_{i-1} - A_i \end{split}\]

   That is to say, the recursive formula of the answer is: $ans = ans + L.top() - A_i$ .

Next, it can be found that the recursive formula can actually be suitable for both cases 1 and 2.

Try to push into the heap first, and then check the top of the heap:

q.push(A[i]);
q.push(A[i]);
ans += q.top() - A[i];
q.pop();

1. Verify the case of $A_i > opt_{i-1}$, because at this time the top of the heap must be the larger $A_i$, so:

   \[\begin{split} ans &= ans + L.top() - A_i \\ &= ans + A_i - A_i \\ &= ans \end{split}\]

   The answer also meets this recursive formula and does not change.

2. Verify the case of $A_i \leq opt_{i-1}$. First push it into the heap. The top of the heap will not be replaced because $A_i$ does not exceed the top of the heap:

   \[\begin{split} ans & = ans + L.top() - A_i \\ & = ans + opt_{i-1} - A_i \end{split}\]

   The answer is still correct.

To summarize, push into the heap first, then calculate the answer, and a unified answer recursive formula can be used.

The final steps are:

1. Push two $A_i$ into the heap first.
2. Then calculate $ans = ans + L.top() - A_i$.
3. Pop the heap top to maintain the properties of the L heap.

The code to describe is as follows:

int ans = 0;
priority_queue<int> q;
for (int i = 1; i <= n; i++) {
    q.push(A[i]);
    q.push(A[i]);
    ans += q.top() - A[i];
    q.pop();
}

The overall time complexity is $O(n\log{n})$.

Also, note that returning to the original question, you also need to reverse the array to find the case of constructing a non-increasing sequence $B$, and then take the minimum answer of the two cases.

Luogu P2893’s $O(n\log{n})$ Complete C++ Code Implementation - github

Outputting a Non-decreasing Sequence ¶

Finally, how to output a non-decreasing sequence that meets the requirements?

It should be reminded that the value of $B_i$ should not be simply assigned to $L.top()$, because the optimal point will regress.

To ensure the overall optimum when $i=n$ is reached, there must be $B_n = opt_n$.

Push from back to front, when $i=n-1$, classify and discuss:

1. If $opt_{n-1} \leq opt_n$, directly take $B_{n-1} = opt_{n-1}$.

2. If $opt_{n-1} > opt_n$, it means that Case 2 caused the optimal point to regress.

   

   Since non-decreasing must be guaranteed, $ B_{n-1} \leq B_n$, then:

   1. $B_{n-1}$ is at most $B_n$.
   2. $B_{n-1}$ should be as close as possible to $opt_{n-1}$, and the slope of this section on the left is $-1$, and $opt_n$ is the nearest inflection point on the left.

   Overall, at this time, you can only take $\min{\{opt_{n-1}, opt_n\}}$.

By analogy in reverse order, the pseudo-code implementation is roughly as follows:

priority_queue<int> q;
for (int i = 1; i <= n; i++) {
    q.push(A[i]);
    q.push(A[i]);
    B[i] = q.top();  // opt(i)
    q.pop();
}
for (int i = n - 1; i; i--) B[i] = min(B[i], B[i + 1]);

P4331 problem ^[1] is a similar problem, but it requires a strictly increasing sequence $B$, and you have to use your brain.

Luogu P4331’s Complete C++ Code Implementation - github

Ending Remarks ¶

This question is indeed a great test of thinking, and the code is extremely short.

Slope trick is always an unpopular knowledge, and it is amazing that the slope is actually linked to the heap.

Wonderful~~ !

(End)

Please note that this post is an AI-automatically chinese-to-english translated version of my original blog post: http://writings.sh/post/slope-trick-mono-sequence.

Footnotes ¶

• Luogu P4331: Requires constructing a strictly increasing sequence $B$.
• Luogu P4597: Use each $+1$ or $-1$ operation to change $A$ into such $B$, and find the minimum number of operations.
• Proof of the lemma given in the 《算阶》 book - mathematical induction

  First, it is obviously true when $n=1$.

  Assume that it holds for $n=k-1$, at this time the constructed sequence is $B_1 .. B_{k-1}$:

  1. If $B_{k-1} \leq A_k$, directly let $B_k = A_k$.
  2. Otherwise, either let $B_k = B_{k-1}$, at this time the proposition still holds, or there exists a $j$ , let $Bj,B{j+1},…,B_k$ be the same value $v$. Considering the properties of the median, take the median $mid$ of $A_j,A_{j+1}…,A_k$:
     1. If $mid \geq B_{j-1}$, then $v=mid$ .
     2. Otherwise, there should be $ v = B_{j-1}$.

     In either case, the numbers in $B1..B_k$ have appeared in $A$.

  The place where I don’t understand this lemma is the second point:

  1. Taking the median of the $A$ of the previous paragraph and replacing all of this paragraph of $B$ with it, is it the best? This paragraph of $A$ is not necessarily monotonically decreasing.
  2. Does such a $j$ necessarily exist?
  3. When the median is still not satisfied, is it optimal to continue to take the previous element of this paragraph of $B$?

  If readers and friends have reasonable explanations, please give advice in the comments section.

• A method of maintaining the median with "mergeable heap"

  A method of maintaining the median with a mergeable heap was found in the problem solution area of P4331, But I didn’t understand its correctness.

  The general idea is: first consider each monotonic segment, and then the merging method.

  In two special cases, the following facts exist (these two points are easy to understand):

  1. For a non-decreasing segment in $A$, directly taking each item $B_i = A_i$, the $S$ of this segment is optimal.
  2. For a monotonically decreasing segment in $A$, you can only take each item of this segment of $B$ as the median of $A$ of this segment.

  The general idea of this type of solution is:

  1. First, set $B_i = A_i$ for all non-decreasing segments.
  2. Then take the median of this segment for all decreasing segments. If this median cannot form an increase with the previous $B$, continue to extend this segment of $A$ forward and find the median for it.
  3. It will eventually form a non-decreasing $B$.

  However, from the problem solution, this type of method does not have its correctness analysis.

• Derivation rule of derivatives - Wikipedia
• Reference materials: 《Slope trick explained》 by Kuroni - codeforces

Original Link： https://writings.sh/post/en/slope-trick-mono-sequence