Hi everyone! Following my last article, today I'm writing about a not-so-common trick that has nevertheless appeared in some problems before and might be helpful to you. I'm not sure if this trick has been given a name yet so I'd refer to it as "Slope Trick" here.

Disclaimer : It would be helpful to have a pen and paper with you to sketch the graphs so that you can visualize these claims easier.

Example Problem 1 : 713C - Sonya and Problem Wihtout a Legend

This solution originated from koosaga's comment in the editorial post here.

The solution below will solve this problem in , wheareas the intended solution is *O*(*n*^{2}).

So, the first step is to get rid of the strictly increasing condition. To do so, we apply `a[i] -= i`

for all *i* and thus we just have to find the minimum number of moves to change it to a non-decreasing sequence.

Define *f*_{i}(*x*) as the minimum number of moves to change the first *i* elements into a non-decreasing sequence such that *a*_{i} ≤ *x*.

It is easy to see that by definition we have the recurrences

*f*_{i}(*X*) = *min*_{Y ≤ X}(|*a*_{i} - *Y*|) when *i* = 1

and

*f*_{i}(*X*) = *min*_{Y ≤ X}(*f*_{i - 1}(*Y*) + |*a*_{i} - *Y*|}.

Now, note that *f*_{i}(*X*) is non-increasing, since it is at most the minimum among all the values of *f* for smaller *X* by definition. We store a set of integers that denotes where the function *f*_{i} change slopes. More formally, we consider the function *g*_{i}(*X*) = *f*_{i}(*X* + 1) - *f*_{i}(*X*). The last element of the set will be the smallest *j* such that *g*_{i}(*j*) = 0, the second last element will be the smallest *j* such that *g*_{i}(*j*) = - 1, and so on. (note that the set of slope changing points is bounded)

Let *Opt*(*i*) denote a position where *f*_{i}(*X*) achieves its minimum. (i.e. *g*_{i}(*Opt*(*i*)) = 0) The desired answer will be *f*_{n}(*Opt*(*n*)). We'll see how to update these values quickly.

Now, suppose we already have everything for *f*_{i - 1}. Now, we want to update the data for *f*_{i}. First, note that all the values *x* < *a*_{i} will have its slope decreased by 1. Also, every value with *x* ≥ *a*_{i} will have its slope increased by 1 unless we have reached the *slope* = 0 point, in which the graph never goes up again.

There are two cases to consider :

Case 1 : *Opt*(*i* - 1) ≤ *a*_{i}

Here, the slope at every point before *a*_{i} decreases by 1. Thus, we push *a*_{i} into the slope array as this indicates that we decreases the slope at all the slope changing points by 1, and the slope changing point for *slope* = 0 is *a*_{i}, i.e. *Opt*(*i*) = *a*_{i}. Thus, this case is settled.

Case 2 : *Opt*(*i* - 1) > *a*_{i}

Now, we insert *a*_{i} into the set, since it decreases the slope at all the slope changing points before *a*_{i} by 1. Furthermore, we insert *a*_{i} again because it increases the slope at the slope changing points between *a*_{i} and *Opt*(*i* - 1) by 1. Now, we can just take *Opt*(*i*) = *Opt*(*i* - 1) since the slope at *Opt*(*i* - 1) is still 0. Finally, we remove *Opt*(*i* - 1) from the set because it's no longer the first point where the slope changes to 0. (it's the previous point where the slope changes to - 1 and the slope now becomes 0 because of the addition of *a*_{i}) Thus, the set of slope changing points is maintained. We have *f*_{i}(*Opt*(*i*)) = *f*_{i - 1}(*Opt*(*i* - 1)) + |*Opt*(*i* - 1) - *a*_{i}|.

Thus, we can just use a priority queue to store the slope changing points and it is easy to see that the priority queue can handle all these operations efficiently (in time).

Here's the implementation of this idea by koosaga : 20623607

This trick is called the "Slope Trick" because we're considering the general function and analyzing how its slope changes at different points to find the minimum or maximum value.

The next example is APIO 2016 P2 — Fireworks

This problem was the "killer" problem of APIO 2016, and was solved by merely 4 contestants in the actual contest.

I'll explain the solution, which is relatively simple and demonstrates the idea of slope trick.

