PrevNext
Not Frequent
 0/11

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 on some range such that for any two functions and , there exists some such that

  • For all ,
  • For all ,

Answer queries of the form "what is the maximum/minimum for some given ," given that we have a way of finding efficiently.

A sufficient (but not necessary) set of conditions:

  • All the functions are continuous along the range .
  • No two functions intersect at more than one point.

The most common case is where each is of the form . Given two lines and such that , their intersection point at can be found in time. Then it's clear that

  • For all , .
  • For all , .

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

Some possible nonlinear forms of :

    • Reduces to the linear case, since we can ignore the term when comparing two functions.
    • If this function is defined for all .
    • Note that when , is strictly decreasing over the range .

In this module, we'll focus on the special case of CHT where "slopes" of functions are monotonic. This specific case is solvable in using a std::deque in C++. For the more general 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 -coordinate and get the following DP recurrence:

Notice how the part of the recurrence describes a straight line .

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 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];

Problems

Alternative Solution

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

StatusSourceProblem NameDifficultyTagsSolutionURL
APIOEasy
Show Tags

DP, convex

External Sol
CEOIEasy
Show Tags

DP, convex

View Solution
CEOINormal
Show Tags

DP, convex

External Sol
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:

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!

Give Us Feedback on Convex Hull Trick!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext