# 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(NgN)$ 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(NgN)$ time solution to the first problem in zscoder's tutorial:

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

## Buy Low Sell High

### 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]≥0.$Then $dif[i][j]≤dif[i][j+1]$ for all $j≥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

### 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},…,a_{N}$ after all the transfers be $a_{1},a_{2},…,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=i=1∑N−1 ∣∣∣∣∣∣ j=1∑i (a_{j}−a_{j})∣∣∣∣∣∣ .$We can show that this is a lower bound and that it's attainable. The term $D=∑_{j=1}(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}=∑_{i=1}dif_{i}$ for each $0≤j≤N$. Similarly, define $dif_{i}=a_{i}−b_{i}$ and $d_{j}=∑_{i=1}dif_{i}$. Since we want $dif_{i}≥0$ for all $i$, we should have $d_{0}=d_{0}≤d_{1}≤⋯≤d_{N}=d_{N}.$ Conversely, every sequence $(d_{0},d_{1},…,d_{N})$ that satisfies this property corresponds to a valid way to assign values of $(a_{1},a_{2},…,a_{N})$.

Now you can verify that $C=∑_{i=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≤i≤N$ and $0≤j≤d_{N}$, let $dp[i][j]$ be the minimum cost to determine $d_{0},d_{1},…,d_{i}$ such that $d_{i}≤j$. Note that by definition, $dp[i][j]≥dp[i][j+1]$. We can easily calculate these values in $O(N⋅d_{N})$ time.

### Full Solution

Explanation

My Code

## USACO Landscaping

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

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 $∑A_{i}+∑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⋅∣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).

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

## Give Us Feedback on Slope Trick!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.