Slope Trick Optimization

A function $f:\mathbf Z\rightarrow\mathbf R\cup\{\pm\infty\}$ is convex if and only if

holds for every $x\in\mathbf Z$.

This proposition is a direct consequence of the slope characterization of convex functions.

If $f$ is convex on $\mathbf Z$, then the slopes are nondecreasing, so

This is exactly the condition above.

Conversely, if the condition above holds, then for any $x_1<x_2$,

This is the arithmetic mean of all differences satisfying $x_1\le i<x_2$. Increasing $x_2$ by one inserts a larger difference, while increasing $x_1$ by one removes a smallest difference. Both operations increase the mean. This shows that the slope $\Delta f(x_1,x_2)$ is nondecreasing, so $f$ is convex on $\mathbf Z$.

Let $S$ be $\mathbf R$ or a discrete subset of it. Then a function $f:S\rightarrow\mathbf R\cup\{\pm\infty\}$ is convex if and only if its slope

For every $x_1,x_2\in S$ with $x_1<x_2$, this slope is a nondecreasing function of $x_1$ and $x_2$.

For a function on $\mathbf R$, written $f(x)$, and for $x_1<x_2$, let $\alpha\in(0,1)$ and $x_3=\alpha x_1+(1-\alpha)x_2$. Then

is equivalent to

Both inequalities are equivalent to $f(x_3)\le\alpha f(x_1)+(1-\alpha)f(x_2)$, which is precisely the convexity of $f(x)$.

For a function on $\mathbf R$ restricted to a discrete subset $S$, written $f(x)$, the necessity of nondecreasing slopes follows from the convexity of $\tilde f(x)$. To prove sufficiency, it is enough to show that $\Delta\tilde f(x_1,x_2)$ is also nondecreasing. Let $S=\{s_i\}$ with $s_i$ strictly increasing in $i$, and suppose $s_{i_1}\le x_1\le s_{i_1+1}$ and $s_{i_2}\le x_2\le s_{i_2+1}$. Naturally, $i_1\le i_2$. Let $\Delta_i=\Delta f(s_i,s_{i+1})$. We can show that $\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}$.

There are two cases. If $i_1=i_2$, then $\Delta_{i_1}=\Delta\tilde f(x_1,x_2)=\Delta_{i_2}$, so the inequality is immediate. Otherwise,

Since the slopes on $S$ are increasing, $\Delta_i$ increases with $i$, and therefore $\Delta_{i_1}\le\Delta\tilde f(x_1,x_2)\le\Delta_{i_2}$.

Using this result, take $x_1<x_2$ and $\alpha\in(0,1)$, let $x_3=\alpha x_1+(1-\alpha)x_2$, and choose $i_3$ such that $s_{i_3}\le x_3\le s_{i_3+1}$. Then

Substituting the expression for $x_3$ gives the convexity of $\tilde f(x)$.

A function $f:\mathbf R\rightarrow\mathbf R\cup\{\pm\infty\}$ is convex if and only if $\operatorname{epi}f$ is a convex set in $\mathbf R^2$.

If $f$ is convex, then for $(x_1,y_1),(x_2,y_2)\in\operatorname{epi}f$ and any $\alpha\in(0,1)$,

Therefore, $\alpha(x_1,y_1)+(1-\alpha)(x_2,y_2)\in\operatorname{epi}f$.

Conversely, if $\operatorname{epi}f$ is convex, then for any $x_1<x_2$ and $\alpha\in(0,1)$,

This is equivalent to $\alpha f(x_1)+(1-\alpha)f(x_2)\ge f\left(\alpha x_1+(1-\alpha)x_2\right)$, which is the convexity of $f$.

Let $f,g$ be convex and let $h$ be their infimal convolution. Take $x_1<x_2$ and $\alpha\in(0,1)$. By the definition of infimal convolution, for any $\varepsilon>0$, there exist $y_i,z_i\in\mathbf R$ such that $y_i+z_i=x_i$ and

Combining this with the convexity of $f,g$ and the definition of $h$ gives

