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

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