So, the idea is similar to the last problem. For each node *u*, we store a function *f*(*x*) which denotes the minimum cost to change the weights on edges in the entire subtree rooted at *u* including the parent edge of *u* such that the sum of weights on each path from *u* to leaves are equal to *x*. We'll store the slope changing points of the function in a container (which we'll determine later) again. In addition, we store two integers *a*, *b*, which denotes that for all *x* ≥ *X*, where *X* is the largest slope changing point, the value of the function is *aX* + *b*. (clearly this function exists, since when *X* increases one can always increase the parent node by 1)

Now, for the child nodes *i*, it is clear that *a* = 1, *b* = - *c*_{i}, where *c*_{i} is the cost of the parent edge of *i*, and the slope changing points are {*c*_{i}, *c*_{i}}.

For a non-leaf node *u*, we have to combine the functions from its children first. Firstly, we set the function as the sum of all functions of its child, and we'll correct it later. We set the value *a* of this node as the sum of all *a*s of its children, and similarly for *b*. Also, we combine all the slope-changing points together. It is important that we merge the smaller sets into the larger set. (see dsu on tree, a.k.a. small-to-large technique)

Now, the function is still incorrect. Firstly, note that all the slope-changing points that have slope > 1 is meaningless, because we can just increase the parent edge by 1 to increase the sum of the whole subtree, so we can remove these slope-changing points while updating the values of *a*, *b*. Suppose we remove a slope-changing point *x* with slope *a*, then we decrement *a*, increase *b* by *x*, and remove *x* from the set. (this is because *ax* + *b* = (*a* - 1)*x* + (*b* + *x*)) Repeat this till *a* becomes at most 1.

Next, since the cost of the parent edge is *c*_{i}, we have to shift the slope 0 and 1 changing points to the right by *c*_{i}. Note that the slope - 1 changing point doesn't change, because we can just reduce the weight of *c*_{i} until it reaches 0. (note that the condition that the weights can be reduced to 0 helped here)

Finally, we have to decrease *b* by *c*_{i}, since we shifted the points to the right by *c*_{i}. Thus, the function for this node is now complete.

Thus, we can do a dfs and keep merging functions until we get the function for the root node. Then, we just have to find the value of the function when *a* = 0. (using the same method by we decrease *a* until it reaches 0) Finally, the answer will be the updated value of *b* at the root node, and we're done.

We'll use a priority queue to store the slope changing points as it is the most convenient option.

## Beyond APIO 2016 Fireworks

Now, the next example is the generalization of this problem. It has came from Codechef October Challenge — Tree Balancing. We'll solve this using the slope trick as well.

The Codechef problem is the same as the last problem, except :

The weights of the edges can be changed to negative values

You must output a possible construction aside from the minimum cost needed

The edges now have a cost

*w*_{i}, and when you change the value of an edge by 1, your total cost increases by*w*_{i}.

However, it is still possible to solve this using Slope Trick.

Firstly, we suppose that *w*_{i} = 1, to simplify the problem. Now, since the edges can be changed to negative values, at each node there is no point with slope that has absolute value greater than 1, since changing the parent edge will yield a better result. Thus, each node actually have only 2 slope-changing points, the point where the slope changes from - 1 to 0 and the point where the slope changes from 0 to 1. Thus, this means that we have to pop slope-changing points from the front as well as the back of the set. The best way to store the data is to use a multiset.

With this modification, we can find the minimum cost needed like before. Now, the second part of the question is, how to reconstruct the answer? This part is not hard if you understand what we're doing here. The problem reduces to solving for each node *u*, if I need to make the sum of weights from the parent of *u* to all leaves equal to *x*, what should the parent edge weight be, where *x* is given. We start from the childrens of the root, with value *x* which is equal to the point where the slope changes from 0 to 1. (i.e. the point that yields minimum value)

For each node we store the 2 slope-changing points *l*_{i}, *r*_{i} in an array while we find the minimum cost. Now, if *l*_{i} ≤ *x* ≤ *r*_{i}, then the best thing to do is not change the parent edge. If *x* > *r*_{i}, then we should increase the parent edge value by *x* - *r*_{i}. Otherwise, we should decrease the parent edge value by *l*_{i} - *x*.

