Convex hull trick

To check all the catalogue's solutions, the sandbox runs 1776 tests in a row, one process per test. Starting the sandbox has its own cost: an empty program takes 65–150 ms from request to answer. You can run each test separately and pay for a start 1776 times, or run everything at once and wait for the first verdict until the very end. Best of all is to split the tests into batches: with a start cost of 80 ms the best is 41 runs, and a verdict arrives after 44 seconds on average, against 113 with a run per test and 81 with a single run for everything. Such a split is found by dynamic programming, and to make it run in linear rather than quadratic time, one geometric trick is needed.

The cheaper a start, the more batches: 102 at 10 ms, 12 at a second. The first batches are large, the last small: verdicts at the end of the queue wait for everyone before them anyway, while a batch at the start delays everyone after it.

The idea

Let T_i be the total time of the first i tests and S the cost of a start. A batch of tests j + 1 … i lasts S + T_i − T_j and delays the verdicts of all tests after j, of which there are n − j. So the sum of waits adds up batch by batch, and the best split of the first i tests is

best[i] = min_{j < i} ( best[j] + (S + T_i − T_j) · (n − j) ).

Trying every j takes n²/2 steps. But for a fixed j the expression is a line in x = T_i: slope n − j, intercept best[j] + (S − T_j) · (n − j). So best[i] is the value of the lower envelope of all lines j < i at the point T_i.

If a DP transition is a minimum of expressions “k_j · x_i + b_j”, each j is a line, and what is needed is the minimum of lines at a point. The envelope is a convex polyline, and lines that lie on it nowhere can be thrown away for good. If slopes arrive in decreasing order and points in increasing order, the envelope lives in a deque: each line enters once and leaves once.

Watch the deque step by step. Here are 13 tests of one problem; at each step a new line arrives at the end of the deque, with the smallest slope, and lines it has made unnecessary leave from the back. Then the query point moves right, and lines that are no longer the best at it leave from the front.

Why the deque is right

Let x(u, v) be the abscissa of the intersection of lines u and v.

Each line is added once and removed at most once, so the whole DP is O(n). For batches of tests this holds by itself: the slope n − j decreases with j, and T_i grows with i.

The Li Chao tree: when there is no order

If slopes arrive in arbitrary order or queries jump about, the deque will not do. A Li Chao tree is built over the range of possible x, like a segment tree. Each node keeps one line, the one that is lower at the middle of its range. A new line is compared with the stored one at the middle: the winner stays, and the loser goes down into one half, the one where it can still win. A query at a point x goes from the root to a leaf and takes the minimum of the lines on the way.

Insertion and query are O(log C), where C is the number of possible x. The tree is also good when the lines cannot be ordered in advance: for example, when they arrive mixed with queries.

Code

The search over j is kept in the listing as a check: on 1776 tests it is still fast. The deque keeps lines with their numbers j to restore the batches; a line is added before the query, because j = i − 1 is an allowed last cut.

What it costs

The measurement is the same problem on queues of length n: the times of the catalogue's tests repeated in a cycle, with a start cost of 80 ms.

At two thousand tests the search in Python is already more than a hundred times slower than the deque, in Go at sixteen thousand a thousand times; the deque processes a million tests in Go in 17 milliseconds.

Easy mistakes

• Overflow in the comparison. The check “is the line redundant” multiplies a difference of intercepts by a difference of slopes. In batches of tests neighbouring slopes differ by one, and on the tests of the article's problem the products are at most 2.4 · 10¹². But if slopes and points are numbers up to 10⁹, the product goes beyond 64 bits, and 128-bit numbers or a comparison of fractions are needed.
• Equal slopes. Of two parallel lines the higher one is redundant; the formula with intersections divides by zero on them.
• The order of steps. Line j = i − 1 must get into the deque before query i, otherwise a batch of just the last test is not considered.
• Leaving from the front with non-monotone queries. If query points do not increase, a line removed from the front may be needed again. Then binary search over the deque or a Li Chao tree is needed.
• The wrong envelope. For a maximum the upper envelope is needed: slopes and inequalities swap.

Where it is used

Batches with a setup cost: in scheduling and when grouping requests to a slow service. DP with a quadratic transition cost: (h_i − h_j)² expands into h_i² − 2h_jh_i + h_j², which is again a line in h_i. Without any DP, the envelope of lines answers which of the “fee + price per unit” plans is cheaper for a given usage, and who is ahead at time t if everyone moves at a constant speed. And if a transition does not split into lines but the best j is monotone, Knuth's and divide-and-conquer optimisations help.

History

The problem of splitting jobs into batches with a setup cost is a classic of scheduling theory. At the International Olympiad in Informatics in 2002 it was given to school students, and since then the trick with a deque of lines has become a competition classic. The Li Chao tree came from competitive programming and bears its author's name; its value is that it requires no order at all, from either the lines or the queries.

Problems

Batches of tests, exactly the problem from the article, but on hundreds of thousands of tests. And plans that appear mixed with the question “how much will I pay at usage x”, for the Li Chao tree.