[Tutorial] Intuition on Slope Trick

Revision en9, by maomao90, 2022-06-03 14:08:52

Introduction

As mentioned in my previous blog, I will be writing a tutorial about slope trick. Since there are already many blogs that goes through the concept of slope trick, my blog will focus more on the intuition behind coming up with the slope trick algorithm.

Hence, if you do not know slope trick yet, I suggest that you read other slope trick blogs such as https://codeforces.me/blog/entry/47821 and https://codeforces.me/blog/entry/77298 before reading my blog. In the future explanation on the example problems, I will assume that the reader already knows the big idea behind slope trick but do not know how to motivate the solution.

When to use slope trick?

Most of the time, slope trick can be used to optimise dp functions in the form of $$$dp_{i, j} = \min(dp_{i - 1, j - 1}, dp_{i - 1, j} + A_i)$$$ or something similar. In this kind of dp functions, the graph of the dp function where the x-axis is $$$j$$$ and y-axis is $$$dp_{i, j}$$$ changes predictably from $$$i$$$ to $$$i + 1$$$ which allows us to store the slope-changing points and move to $$$i + 1$$$ by inserting and deleting some slope-changing points.

Sometimes, slope trick can also be an alternative solution to a greedy solution. The code will probably end up being the same as well, so sometimes slope trick can help you to find out the greedy solution instead. Personally, I find that slope trick is very helpful in this area as we do not have to proof the greedy since dp completely searches all possible states and is definitely correct.

Examples

Social Distancing

Abridged Statement

You are given a array of $$$n$$$ numbers $$$a_1,a_2,\ldots,a_n$$$. You want to select a permutation $$$p_1,p_2,\ldots,p_n$$$ of size $$$n$$$ such that the following cost $$$\sum\limits_{i=1}^{n-1} a_{\max(p_i, p_{i+1})}$$$ is minimized. Find the minimum possible cost.

Ideas

We can iterate from $$$i=1$$$ to $$$i=n$$$ and pick which position to put $$$i$$$. If you put $$$a_i$$$ directly adjacent to two earlier elements, it will contribute to a cost of $$$2a_i$$$. If you put it adjacent to one, it will contribute to a cost of $$$a_i$$$. Otherwise, if you put it by itself, it will not contribute to the cost.

For example, for the array $$$a = [1, 3, 5]$$$, we first place $$$a_1$$$ by itself as there is nothing else placed yet. Then, we can put $$$a_2$$$ by itself as well and finally we put $$$a_3$$$ in the middle of both of them, contributing to a cost of $$$10$$$. However, we can achieve a cost of 8 by putting $$$a_2$$$ next to $$$a_1$$$, contributing to a cost of $$$3$$$ and finally putting $$$a_3$$$ next to $$$a_2$$$, contributing to a cost of $$$5$$$.

We can think of the operations as the following. Combining two connected components incur a cost of $$$2a_i$$$, doing nothing incurs a cost of $$$a_i$$$, and adding a connected component is free. Hence, we can come up with the following dp.

$$$dp[i][j] = \min(dp[i - 1][j + 1] + 2a_i, dp[i - 1][j] + a_i, dp[i - 1][j - 1])$$$

Using the same array $$$a = [1, 3, 5]$$$, we have the following dp table where the cell in the $$$i$$$-th row and $$$j$$$-th column represent $$$dp[i][j]$$$.

i\j 1 2 3
1 0 $$$\infty$$$ $$$\infty$$$
2 3 0 $$$\infty$$$
3 8 3 0

Solution

From the dp function, we can see that $$$dp[i]$$$ is just made up of 3 different copies of $$$dp[i - 1]$$$ shifted in different directions. This is often how slope trick looks like. Let us draw some graphs to see how the dp changes from $$$i - 1$$$ to $$$i$$$.

Let us see how we can obtain the graph of $$$dp[i]$$$ from $$$dp[i - 1]$$$. From the recurrence relation, we can see that $$$dp[i]$$$ is obtained by taking the minimum of the following 3 graphs: $$$dp[i - 1]$$$ shifted 1 to the right, $$$dp[i - 1]$$$ shifted $$$a_i$$$ upwards, and $$$dp[i - 1]$$$ shifted 1 to the left and $$$2a_i$$$ upwards.

As you can see in the image to the right, $$$dp[3]$$$ (shown in blue lines) can be formed by duplicating $$$dp[2]$$$ (shown in dotted lines) 3 times. Furthermore, the gradients of the resulting graph seems to be related to $$$a_i$$$.

Let us see how the dp function changes for a more complicated function. For this purpose, we will use the array $$$a = [1, 5, 5, 3, 6, 4]$$$. Supposed we have already calculated $$$dp[5]$$$ (shown in dotted lines) and want to calculate $$$dp[6]$$$.

Note that the crosses are colour coded according to which $$$j$$$ it came from ($$$dp[5][1]$$$ is cyan, $$$dp[5][2]$$$ is green, $$$dp[5][3]$$$ is blue, $$$dp[5][4]$$$ is magenta, and $$$dp[5][5]$$$ is brown). We can see that as we compare the 3 overlapping graphs, the point where one graph starts to become the minimum is when the gradient becomes larger than $$$a_i$$$ (in this case $$$a_6 = 4$$$). Why is that so?