Thus, we can find the required weights for the parent nodes and it remains to push the remaining sum of weights needed to its children and recurse until we get all the weights of the edges. The time complexity is the same.

My submission for this case, which gives 20 points

To get the full AC, we need to solve the cost-weighted case. It is actually similar to this case, but we have to modify the solution a bit.

The idea is still the same. However, the slope changing points has increased by a lot. To efficiently store these slope points, we will store the compressed form of the set. For example, the set {3, 4, 5, 5, 5, 5, 6, 6} will be stored as {(3, 1), (4, 1), (5, 4), (6, 2)}. Basically, we store the number of occurences of the integers instead of storing it one by one. We can use a map to handle this.

The base case is a bit different now. Suppose the leaf node is *u* and the cost of its parent edge is *d*_{u}. Then, *a* = *d*_{u}, *b* = - *c*_{u} × *d*_{u}, where *c*_{u} is the weight of its parent edge. The slope changing points is {(*c*_{u}, 2*d*_{u})}.

Merging the functions to its parent will be the same. Now, we have to update the slope changing points and the function *ax* + *b*. First, we remove all points with slope > *d*_{u} and < - *d*_{u}, as we can just change the parent edge. Then, we have to shift every slope changing point by *c*_{u}. However, shifting the whole map naively is inefficient. The trick here is to store a counter *shift* for each node that denotes the amount to add for each slope changing point. Now, the shifting part is equivalent to just adding *c*_{u} to the counter *shift*. Finally, we update *a* and *b* as before.

To recover the solution, we use the same method as above, with some changes. Firstly, *l* and *r* will be the minimum slope changing point of the function and maximum slope changing point of the function respectively. Secondly, if the sum of *d*_{i} of all children is less than the *d*_{i} of the parent edge, then we do not change the weight of the parent edge, as it is sufficient to just update all the children edges.

My implementation of this solution (100 points)

That's it for this post. If you know any other application of this trick, feel free to post them in the comments.

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).You are really inspiring, and your performance is becoming better everyday. I have hardly been in a contest on Codechef or Hackerrank with not your name in the leaderboard. I was wondering whether there's some peculiar thing that you have been doing lately. Perhaps the ladders or something that helped you improve?

Fabulous math background, isn't it enough ?!

3 IMO participations (2 Bronze medals)

And

IOIbronze :)rachitjain you are an inspiration to me. At least you can tell us something about your training. Did you use ladders or something else to reach div1?

Practised DP from problemset and Div2 D,E. Plus upsolving.

In problem Fireworks, i do not understand why when we remove a slope changing point by decreasing a and increasing b by x, the function becomes correct ???

Can we somehow recover the answer sequence in 713C - Sonya and Problem Wihtout a Legend?

suffix minimum of opt[] is the answer (sorry but I don't remember why)

From the definition, opt[i] = the minimum value of a[i] in order to get the best sequence of the first i values. But suppose opt[i] > opt[j] and i < j. In order to get a nondecreasing subsequence, a[i] should be decreased to opt[j] instead of opt[i]. That's why a[i] should be min(opt[i], opt[i + 1], ..., opt[n]).

Are there any other problems that involve this optimization?

This problem on AtCoder: http://arc070.contest.atcoder.jp/tasks/arc070_c

Could you help me understand what is needed to maintain the slope segments? I can build the graph by hand, but I couldn't understand exactly what the accepted codes are keeping.

Can you explain in details why we have to insert a[i] twice in case 2?

Assume that we have some points in our set of slope changing points — let them be

b_{1},b_{2},b_{3}, ...b_{k}(b_{i}≥b_{i + 1}). When we inserta_{i}we want to decrease all slopesb_{j}≥a_{i}by 1 and increaseb_{j}<a_{i}by 1. We also have to removeb_{1}. But note that after removingb_{1}all points are increased by 1. In order to decrease pointsb_{j}≥a_{i}by 1 in original set we have to decrease them by 2 in modified set (after removingb_{1}) so we inserta_{i}twice.Thank you very much ^^

If we slightly change the definition of our set of slope-change points so that it can incorporate duplicates for when the slope changes by more than 1, we can show that you can simply insert a_i twice, update f(opt(i)) with the top element, then remove the top element. This results in a really short implementation: 39851508

Can anyone please explain why fi(X) is non-increasing?