Kuroni's blog

By Kuroni, 10 months ago, In English

Special thanks to Ari for helping me proof-reading this blog :D

Hi everyone! Some years ago I read zscoder's tutorial on slope trick. Initially, I found the blog a bit difficult to understand, so I came up with a different explanation and system for my personal use. Today, I finally have the courage to share it with you guys. So without further ado, let's get started!

Formulation and properties

Slope trick is a way to represent a function. Here, I denote that a function is slope-trick-able (sorry for the lack of creativity) if the function satisfies 3 conditions:

  1. It is continuous.

  2. It can be divided into multiple sections, where each section is a linear function with an integer slope.

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

For example, the function $$$y = f(x) = |x|$$$ is a slope-trick-able function because it can be divided into two sections of linear functions with integer slopes ($$$y = -x$$$ for $$$x \in (-\infty, 0)$$$, and $$$y = x$$$ for $$$x \in [0, \infty)$$$), and the slope is non-decreasing going from left to right.

Let's define some other terms. I define a slope changing point to be the value $$$x_{change}$$$ such that when going from the left of $$$x_{change}$$$ to the right of $$$x_{change}$$$, the function changes its slope. Taking the example above, $$$x_{change} = 0$$$ is a slope changing point, the slope is $$$-1$$$ to the left of $$$x = 0$$$ and is $$$1$$$ to the right of $$$x = 0$$$. Note that a function can have multiple slope changing points. For example, this artificial function

$$$ y = g(x) = \begin{cases} 2 &\quad\text{when } x < 2\\ x &\quad\text{when } 2 \leq x < 8\\ 4x-24 &\quad\text{when } 8 \leq x\\ \end{cases} $$$

has $$$x = 2$$$ and $$$x = 8$$$ as slope changing points.

Let's come up with a way to represent this kind of function smoothly. I can represent this function by storing the linear function of the rightmost section, and the multiset $$$\text{S}$$$ all the slope changing points where the slope changes its value by $$$1$$$ (here I use the multiset with its mathematical definition, i.e. a set where we can repeat elements). This also means that if there is a slope changing point where the slope changes its value by more than $$$1$$$, we simply store that point as many times as the change in the slope value.

