# 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 $\mathcal{O}(N^2)$) DP first and then optimize it to $\mathcal{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 able to solve the following problem (it's almost identical to the first problem in zscoder's tutorial):

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

CSES | Easy | ## Show TagsSlope Trick | |||||||

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

## Buy Low Sell High

Focus Problem – read through this problem before continuing!

### 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 $\mathcal{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

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

Focus Problem – read through this problem before continuing!

### 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

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 $\mathcal{O}(N\cdot d_N)$ time.

### Full Solution

Explanation

My Code

## USACO Landscaping

Focus Problem – read through this problem before continuing!

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 | |||||
---|---|---|---|---|---|---|---|---|---|

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

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

CEOI | Normal | ## Show TagsSlope Trick | |||||||

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

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

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

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

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

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

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!