# Slope Trick

Author: Benjamin Qi

Slope trick refers to a way to manipulate piecewise linear convex functions. Includes a simple solution to USACO Landscaping.

## Tutorials

Resources | |||
---|---|---|---|

CF | 3 problems using this trick | ||

CF | clarifying the above and another example problem |

From the latter link (modified):

Slope trick is a way to represent a function that satisfies the following conditions:

- It can be divided into multiple sections, where each section is a linear function (usually) with an integer slope.
- It is a convex/concave function. In other words, the slope of each section is non-decreasing or non-increasing when scanning the function from left to right.

It's generally applicable as a DP optimization.

### Pro Tip

Usually you can come up with a slower (usually $O(N^2)$) DP first and then optimize it to $O(N\log N)$ with slope trick.

The rest of this module assumes that you know the basic idea of this trick. In particular, you should be at least somewhat familiar with the $O(N\log N)$ time solution to the first problem in zscoder's tutorial:

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Easy | ## Show TagsSlope Trick | Check CF |

It's ok if you found the explanations confusing; the example below should help clarify.

## Buy Low Sell High

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Easy | ## Show TagsSlope Trick |

### Slow Solution

Let $dp[i][j]$ denote the maximum amount of money you can have on day $i$ if you have exactly $j$ shares of stock on that day. The final answer will be $dp[N][0]$. This solution runs in $O(N^2)$ time.

Slow Code

If we run this on the first sample case, then we get the following table:

Input: 9 10 5 4 7 9 12 6 2 10 Output: dp[0] = { 0} dp[1] = { 0, -10} dp[2] = { 0, -5, -15} dp[3] = { 0, -4, -9, -19} dp[4] = { 3, -2, -9, -16, -26} dp[5] = { 7, 0, -7, -16, -25, -35} dp[6] = { 12, 5, -4, -13, -23, -35, -47} dp[7] = { 12, 6, -1, -10, -19, -29, -41, -53} dp[8] = { 12, 10, 4, -3, -12, -21, -31, -43, -55} dp[9] = { 20, 14, 7, -2, -11, -21, -31, -41, -53, -65}

However, the DP values look quite special! Specifically, let

$dif[i][j]=dp[i][j]-dp[i][j+1]\ge 0.$Then $dif[i][j]\le dif[i][j+1]$ for all $j\ge 0$. In other words, $dp[i][j]$ as a function of $j$ is **concave down**.

### Full Solution

Explanation

My Code

### Extension

*Stock Trading (USACO Camp)*: What if your amount of shares can go negative, but you can never have more than $L$ shares or less than $-L$?

## Potatoes & Fertilizers

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

LMiO | Normal | ## Show TagsSlope Trick |

### Simplifying the Problem

Instead of saying that moving fertilizer from segment $i$ to segment $j$ costs $|i-j|$, we'll say that it costs $1$ to move fertilizer from a segment to an adjacent segment.

Let the values of $a_1,a_2,\ldots,a_N$ after all the transfers be $a_1',a_2',\ldots,a_N'$. If we know this final sequence, how much did the transfers cost (in the best case scenario)? It turns out that this is just

$C=\sum_{i=1}^{N-1}\left|\sum_{j=1}^i(a_j-a_j')\right|.$We can show that this is a lower bound and that it's attainable. The term $D=\sum_{j=1}^i(a_j-a_j')$ denotes the number of units of fertilizer that move from segment $i$ to segment $i+1$. Namely, if $D$ is positive then $D$ units of fertilizer moved from segment $i$ to segment $i+1$; otherwise, $-D$ units of fertilizer moved in the opposite direction. Note that it is never optimal to have fertilizer moving in both directions.

Let $dif_i=a_i-b_i$ and define $d_j=\sum_{i=1}^jdif_i$ for each $0\le j\le N$. Similarly, define $dif_i'=a_i'-b_i$ and $d_j'=\sum_{i=1}^jdif_i'$. Since we want $dif_i'\ge 0$ for all $i$, we should have $d_0=d_0'\le d_1'\le \cdots\le d_N'=d_N.$ Conversely, every sequence $(d_0',d_1',\ldots,d_N')$ that satisfies this property corresponds to a valid way to assign values of $(a_1',a_2',\ldots,a_N')$.

Now you can verify that $C=\sum_{i=1}^{N-1}|d_i-d_i'|$. This makes sense since moving one unit of fertilizer one position is equivalent to changing one of the $d_i$ by one (although $d_0,d_N$ always remain the same).

### Slow Solution

For each $0\le i\le N$ and $0\le j\le d_N$, let $dp[i][j]$ be the minimum cost to determine $d_0',d_1',\ldots,d_i'$ such that $d_i'\le j$. Note that by definition, $dp[i][j]\ge dp[i][j+1]$. We can easily calculate these values in $O(N\cdot d_N)$ time.

### Full Solution

Explanation

My Code

## USACO Landscaping

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

Plat | Hard | ## Show TagsSlope Trick | External Sol |

This looks similar to the previous task (we're moving dirt instead of fertilizer), so it's not too hard to guess that slope trick is applicable.

### Slow Solution

Let $dp[i][j]$ equal the number of ways to move dirt around the first $i$ flowerbeds such that the first $i-1$ flowerbeds all have the correct amount of dirt while the $i$-th flowerbed has $j$ extra units of dirt (or lacks $-j$ units of dirt if $j$ is negative). The answer will be $dp[N][0]$.

### Full Solution

Explanation

My Solution

### Extension

We can solve this problem when $\sum A_i+\sum B_i$ is not so small by maintaining a map from $j$ to $dif[j+1]-dif[j]$ for all $j$ such that the latter quantity is nonzero. Then the operation "add $Z\cdot |j|$ to $DP[j]$ for all $j$" corresponds to a point update in the map (`advance()`

in the code below).

Code (from Alex Wei)

## Problems

Although we haven't provided any examples of this, some of the problems below will require you to merge two slope containers (usually priority queues).

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Normal | ## Show TagsSlope Trick | Check CF | ||

CC | Normal | ## Show TagsSlope Trick | Check CC | ||

CEOI | Normal | ## Show TagsSlope Trick | View Solution | ||

NOI.sg | Hard | ## Show TagsSlope Trick | View Solution | ||

CF | Hard | ## Show TagsSlope Trick | Check CF | ||

CF | Hard | ## Show TagsSlope Trick | Check CF | ||

APIO | Hard | ## Show TagsSlope Trick, Small to Large | View Solution | ||

CF | Very Hard | ## Show TagsSlope Trick | Check CF | ||

ICPC WF | Very Hard | ## Show TagsSlope Trick, Small to Large | Show Sketch |