Using this, we see that the function $$$f(x) = |x|$$$ can be represented in slope trick language as $$$[y=x, \text{ S = {0, 0}}]$$$ ($$$x$$$ is the function of the rightmost function, and $$$0$$$ is stored twice because the slope increases by $$$2$$$ (from $$$-1$$$ to $$$1$$$). Likewise, the artificial function above can be represented as $$$[y=4x-24, \text{ S = {2, 8, 8, 8}}]$$$.

We note that just by storing these values, we can reconstruct every segment and therefore the whole function itself. Let's take the artificial function as an example. Using the multiset of slope changing point, we see that there are 3 sections $$$(-\infty, 2)$$$, $$$[2, 8)$$$, and $$$[8, \infty)$$$. The last section has the function of $$$y = 4x - 24$$$. The second-to-last section has the function of $$$y = x + b$$$ (because the slope changes by $$$3$$$ at $$$x = 8$$$), and we can solve $$$x + b = 4x - 24$$$ at $$$x = 8$$$ to yield $$$b = 0$$$, hence the second-to-last section has the function of $$$y = x$$$. Finally, the first section has the function of $$$y = c$$$ (the slope changes by $$$1$$$ at $$$x = 2$$$), and $$$c = x$$$ at $$$x = 2$$$ yields $$$c = 2$$$, therefore the function for the first section is $$$y = 2$$$.

Here comes the single most important property of slope-trick-able functions: they are mergable! In other words, if both $$$f(x)$$$ and $$$g(x)$$$ are slope-trick-able functions, then $$$h(x)=f(x)+g(x)$$$ is also a slope-trick-able function. Note that we only consider addition of the same type of slope-trick-able functions, i.e. both convex functions or concave functions. Even more beautifully, the slope trick representation of $$$h(x)$$$ is also easily deductable: the rightmost function is equals to the sum of two rightmost functions of $$$f(x)$$$ and $$$g(x)$$$, and the multiset $$$S_h = S_f \cup S_g$$$. To see how this union operation works, if you are familiar with how sweep line works, we can view the slope changing points as the event points where the slope changes, and so when adding two functions, we can simply union all the event points together.

Now we are done with all the definitions, let's get this new knowledge to work! As we will see in the next few examples, the essence of slope trick lies in the flexibility of transforming our functions just from modifying the slope changing points and the rightmost function.

713C - Sonya and Problem Wihtout a Legend

TL;DR: You are given an array, each operation you are allowed to increase or decrease an element's value by $$$1$$$. Find the minimum number of operations to make the array strictly increasing.

We first need to transform this problem a bit by changing the condition from strictly increasing to non-decreasing. To do that, simply do a[i] -= i for all elements.

Let's denote the function $$$f_i(x)$$$ to be the mininum number of operations to make the first $$$i$$$ elements of the array non-decreasing, with the condition that $$$a_i \leq x$$$. We see that the answer to our problem is simply $$$f_n(\infty)$$$. Here, I will prove that $$$f_i(x)$$$ is a convex slope-trick-able function for all $$$i$$$ using induction.

Firstly, we see that $$$f_0(x)$$$ is a convex slope-trick-able function, it is simply $$$f_0(x) = 0$$$.

Let's suppose $$$f_{i - 1}(x)$$$ is a convex slope-trick-able function. Denote $$$g_i(x)$$$ to be the mininum number of operations to make the first $$$i$$$ elements of the array non-decreasing, with the condition that $$$a_i = x$$$ (note that $$$g_i(x)$$$ is almost similar to $$$f_i(x)$$$, but with $$$=$$$ instead of $$$\leq$$$ condition for $$$a_i$$$). We can see that $$$g_i(x) = f_{i - 1}(x) + |x - a_i|$$$. Since $$$|x - a_i|$$$ is a convex slope-trick-able function (similar to the first example function), and $$$f_{i - 1}(x)$$$ is a convex slope-trick-able function due to our induction hypothesis, $$$g_i(x)$$$ is also convex slope-trick-able.

Now comes to our finale: We observe that $$$f_i(x)$$$ is a prefix-min function to $$$g_i(x)$$$ (i.e. $$$f_i(x) = \min(g_i(t), \forall t \leq x)$$$). We see that for a convex slope-trick-able function, its value is non-increasing up until the point where the slope becomes $$$1$$$, and non-decreasing from that point on. So, in order to make $$$f_i(x)$$$, we simply "cut" $$$g_i(x)$$$ at the point where the slope becomes $$$1$$$, and "extend" that point rightward. I give you this absolutely amazing doodle to demonstrate what I've just said:

Since the "cut" and "extend" operation is simply simultaneously removing the largest slope changing point along with modifying the rightmost function until the slope of the rightmost function becomes $$$0$$$, $$$f_i(x)$$$ is also a convex slope-trick-able function. Additionally, you can inductively prove that the slope of the rightmost function of $$$g_i(x)$$$ is $$$1$$$, and therefore we only have to remove the largest slope changing point of $$$g_i(x)$$$ to obtain $$$f_i(x)$$$.

Therefore, we can continously maintain $$$f_i(x)$$$ with increasing $$$i$$$, using a priority_queue as the data structure backing our slope changing multiset, and simply output $$$f_n(\infty)$$$ as our answer. The complexity is $$$O(n \log n)$$$.

Singapore NOI 2018 — Task 5

TL;DR: You are given an array of $$$n$$$ non-negative integers, each operation you are allowed to increase or decrease an element's value by $$$1$$$ (you must keep all elements non-negative at all times). Find the minimum number of operations to make the array satisfy $$$|a_i - a_{i + 1}| \leq h$$$ for $$$1 \leq i < n$$$, where $$$h$$$ is a given value.

We first observe that the restriction to keep all elements non-negative is unnecessary, because in an optimal construction, we would never have a negative element in the array (we can simply make the negative elements equal to $$$0$$$ to use less operations and still satisfy the condition).

We denote $$$f_i(x)$$$ to be the minimum number of operations to make the first $$$i$$$ elements satisfiable, while ensuring that $$$a_i = x$$$. We will once again prove that this function is convex slope-trick-able for all $$$i$$$.

It is easy to see that $$$f_1(x) = |a_1 - x|$$$, and therefore $$$f_1(x)$$$ is convex slope-trick-able.

Suppose $$$f_{i - 1}(x)$$$ is convex slope-trick-able. Denote $$$g_i(x)$$$ as the minimum number of operations to make the first $$$i$$$ elements satisfiable, with $$$|a_i - x| \leq h$$$. We see that $$$g_i(x)$$$ is some sort of a "local-minimum" function of $$$f_i(x)$$$, where $$$g_i(x) = \min(f_i(t), |t - x| \leq h)$$$. Let's transform $$$f_{i - 1}$$$ into $$$g_{i - 1}$$$. Here, let's focus on three parts: the section where the slope is 0, the left of that section, and the right of that section.

  1. The section where the slope is 0 remains the same, because as we have stated in the previous problem, this section contains the minimum value of $$$f_{i - 1}$$$.
  2. The part to the left of the 0-section "shifts" to the left by $$$h$$$. That is because this left part is non-increasing, therefore $$$g_{i - 1}(x)$$$ will always try to take the minimum value of $$$f_{i - 1}(t)$$$ where $$$x \leq t \leq x + h$$$.
  3. The part to the right of the 0-section "shifts" to the right by $$$h$$$. Same explanation.

Again, an amazing doodle:

Here, we can maintain the slope changing points by subtracting every slope changing points up until the 0-section by $$$h$$$, and adding $$$h$$$ to every other slope changing points (we need to also recalculate the rightmost function). Therefore, $$$g_{i - 1}(x)$$$ is convex slope-trick-able. Finally, we see that $$$f_i(x) = g_{i - 1}(x) + |a_i - x|$$$, and therefore $$$f_i(x)$$$ is convex slope-trick-able.

A sidenote when implementing, we can use 2 priority_queue's to maintain the slope changing points of our left and right part, and rather than maintaining the rightmost function, we can maintain the function of the minimum section itself. Complexity is $$$O(n \log n)$$$.

 
 
 
 
  • Vote: I like it
  • +465
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).

