# Convex hulls of lines
This blog is the third blog in a series of blogs about line containers.
Links:
- 1: [Data structure: add line, query max](https://hackmd.io/I4227EHWRuO16T9odRgZWw)
- 2: [Slope trick](https://hackmd.io/K7t3ly9USMWT8BFLr-GjlQ)
- 3: Convex hulls (this blog)
This blog will focus on using convex hulls where we don't support arbitrary inserts, but instead build them from scratch, which makes it easier to code more operations. Then, we combine this with divide and conquer to get a decent complexity.
## Building convex hull in $O(N\log(N))$
We will define the following general operation: given a set of lines, construct its upper convex hull. Using this, we can then easily define other useful operations on upper convex hulls.
(Image stolen from https://codeforces.com/blog/entry/63823)
The idea is as follows: we will first sort the lines by slope in ascending order. Then, we will process the lines in this order and add them to the current hull. When we add a new line, it is definitely part of the hull, as its slope is larger than all current lines, and will eventually be better. However, some of the current lines might become completely covered by the new line.
Suppose that these lines make up the current convex hull.
Then, if we add the line y=4, then the blue line will become completely dominated, so we should remove it.
If the line added was instead y=1, then we should not remove it
How should we distinguish between these cases? The easiest way is to compare the blue and red intersections.
I encourage you to think for yourself what it means for the blue intersection to come first, as that helps build intuition. And that's it! Just keep popping some suffix of lines while they are dominated by the new line, and then add it.
Some small details to take care of: we need to special-handle parallel lines. But this can be done quite easily, as in that case, we pop the back of the hull if its $m$ is smaller, otherwise we do nothing. Also, how do we safely compare intersections? In some problems, lines can have slopes up to $10^{18}$, so we need to be careful. The best way to do it is to write out the inequality algebraically, then cross-multiply the divisions. Finally, use 128-bit integers, since we will probably overflow otherwise.
```c++
struct Line {
ll k, m; // y = kx + m
bool operator<(const Line& o) const {
return k < o.k;
}
};
struct UpperHull {
vector<Line> hull;
bool intersection_geq(const Line& A, const Line& B, const Line& C) {
auto left = (__int128)(B.m - A.m) * (A.k - C.k);
auto right = (__int128)(C.m - A.m) * (A.k - B.k);
return left >= right;
}
void push_back(Line& l) {
if (sz(hull)) assert(l.k >= hull.back().k);
if (sz(hull) && hull.back().k == l.k) {
if (hull.back().m >= l.m) return;
hull.pop_back();
}
while (sz(hull) >= 2 && intersection_geq(hull[sz(hull) - 2], hull.back(), l)) {
hull.pop_back();
}
hull.push_back(l);
}
UpperHull(const vector<Line>& a) {
sort(all(a));
for (auto l : a) {
push_back(l);
}
}
};
```
This implementation will find the set of lines that are optimal in some interval. However, it's not very useful as-is. Let's see how to extend it.
## Eval at point
One of the most useful operations is to evaluate the hull at a point. Because we maintain an upper hull, this is equivalent to "given a set of lines, which attains the largest value at point x?".
Because there is only one line for each point (not completely true, but true enough), we only need to be able to efficiently find the correct line and then evaluate it. The way we will do this is that each line stores the intersection with the line to the right of it. Then, we can binary search for the correct line.
An implementation can be found [here](https://gist.github.com/Matistjati/1497635256724b782cbc96aa166607cc). Currently untested. Note that the implementation uses some pretty tricky math tricks to use long longs. If you need to implement this during a contest with no prewritten material, just spam long double.
## Min hull
If you want a min-hull instead, just negate everything.
## Max of two hulls
Suppose that each hull is a function $y(x)$. Then, the max operation is defined as follows: given two hulls $f$ and $g$, create a new function, where $h(x)=max(f(x),g(x))$ for all $x$. This operation is quite simple: simply throw all the lines into a common vector and call the constructor.
## Problem: [Ruler of Everything](https://open.kattis.com/problems/rulerofeverything)
Let's solve a problem with our current knowledge. First, let's split all videos based on whether $a=1$ or $a>1$. Let's call the videos with $a>1$ heavy videos, and the others light videos.
### Lemma 1
Suppose we release some light videos, and the rest heavy. Then, it's optimal to release all light videos first.
### Lemma 2
Among the light videos, we will take them in decreasing order of $B$.
### Lemma 3
The smallest number of light videos needed is binary searchable. We do this by defining the function "$f(x)=$ if we start with $x$ subscribers from light videos, how many heavy videos do we need?". $f(x)$ can be computed quickly, which we will get to later.
### Lemma 4
$f(x) \leq \log_2(8 \cdot 10^9)$, or it is infinite (we don't have enough heavy videos). This holds, because for every heavy video, we at least double our subscriber count.
From these, we can solve the problem. Binary search for the smallest amount of light videos needed. Then, we only need to consider taking $\log_2(8 \cdot 10^9)$ more light videos, due to lemma 3. Let $l$ be the smallest number of light videos needed. Then, this amount gives us $l+f(l)$ videos in total. This means that, because $f(x)$ is bounded, any value larger than $l+\log_2(8 \cdot 10^9)$ must be suboptimal.
Now, how do we compute $f(x)$? To do this, let's define the DP
$$
DP[i][k][s] =
$$
max subscribers if we start with $s$ subscribers, use $k$ videos and have considered the first $i$ videos.
One crucial detail is that we can sort the heavy videos in a particular order, which is optimal.
This DP can be computed in a knapsack-like manner. It might seem hopelessly slow, since $s$ might be huge. However, it can be shown that $DP[i][k]$ is the upper hull of a bunch of lines. Let's write out the transitions. From $DP[i][k][s]$, we can either go to
$DP[i+1][k][s]$
or
$DP[i+1][k+1][s*a[i]+b[i]]$
And we of course combine these using max. So basically, we start with the line $y=x$, and then repeatedly perform an affine transform on it and take max. This preserves that we are working with an upper hull.
The driver code will look as follows:
```c++
read input
...
sort(all(heavy_videos), [](p2 a, p2 b)
{
return (a.second) * (b.first - 1) > b.second * (a.first - 1);
});
vector<Line> default_hull = { Line{ 1,0,0 } };
vector<UpperHull> dp(38, UpperHull(default_hull));
rep(i, sz(vids))
{
for (int j = 36; j > 0; j--)
{
UpperHull c = fn[j - 1];
// take c = c*k+m
c = UpperHull::affine_transform(c, vids[i].first, vids[i].second);
fn[j] = UpperHull::max(fn[j], c);
}
}
```
This is correct, but a little slow. The time complexity is a little unclear, but probably exponential. However, there's a nice idea to speed it up: if any positive slope (all are positive) for a particular $k$ has $m \geq 8 \cdot 10^9$, then we don't need to add any more lines, because any amount of starting subscribers will suffice. From here, the best bound I know of is something like $\sqrt{b}$ lines per $k$. However, it behaves more like $\log$ in practice. I have not dug too deep into why.
[Implementation](https://gist.github.com/Matistjati/b7a8d57ac17f392398c0854f32384974).
## Minkowski sum/max plus convolution
This is the powerful operation. Given two hulls $f$ and $g$, it computes a new hull $h$, where $h(x)=\max\limits_{i+j=x}{f(i)+g(j)}$.
One way to think of it is that it merges two knapsacks.
I will not explain the correctness of this implementation
```c++
static UpperHull minkowskiSum(const UpperHull& l, const UpperHull& r) {
auto& A = l.hull;
auto& B = r.hull;
int i = 0, j = 0;
vector<Line> merged;
while (i < sz(A) && j < sz(B)) {
merged.push_back(A[i] + B[j]);
ll x1 = (i + 1 < sz(A) ? A[i].xRight : LLONG_MAX);
ll x2 = (j + 1 < sz(B) ? B[j].xRight : LLONG_MAX);
if (x1 < x2) ++i;
else if (x2 < x1) ++j;
else { ++i; ++j; }
}
while (i < sz(A)) merged.push_back(A[i++] + B.back());
while (j < sz(B)) merged.push_back(A.back() + B[j++]);
return { merged };
}
```
This can be thought of kind of as a merge sort. The important bit is that it runs in $O(N)$. It's kind of nontrivial and I don't have the intuition to offer a better explanation than ChatGPT would.
## Problem: Subtask 3 of [Mildly Inconvenient Array Problem](https://po2punkt0.kattis.com/problems/inconvenientarray)
The problem is as follows. You are given an array with $N$ integers, potentially negative, and need to support $Q$ queries
- Query: take the subarray (interval) with largest sum and print it
- Update: add $+x$ to every element in the array
We can realize that the value of some interval is a linear function in the sum of $x$: we increase the interval's value by the sum of $x$ times its length. The $m$ is then simply the original sum of it. Because intervals have slope up to $N$, the solution is to compute for each slope the best $m$. However, doing it in this way is nontrivial.
Instead, let's do a divide and conquer. For each $l$ and $r$, we will compute the best interval that crosses the midpoint, or is a suffix or prefix of the interval. Note that doing this divide-and-conquer style, we consider all lines. At every step, just throw all found lines into a giant global upper hull. Now, how do we compute the best line that crosses the midpoint? We have to consider every pair of left suffix with each right prefix.
Doing this naively is of course $O(N^2)$. Let's look at the code for combining the sides.
```c++
vector<Line> combined;
for (auto line1 : leftside) {
for (auto line2 : rightside) {
combined.push_back(line1 + line2);
}
}
```
This is precisely a minkowski sum or max plus convolution. Since we know how to do it in $O(N)$, we get
$$T(N)=2T(N/2)+O(N\log(N))$$
With the solution $O(N\log(N)^2)$. The log factor comes from sorting. The solution can be optimized to $O(N\log{N})$ quite easily in this case; we never really need to sort. In general, similar performance gains can be obtained by never sorting, and instead merging hulls in a merge-sort style.
[Implementation](https://gist.github.com/Matistjati/3c9a0e311d100ed3d0e2eecbac047102).
## Problem: [titanomachy](https://codeforces.com/problemset/gymProblem/105677/A) or subtask 4 of of [Mildly Inconvenient Array Problem](https://po2punkt0.kattis.com/problems/inconvenientarray)
This is the same as the previous problem, but now we have range queries. To solve it, we will use a very similar solution, by having a segment tree. Each node stores the line if the whole node is taken, and convex hulls for the best prefix, best suffix and best line within the node. To answer queries, query the $log$ segtree nodes covering our interval. Then, try every interval of nodes (best suffix + fixed inbetween + best prefix).
[implementation](https://gist.github.com/Matistjati/3942eba3f5994f731cad7a8e3cd5cb54).
## Problem: titanomachy on tree
One way to generalize titanomachy is that we get path queries on a tree. To solve this, just do the previous solution with HLD. To avoid three log factors, do everything offline.
## Problem: best path on tree
Suppose that we are instead asked of the globally best path in the tree. Equivalently, we are given a tree where each edge has some weights. We then get queries:
- Query: print the diameter of the tree
- Update: add a constant to all edges
This may be seen most naturally as a generalization of the max subarray with updates problem. How do we extend divide and conquer to trees? Centroid decomposition! For each centroid, gather all lines in the centroid subtree. Then, do another divide and conquer to compute all ways to combine lines from distinct subtrees (we don't want to allow using the same path twice).
[Implementation](https://gist.github.com/Matistjati/b8da7fd7d7d507d7798afe7ede2fc6d4)
The other way is using smaller-to-larger merging. We "obviously" can't do this by storing an explicit hull of lines.
Sign in with Wallet
Connect another wallet