Since $\varepsilon>0$ is arbitrary,

This proves the convexity of $h$.

For the geometric statement, strictly speaking, we can prove only

Here $\operatorname{cl}$ denotes closure.

For any $(x,y)\in\operatorname{epi} f + \operatorname{epi} g$, there are $(x_1,y_1)\in\operatorname{epi} f$ and $(x_2,y_2)\in\operatorname{epi} g$ with $x=x_1+x_2$ and

Hence $(x,y)\in\operatorname{epi}h$, proving $\operatorname{epi} f + \operatorname{epi} g\subseteq \operatorname{epi}h$.

Conversely, for any $(x,y)\in\operatorname{epi}h$, we have $y\ge h(x)$. By the definition of $h$, for every $\varepsilon>0$ there are $x_1+x_2=x$ such that

Let $y_1=f(x_1)$ and $y_2=g(x_2)$, so $y+\varepsilon>y_1+y_2$. Thus, for every $\varepsilon>0$, a point $(x_1,y_1)+(x_2,y_2)\in\operatorname{epi} f + \operatorname{epi} g$ lies on the line segment joining $(x,y)$ and $(x,y+\varepsilon)$. Letting $\varepsilon\rightarrow 0$ yields $\operatorname{epi}h \subseteq \operatorname{cl}(\operatorname{epi} f + \operatorname{epi} g)$.

Therefore, $\operatorname{epi} f + \operatorname{epi} g = \operatorname{epi}h$ if and only if it is a closed convex set. One sufficient condition is that $f$ and $g$ are proper, convex, and lower semicontinuous. This is enough for algorithmic applications; piecewise-linear functions, for example, always satisfy these conditions.

First, $\{b_i\}$ being strictly increasing is equivalent to $\{b'_i\}=\{b_i-i\}$ being nondecreasing. Therefore, from $\{a'_i\}=\{a_i-i\}$ we can find a nondecreasing sequence $\{b'_i\}=\{b_i-i\}$ minimizing the difference, and then recover $\{b_i\}$.

Consider the naive DP solution. Let $f_i(x)$ be the minimum difference after selecting the first values of $\{b'_i\}$—there are $i$ of them—and requiring the $i$-th value to be no greater than $x$, compared with $\{a'_i\}$, taking its first $i$ values:

The state transition is readily obtained:

The initial state is $f_0(x)\equiv 0$, and the final answer is $\min_xf_n(x)$. Using the transformations of convex functions introduced above, transforming $f_{i-1}(x)$ into $f_i(x)$ requires two steps:

1. First, add $|a'_i-x|$. This increases all slope segments in $(-\infty,a'_i]$ by $-1$ and all slope segments in $[a'_i,+\infty)$ by $1$.
2. Take the minimum of the resulting function, changing $g(x)=f_{i-1}(x)+|a'_i-x|$ into $f_i(x)=\min_{y\le x}g(y)$. From the analysis above, this is equivalent to taking the infimal convolution of $g(x)$ and $0_{[0,+\infty)}$. The latter has only one slope segment, with slope $0$ extending infinitely to the right. Inserting it into the slope segments of $g(x)$ is equivalent to deleting all positive-slope segments.

Once these operations are clear, all slope segments can be maintained directly with a balanced tree, but the code is complicated. Notice that the slope changes by at most $1$ each time in this problem, so the absolute value of every slope is at most $n$. Instead of maintaining slope segments directly, it is more convenient to maintain the slope kinks.

Suppose the kink set of $f_{-1}(x)$ is $\xi_{-k}\le\cdots\le\xi_{-1}\le\xi_{1}\le\cdots\le\xi_{\ell}$. Then the two operations above correspond to:

1. Add a kink at $a'_i$ for a negative-slope segment and a kink at $a'_i$ for a positive-slope segment.
2. Pop the kinks $\xi_1,\cdots,\xi_{\ell}$ of all positive-slope segments.

In the actual maintenance, after each operation there are no kinks of positive-slope segments, so the slope kinks have the form $\xi_{-k}\le\cdots\le\xi_{-1}$. Moreover, the operations always occur at the boundary between positive- and negative-slope segments, so it is enough to maintain a max-heap containing all kinks. The two operations correspond to:

1. Insert $a'_i$ twice.
2. Pop the top of the heap.

Of course, the minimum value of the current function must also be maintained after each operation. Since there are no positive-slope kinks after an operation, the minimum is the value of the function at the top of the max-heap. Suppose the heap top before each operation is $\xi_{-1}$ and the minimum is $f_{i-1}(\xi_{-1})$. Because the popped top is the smallest kink of the positive-slope segments, the minimum equals the function value at that point. Thus, we can directly compute the function value at the heap top before popping, namely

The equality of the first terms follows because $f_{i-1}(x)$ has no positive-slope segments. Therefore, at each step we only need to repeatedly add $\max\{0,\xi_{-1}-a'_i\}$ to the minimum value.

This problem also asks us to output one optimal solution. At the end of the final operation, the optimal solution is the heap top, so the value of $b'_n$ can be determined directly. If the $i$-th optimal value $b'_i$ is known and we need an optimal solution of $f_{i-1}(x)$ satisfying $x\le b'$, note that because $f_{i-1}(x)$ is convex, the closer a point is to its global minimum point, the better the solution. Therefore, it is enough to record a global minimum point of $f_{i-1}(x)$ and take its minimum with $b'_i$ to obtain the optimal $b'_{i-1}$.

The time complexity is $O(n\log n)$.

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n), b(n);
  for (int& x : a) std::cin >> x;
  for (int i = 0; i < n; ++i) a[i] -= i;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int i = 0; i < n; ++i) {
    max_heap.emplace(a[i]);
    max_heap.emplace(a[i]);
    res += max_heap.top() - a[i];
    max_heap.pop();
    b[i] = max_heap.top();
  }
  std::cout << res << '\n';
  for (int i = n - 2; i >= 0; --i) b[i] = std::min(b[i], b[i + 1]);
  for (int i = 0; i < n; ++i)
    std::cout << (b[i] + i) << (i == n - 1 ? '\n' : ' ');
  return 0;
}

