Not Frequent

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)\mathcal{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)\mathcal{O}(N) using a std::deque in C++. For the more general O(NlogN)\mathcal{O}(N \log N) CHT (which involves a std::set), see the LineContainer module.

Focus Problem – read through this problem before continuing!


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)\mathcal{O}(N) time! Here is my implementation:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Rect {
ll x, y, a;
bool operator<(Rect B) { return x < B.x; }
Rect a[1000001];


Alternative Solution

Some of these problems can also be solved using divide & conquer.

StatusSourceProblem NameDifficultyTags
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex, DP
Show TagsConvex
Show TagsConvex, DP

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!