Rare
 0/13

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(N2)\mathcal{O}(N^2)) DP first and then optimize it to O(NlogN)\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):

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsSlope Trick

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

Buy Low Sell High

Focus Problem – try your best to solve this problem before continuing!

Slow Solution

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

vector<vl> dp = {{0}};
int N;
int main() {
re(N);
F0R(i, N) {
int x;
re(x);
dp.pb(vl(i + 2, -INF));
F0R(j, i + 1) {

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.dif[i][j]=dp[i][j]-dp[i][j+1]\ge 0.

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

Full Solution

We'll process the shares in order. Suppose that we are currently considering the ii-th day, where shares are worth pip_i. We can replace (buy or sell a share) in the statement with (buy, then sell somewhere between 0 and 2 shares).

  • If we currently have jj shares and overall balance bb, then after buying, jj increases by one and bb decreases by pip_i. So we set dp[i][j]=dp[i1][j1]pidp[i][j]=dp[i-1][j-1]-p_i for all jj. Note that the differences between every two consecutive elements of dp[i]dp[i] have not changed.

  • If we choose to sell a share, this is equivalent to setting dp[i][j]=max(dp[i][j],dp[i][j+1]+pi)dp[i][j]=\max(dp[i][j],dp[i][j+1]+p_i) for all jj at the same time. By the concavity condition, dp[i][j]=dp[i][j+1]+pidp[i][j]=dp[i][j+1]+p_i will hold for all jj less than a certain threshold while dp[i][j]dp[i][j] will remain unchanged for all others. So this is equivalent to inserting pip_i into the list of differences while maintaining the condition that the differences are in sorted order.

  • So choosing to sell between 0 and 2 shares is represented by adding pip_i to the list of differences two times. After that, we should pop the smallest difference in the list because we can't end up with a negative amount of shares.

Example

The implementation is quite simple; maintain a priority queue representing dif[i]dif[i] that allows you to pop the minimum element. After adding ii elements, ansans stores the current value of dp[i][i]dp[i][i]. At the end, you add all the differences in dif[N]dif[N] to go from dp[N][N]dp[N][N] to dp[N][0]dp[N][0].

#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
priority_queue<int, vector<int>, greater<int>> pq;
long long ans = 0;
for (int i = 0; i < N; ++i) {
int p;

Extension

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

Potatoes & Fertilizers

Focus Problem – try your best to solve this problem before continuing!

Simplifying the Problem

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

Let the values of a1,a2,,aNa_1,a_2,\ldots,a_N after all the transfers be a1,a2,,aNa_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=i=1N1j=1i(ajaj).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=j=1i(ajaj)D=\sum_{j=1}^i(a_j-a_j') denotes the number of units of fertilizer that move from segment ii to segment i+1i+1. Namely, if DD is positive then DD units of fertilizer moved from segment ii to segment i+1i+1; otherwise, D-D units of fertilizer moved in the opposite direction. Note that it is never optimal to have fertilizer moving in both directions.

Let difi=aibidif_i=a_i-b_i and define dj=i=1jdifid_j=\sum_{i=1}^jdif_i for each 0jN0\le j\le N. Similarly, define difi=aibidif_i'=a_i'-b_i and dj=i=1jdifid_j'=\sum_{i=1}^jdif_i'. Since we want difi0dif_i'\ge 0 for all ii, we should have d0=d0d1dN=dN.d_0=d_0'\le d_1'\le \cdots\le d_N'=d_N. Conversely, every sequence (d0,d1,,dN)(d_0',d_1',\ldots,d_N') that satisfies this property corresponds to a valid way to assign values of (a1,a2,,aN)(a_1',a_2',\ldots,a_N').

Now you can verify that C=i=1N1didiC=\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 did_i by one (although d0,dNd_0,d_N always remain the same).

Slow Solution

For each 0iN0\le i\le N and 0jdN0\le j\le d_N, let dp[i][j]dp[i][j] be the minimum cost to determine d0,d1,,did_0',d_1',\ldots,d_i' such that dijd_i'\le j. Note that by definition, dp[i][j]dp[i][j+1]dp[i][j]\ge dp[i][j+1]. We can easily calculate these values in O(NdN)\mathcal{O}(N\cdot d_N) time.

Full Solution

Similar to before, this DP is concave up for a fixed ii! Given a piecewise linear function fi(x)f_i(x) that takes as input xx and outputs dp[i][x]dp[i][x], we need to support the following two operations to transform this function into fi+1f_{i+1}.

  • Add xk|x-k| to the function for some kk
  • Set f(x)=min(f(x),f(x1))f(x)=\min(f(x),f(x-1)) for all xx

Again, these can be done with a priority queue. Instead of storing the consecutive differences, we store the points where the slope of the piecewise linear function changes by one.

  • The first operation corresponds to inserting kk into the priority queue two times because the slope increases by two at x=kx=k.
  • The latter operation just corresponds to removing the greatest element of the priority queue.

This solution runs in O(NlogN)\mathcal{O}(N\log N) time.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll fst = 0; // value of DP function at 0
priority_queue<ll> points; // points where DP function changes slope
int main() {

USACO Landscaping

Focus Problem – try your best to solve 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]dp[i][j] equal the number of ways to move dirt around the first ii flowerbeds such that the first i1i-1 flowerbeds all have the correct amount of dirt while the ii-th flowerbed has jj extra units of dirt (or lacks j-j units of dirt if jj is negative). The answer will be dp[N][0]dp[N][0].

Full Solution

This DP is concave up for any fixed ii. To get dp[i+1]dp[i+1] from dp[i]dp[i] we must be able to support the following operations.

  • Shift the DP curve AiA_i units to the right.
  • Shift the DP curve BiB_i units to the left.
  • Add ZjZ\cdot |j| to DP[j]DP[j] for all jj.
  • Set DP[j]=min(DP[j],DP[j1]+X)DP[j] = \min(DP[j],DP[j-1]+X) and DP[j]=min(DP[j],DP[j+1]+Y)DP[j] = \min(DP[j],DP[j+1]+Y) for all jj.

As before, it helps to look at the differences dif[j]=DP[j+1]DP[j]dif[j]=DP[j+1]-DP[j] instead. We'll maintain separate deques for difdif depending on whether j<0j < 0 or j0j\ge 0. We'll call these the left and right deques, respectively.

  • The first two operations correspond to repeatedly popping the last element off of the left deque and adding it to the front of the right deque (or vice versa, depending on the direction of the shift).
  • The third operation corresponds to subtracting ZZ from all elements of the left deque and adding ZZ to all elements of the right deque.
  • The last operation corresponds to setting dif[j]=max(dif[j],Y)dif[j]=\max(dif[j],-Y) for all j<0j < 0 and dif[j]=min(dif[j],X)dif[j] = \min(dif[j],X) for all j0j\ge 0.

We can implement the last operation by updating all of the differences in the deques "lazily." This solution runs in O(Ai+Bi)\mathcal{O}(\sum A_i+\sum B_i) time.

#include <bits/stdc++.h>
using namespace std;
int N, X, Y, Z;
int difl, difr; // "lazy" update
deque<int> L, R;
long long ans;
void rig() { // shift right A, so origin moves left

Extension

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

Code from Alex Wei.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
ifstream fin("landscape.in");
ofstream fout("landscape.out");

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

StatusSourceProblem NameDifficultyTags
CFNormal
Show TagsSlope Trick
CCNormal
Show TagsSlope Trick
CEOINormal
Show TagsSlope Trick
NOI.sgHard
Show TagsSlope Trick
CFHard
Show TagsSlope Trick
CFHard
Show TagsSlope Trick
APIOHard
Show TagsSlope Trick, Small to Large
CFVery Hard
Show TagsSlope Trick
ICPC WFVery 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!