First consider the naive DP solution. Let $f_i(x)$ be the maximum profit after day $i$ when holding $x\ge 0$ shares:

The initial state is $f_0(0)=0$, and for every $x\neq 0$, $f_0(x)=-\infty$. The answer is $f_n(0)$.

Transforming $f_{i-1}(x)$ into $f_i(x)$ requires two steps:

1. Take the supremal convolution of $f_{i-1}(x)$ with the piecewise-linear function $\tilde h(x)$ corresponding to

   $$h_i(x) = \begin{cases}p_i,&x=-1,\\0,&x=0,\\-p_i,&x=1\end{cases}$$

   (which is clearly concave);

2. This gives the function finite values on $[-1,0)$, which conflicts with the requirement $x\ge 0$, so take only the part of the function on $[0,+\infty)$.

Translated into changes to slope segments, these are:

1. Insert a slope segment of length $2$ and slope $-p_i$;
2. Delete, among the slope segments with finite slope, the segment with the largest slope and length $1$.

Since the lengths of slope segments are always integers, we may maintain several slope segments of length one and record only the slope of each segment. Since we only need insertion and maximum queries, a max-heap is enough. The two operations are:

1. Insert $-p_i$ twice.
2. Pop the heap top.

We also need to maintain the value of $f_i(0)$. The function obtained after the first operation has value at $x=-1$ equal to $f_{i-1}(0)+p_i$, so its value at $x=0$ is that value plus the heap top that is about to be popped, which is the slope of the function on $[-1,0]$. Because truncation does not change the value at $x=0$, this is $f_i(0)$.

Comparing this implementation with the code for Minimum-Cost Increasing Sequence above shows that this algorithm is equivalent to finding the minimum cost of changing the stock prices into a nonincreasing sequence.