»
10 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Hey.

In other words, if both $$$f(x)$$$ and $$$g(x)$$$ are slope-trick-able functions, then $$$h(x)=f(x)+g(x)$$$ is also a slope-trick-able function.

I'm having trouble understanding the "why" behind this. Could you help with some intuition? The next sentence mentions that the multisets can be merged to obtain the slope-trick-able representation of h(x). It's linear merging time, right?

EDIT: Nevermind, explained it to myself using an example and a graphing calculator.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I hope this helps. For the second question, yes it is linear.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      It's not very precise to say that slope-trick-able functions have to be, among other conditions, convex or concave, and then say that slope-trick-able function class is closed on addition.

      The convex slope-trick-able functions are, and the concave ones are too, but adding a convex and concave one doesn't necessarily produce one, too. For example $$$|x| + (-|x-2|)$$$ is not slope-trick-able.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        That's true, I suppose I should have clarified that we should only work with either convex or concave functions and not both.

»
10 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Thank you for the amazing tutorial!

»
10 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Very well-written and helpful. And the absolutely amazing doodles are just icing on the cake. Thanks Kuroni!

»
10 months ago, # |
  Vote: I like it +27 Vote: I do not like it

I know this as a piecewise linear function. Well, a convex piecewise linear function.

»
10 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Good work! Some suggestions:

  1. It would be good to explain very clearly what the slope trick actually is. You have definitions and observations, but it is difficult to understand what the trick is.

  2. Both the example problems are quite complex. Is there a simpler problem that a) can be solved using the slope trick and b) shows what is the essence of the trick?

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Thanks for the feedback :D I will edit this into the main blog later, but the essence of slope trick is to maintain and edit the function by working around the slope changing points. I call this slope "trick" because zs deemed the term in his tutorial; in Vietnam we just call this method "function merging".

    As for examples, I think 713C is the simplest problem to demonstrate the method already. The modification to the slope multiset is pretty simple (popping the largest element in the multiset). There is indeed a really simple theoretical example: given an integer array, each operation increase/decrease 1 to one element, find the minimum number of operations to make all elements equal. We can apply slope trick directly to proof that we should use the median to converge all elements, but I didn't include this example because 1) it is very theoretical 2) it doesn't involve working around with the slope multiset at all.

    EDIT: When I think about it, slope trick can probably be classified as a dp optimization when the dp function is slope-trick-able, and we are restricted with the addition operation.

»
10 months ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

I think the difficulty in the slope trick is not how to handle the hulls, but how to figure out that this encoding make sense in the task at hand. In essence, I think the hard part is looking at the problem and figuring out at each step the dp is a convex piecewise linear function in the second argument, and the transitions modify the function in such a subtle way. And I think some would agree that "proof by induction" seems in this case as a cheater's proof, as one has to make the educated guess of this form beforehand and then argue that it's correct.

I think a more interesting proof might come from LP: in essence, one could take the problem 713C, formulate it as a linear program with $$$2n$$$ variables and $$$2n$$$ constraints, construct its dual (which, after some paperwork, sounds like):

$$$max \sum_{i = 1}^{n}{c_i y_i}$$$

$$$s.t. -1 \leq y_i \leq 1, \sum_{j = i}^{n}{y_j} \leq 0$$$

(it's a good exercise to try to dualize it yourself, although not trivial and rather time-consuming).

In the above LP, you could argue that the solutions should be integer, and the "slope trick" greedy becomes more apparent, and formulating an LP and analyzing its dual seems less far-fetched to me than looking at slopes. Although, in some sense, you could think of dualization as some generatization of slope trick, because I think it has something in common with the idea of transitioning to a space generated by $$$(slope, intercept)$$$, but I know far too little math to prove that.

Again, it's not an elegant proof, but it's something that someone could come up with without some divine inspiration.

By the way, the problem can be solved in $$$O(n log^2(n))$$$ and probably even in $$$O(n log(n))$$$ with a greedy and some mergeable median heaps.

https://codeforces.com/contest/713/submission/80008205

Edit: The above solution is especially cool because it provides a trivial solution reconstruction method, whereas slope trick doesn't (not trivial).

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Amazing :)

»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

The truth is, I do not understand both zscoder's and your explanation.

Firstly, how does a[i] -= i change 713C from strictly increasing to non-decreasing. Applying a[i] -= i to [2 1 5 11 5 9 11] yields [2 0 3 8 1 4 5] and it is not apparent how this has changed the problem statement or how it helps solve the problem. Having a good understanding of your post will also help developers understand what to do when the problem statement changes from strictly increasing to something like strictly decreasing, non-increasing, non-decreasing and other flavors.

I also think that using a concrete example will help developers especially those not too experienced to understand all the confusing mathematical equations.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    $$$a[i] < a[i + 1] \rightarrow a[i] - i \leq a[i + 1] - (i + 1)$$$

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone plz explain how we maintain f(x) for different i and x's for the 1st example. If you can share code that will be much helpful.