If we only compare the red and black line, we see that the difference between a point on the red line and the same coloured point on the black line (it is one spot to the left) always has a difference of $$$a_i$$$. This is because same coloured points comes from the same $$$dp[i - 1][j]$$$ and only differ from shifting upwards by $$$a_i$$$.

Hence, when we look from right to left, while the gradient of the red line is less than $$$a_i$$$, the red line is always optimal as the difference between two adjacent points on the red line is equal to the gradient while the difference between the adjacent points on the black line and red line is equal to $$$a_i$$$. The moment $$$a_i$$$ becomes smaller than the gradient, the black line becomes more optimal instead, and when we switch from the black line to red line, the new gradient in between the two lines is $$$a_i$$$ (see the blue points on the right graph).

Hence, if we store the gradients of $$$dp[i - 1]$$$ in a priority queue, all we need to do to transition to $$$dp[i]$$$ is to insert $$$a_i$$$ two times. However, since we do not want $$$dp[i][0]$$$, we can just pop out the largest gradient which represents $$$dp[i][0]$$$. Then after we are done processing $$$dp[n]$$$, the answer is just the sum of the gradients in the priority queue.

Code

ARC123D — Inc, Dec — Decomposition

Abridged Statement

Given an array of $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$.

You want to construct two arrays $$$b_1, b_2, \ldots, b_n$$$ and $$$c_1, c_2, \ldots, c_n$$$ that satisfies the following conditions

  • $$$a_i = b_i + c_i$$$ for all $$$1 \le i \le n$$$,
  • $$$b$$$ is non-decreasing,
  • $$$c$$$ is non-increasing

Find the minimum possible cost of $$$\sum_{i=1}^n(|b_i| + |c_i|)$$$

Ideas

We define $$$dp[i][j]$$$ as the minimum possible cost from $$$1$$$ to $$$i$$$ such that $$$b_i \le j$$$. By letting $$$b_i = k$$$ for each $$$k \le j$$$, we can come up with the following relation

$$$dp[i][j] = \max_{k \le j} (dp[i - 1][k - \max(0, a_i - a_{i - 1})] + |k| + |a_i - k|)$$$

The reason why we have $$$dp[i - 1][k - \max(0, a_i - a_{i - 1})]$$$ is to account for the non-increasing property of $$$c$$$. Let $$$k' = b_{i - 1}$$$ and $$$k = b_i$$$. Then, $$$c_{i - 1} = a_{i - 1} - k'$$$ and $$$c_i = a_i - k$$$. Since $$$c_{i -1} \ge c_i$$$, we have $$$a_{i - 1} - k' \ge a_i - k$$$, it simplifies to $$$k' \le k - (a_i - a_{i - 1})$$$.

Solution

Does the absolute signs remind you of 713C - Sonya and Problem Wihtout a Legend? If we plot the graph of $$$y = |x| + |a_i - x|$$$, we get

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // the offset in the x direction
    long long offset = 0;
    // the y coordinate at the point where the line is horizontal
    long long ans = 0;
    priority_queue<long long> pq;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            offset += max(0, a[i] - a[i - 1]);
        }
        pq.push(-offset);
        pq.push(a[i] - offset);
        ans += abs(a[i]);
        long long u = pq.top(); pq.pop();
        ans += 2 * (u + offset - max(0, a[i]));
    }
    cout << ans << '\n';
    return 0;
}

Tags slope trick, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en19 English maomao90 2023-07-31 12:05:57 9 Tiny change: 'rrect.\n\n# Exam' -> 'rrect.\n\n[cut]\n\n# Exam'
en18 English maomao90 2023-03-06 15:24:48 8
en17 English maomao90 2022-06-25 16:23:43 837
en16 English maomao90 2022-06-25 15:24:21 429
en15 English maomao90 2022-06-25 14:11:11 0 (published)
en14 English maomao90 2022-06-25 14:10:55 10
en13 English maomao90 2022-06-25 14:08:36 36982
en12 English maomao90 2022-06-24 19:03:53 5654
en11 English maomao90 2022-06-17 16:38:41 6876
en10 English maomao90 2022-06-16 17:34:39 1392
en9 English maomao90 2022-06-03 14:08:52 1984
en8 English maomao90 2022-05-27 04:53:00 25 Tiny change: '6]$.\n\n![](https://' -> '6]$.\n\n![Image of dp[5] to dp[6]](https://'
en7 English maomao90 2022-05-27 04:51:38 2766 Tiny change: 'ueue.\n\n<spoil' -> 'ueue.\n\n<\br>\n\n<spoil'
en6 English maomao90 2022-05-26 19:00:35 73 Tiny change: '"50%"/> \n' -> '"50%"/> \n\n![ ](https://codeforces.me/37c084/Slope Trick 3.png)'
en5 English maomao90 2022-05-26 17:51:46 504 Tiny change: '<img src="/predownlo' -> '<img src="https://codeforces.me/predownlo'
en4 English maomao90 2022-05-26 17:36:51 60
en3 English maomao90 2022-05-26 17:12:00 355
en2 English maomao90 2022-05-26 17:00:18 79 Tiny change: '0 |' -> '0 |\n\n[](https://codeforces.me/f338ff/Slope Trick.png)'
en1 English maomao90 2022-05-26 16:08:21 3311 Initial revision (saved to drafts)