The time complexity is $O(n\log n)$.

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int& x : a) std::cin >> x;
  long long res = 0;
  std::priority_queue<int> max_heap;
  for (int x : a) {
    max_heap.emplace(-x);
    max_heap.emplace(-x);
    res += x + max_heap.top();
    max_heap.pop();
  }
  std::cout << res << '\n';
  return 0;
}

Consider the naive DP solution. Let $f_i(x)$ be the minimum cost after satisfying the demands of the first $i$ gardens, when a net surplus of $x$ units of soil is transported to later gardens. If $x<0$, this means that a net shortage of $|x|$ units must be transported from later gardens. Then the state transition can be written as

Here, $h(\delta)$ denotes the cost when the net amount of soil purchased for the current garden is $\delta$:

This is clearly convex. The meaning of the state transition is:

• When the net surplus of soil among the first $i-1$ gardens is $y$, the minimum cost is $f_{i-1}(y)$.
• The cost of transporting the net surplus (or shortage) between gardens $i$ and $i-1$ is $|y|Z$.
• By buying and selling, the amount of soil in garden $i$ is adjusted from $a_i$ to $b_i$, and the net surplus is adjusted from $y$ to $x$, at minimum cost $h((x-y)+(b_i-a_i))$.

The initial state is $f_0(0)=0$, and for every $x\neq 0$, $f_0(x)=+\infty$. The answer is $f_n(0)$.

Transforming $f_{i-1}(x)$ into $f_i(x)$ can be divided into three steps:

1. First, add $|x|Z$, obtaining $f_{i-1}(x)+|x|Z$.
2. Then take the infimal convolution with $h(x)$, obtaining $\min_{y\in\mathbf R}f_{i-1}(y)+|y|Z+h(x-y)$.
3. Finally, shift the function $(b_i-a_i)$ units to the left.

Converted into operations on slope segments, the three steps are:

1. Add $-Z$ to all slope segments left of the origin, and add $Z$ to all slope segments right of the origin.
2. Replace every slope segment smaller than $-Y$ by $-Y$, and every slope segment greater than $X$ by $X$.
3. Shift all slope segments $(b_i-a_i)$ units to the left.

In the original problem, $a_i$ and $b_i$ are small, so it is enough to maintain several slope segments of length $1$. Although there are infinitely many slope segments, their upper and lower bounds are $X$ and $-Y$, and there are only a few segments strictly between them. Since there are no insertion operations, two stacks can maintain the slope segments on the two sides of the origin, with interval additions and interval extrema handled by lazy tags. The three operations above correspond to:

1. Apply lazy tags to the two stacks, adding $-Z$ on the left and $Z$ on the right.
2. Whenever an element is popped from a stack, take its maximum with $-Y$ and its minimum with $X$. If the left stack is empty, pop $-Y$; if the right stack is empty, pop $X$.
3. Pop $(b_i-a_i)$ elements from the top of the left stack and insert them into the right stack; when $b_i-a_i<0$, do the reverse.

When swapping stack tops, update the answer: moving left subtracts the current slope, while moving right adds the current slope.

The algorithm has complexity $O(n\max\{a_i,b_i\})$.

#include <iostream>
#include <stack>

int main() {
  int n;
  long long x, y, z;
  std::cin >> n >> x >> y >> z;
  std::stack<long long> neg, pos;
  long long lt = 0, rt = 0;
  long long res = 0;
  for (; n; --n) {
    int a, b;
    std::cin >> a >> b;
    lt -= z;
    rt += z;
    for (; b < a; ++b) {
      auto l = -y;
      if (!neg.empty()) {
        l = std::max(l, neg.top() + lt);
        neg.pop();
      }
      pos.emplace(l - rt);
      res -= l;
    }
    for (; b > a; --b) {
      auto r = x;
      if (!pos.empty()) {
        r = std::min(r, pos.top() + rt);
        pos.pop();
      }
      neg.emplace(r - lt);
      res += r;
    }
  }
  std::cout << res << std::endl;
  return 0;
}