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 ko_osaga's comment in the editorial post here.

The solution below will solve this problem in , wheareas the intended solution is O(n²).

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 ko_osaga : 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 as 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.

Official Solution

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 :

1. The weights of the edges can be changed to negative values

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

3. 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, 2d_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.