Hi everyone! Following my [last article](http://codeforces.me/blog/entry/47764), 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 : [problem:713C]↵
↵
This solution originated from [user:koosaga,2016-10-16]'s comment in the editorial post [here](http://codeforces.me/blog/entry/47094?#comment-315161).↵
↵
The solution below will solve this problem in $O(n\log n)$, 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} \le x$.↵
↵
It is easy to see that by definition we have the recurrences↵
↵
$f_{i}(X) = min_{Y \le X}(|a_{i} - Y|)$ when $i = 1$ ↵
↵
and ↵
↵
$f_{i}(X) = min_{Y \le 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 \ge 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) \le 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 $O(\log n)$ time). ↵
↵
Here's the implementation of this idea by [user:koosaga,2016-10-16] : [submission: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](https://github.com/apio-2016/apio2016-tasks/blob/master/fireworks/descriptions/en.pdf)↵
↵
This problem was the "killer" problem of APIO 2016, and was solved by merely $4$ contestants in the actual contest. ↵
↵
I'll explain the $O((N + M)\log^{2}(N + M)$ 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 \ge 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](http://codeforces.me/blog/entry/44351))↵
↵
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](https://github.com/apio-2016/apio2016-tasks/blob/master/fireworks/solutions/fireworks_seokhwan_nlg2n.cpp)↵
↵
Beyond APIO 2016 Fireworks↵
------------------↵
↵
Now, the next example is the generalization of this problem. It has came from [Codechef October Challenge — Tree Balancing](https://www.codechef.com/OCT16/problems/TREEBAL). 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} \le x \le 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](https://www.codechef.com/viewsolution/11786858) ↵
↵
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} \times 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)](https://www.codechef.com/viewsolution/11865552)↵
↵
That's it for this post. If you know any other application of this trick, feel free to post them in the comments.
↵
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 : [problem:713C]↵
↵
This solution originated from [user:koosaga,2016-10-16]'s comment in the editorial post [here](http://codeforces.me/blog/entry/47094?#comment-315161).↵
↵
The solution below will solve this problem in $O(n\log n)$, 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} \le x$.↵
↵
It is easy to see that by definition we have the recurrences↵
↵
$f_{i}(X) = min_{Y \le X}(|a_{i} - Y|)$ when $i = 1$ ↵
↵
and ↵
↵
$f_{i}(X) = min_{Y \le 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 \ge 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) \le 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 $O(\log n)$ time). ↵
↵
Here's the implementation of this idea by [user:koosaga,2016-10-16] : [submission: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](https://github.com/apio-2016/apio2016-tasks/blob/master/fireworks/descriptions/en.pdf)↵
↵
This problem was the "killer" problem of APIO 2016, and was solved by merely $4$ contestants in the actual contest. ↵
↵
I'll explain the $O((N + M)\log^{2}(N + M)$ 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 \ge 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](http://codeforces.me/blog/entry/44351))↵
↵
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](https://github.com/apio-2016/apio2016-tasks/blob/master/fireworks/solutions/fireworks_seokhwan_nlg2n.cpp)↵
↵
Beyond APIO 2016 Fireworks↵
------------------↵
↵
Now, the next example is the generalization of this problem. It has came from [Codechef October Challenge — Tree Balancing](https://www.codechef.com/OCT16/problems/TREEBAL). 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} \le x \le 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](https://www.codechef.com/viewsolution/11786858) ↵
↵
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} \times 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)](https://www.codechef.com/viewsolution/11865552)↵
↵
That's it for this post. If you know any other application of this trick, feel free to post them in the comments.
