PrevNext
Not Frequent
 0/10

Convex Hull Trick

Author: Andi Qu

A way to find the maximum or minimum value of several convex functions at given points.

We wish to solve problems that are of the following form:

Consider a set of functions {fi(x)}\{f_i(x)\} on some range [l,r][l,r] such that for any two functions fif_i and fjf_j, there exists some mm such that

  • For all x[l,m]x \in [l,m], fi(x)fj(x)f_i(x)\le f_j(x)
  • For all x[m,r]x \in [m,r], fi(x)fj(x)f_i(x)\ge f_j(x)

Answer queries of the form "what is the maximum/minimum fi(x)f_i(x) for some given x[l,r]x\in [l,r]," given that we have a way of finding mm efficiently.

A sufficient (but not necessary) set of conditions:

  • All the functions are continuous along the range [l,r][l,r].
  • No two functions intersect at more than one point.

The most common case is where each fi(x)f_i(x) is of the form aix+bia_ix+b_i. Given two lines fi(x)=aix+bif_i(x)=a_ix+b_i and fj(x)=ajx+bjf_j(x)=a_jx+b_j such that ai<aja_i<a_j, their intersection point at m=bibjajaim=\frac{b_i-b_j}{a_j-a_i} can be found in O(1)O(1) time. Then it's clear that

  • For all xmx\le m, fi(x)fj(x)f_i(x)\ge f_j(x).
  • For all xmx\ge m, fi(x)fj(x)f_i(x)\le f_j(x).

The linear case is known as the convex hull trick because maxi(fi(x))\max_i(f_i(x)) as a function of xx is concave up (similarly, mini(fi(x))\min_i(f_i(x)) as a function of xx is concave down). Check the images from the CF tutorial below if you don't know what this means.

Some possible nonlinear forms of fi(x)f_i(x):

  • fi(x)=x2+aix+bif_i(x)=x^2+a_ix+b_i
    • Reduces to the linear case, since we can ignore the x2x^2 term when comparing two functions.
  • fi(x)=xai+bif_i(x) = \sqrt{x - a_i} + b_i
    • If this function is defined for all x[l,r]x\in [l,r].
    • Note that when ai<aja_i<a_j, xaixaj\sqrt{x-a_i}-\sqrt{x-a_j} is strictly decreasing over the range x[aj,)x\in [a_j,\infty).

In this module, we'll focus on the special case of CHT where "slopes" of functions are monotonic. This specific case is solvable in O(N)O(N) using a std::deque in C++. For the more general O(NlogN)O(N \log N) CHT (which involves a std::set), see the LineContainer module.

Focus Problem – read through this problem before continuing!

Tutorial

Solution - The Fair Nut and Rectangles

I won't analyse this problem in great detail since the Codeforces blog in the resources already does so, but essentially, we sort the rectangles by xx-coordinate and get the following DP recurrence:

dp[i]=piqiai+maxj<i(pjqi+dp[j])dp[i] = p_i \cdot q_i - a_i + \max_{j < i}(-p_j \cdot q_i + dp[j])

Notice how the pjqi+dp[j]-p_j \cdot q_i + dp[j] part of the recurrence describes a straight line y=mx+cy = mx + c.

Since we sorted the rectangles and no two rectangles are nested, the slopes of the lines we insert are strictly increasing. The query positions are also strictly increasing.

This means we can solve this problem using CHT in O(N)O(N) time! Here is my implementation:

1#include <bits/stdc++.h>
2typedef long long ll;
3using namespace std;
4
5struct Rect {
6 ll x, y, a;
7 bool operator<(Rect B) { return x < B.x; }
8};
9
10Rect a[1000001];

Problems

StatusSourceProblem NameDifficultyTagsSolution
APIOEasy
Show Tags

DP, convex

External Sol
CEOIEasy
Show Tags

DP, convex

View Solution
IOINormal
Show Tags

DP, convex

External Sol
APIONormal
Show Tags

DP, convex

POINormal
Show Tags

DP, convex

POINormal
Show Tags

DP, convex

View Solution
PlatNormal
Show Tags

DP, convex

PlatNormal
Show Tags

convex

External Sol
JOIHard
Show Tags

DP, convex

View Solution

Module Progress:

Give Us Feedback on Convex Hull Trick!

PrevNext