Skip to Content
ReferenceLibrary

dp

O(1) per evaluation.

Generated from spec/std/dp.cp by cpl doc --format json.

Line

pub struct Line(k: Int, m: Int)

O(1) per evaluation. The line k * x + m, the usual entry of a LiChao.

Source

Line.at

fn at(self, x: Int) -> Int

Evaluate the line at x: k * x + m.

  • cost: O(1)
  • traps: when k * x + m overflows Int

Examples:

  • Line(2, 3).at(4) == 11

Source

LiChao

pub struct LiChao<L = Line, K = Int>(pick: (K, K) -> K, lo: Int, hi: Int)

O(log n) per at, O(log n) per whole-line add, O(log^2 n) on a segment. The lower (LiChao(min, over: 0..=1e9)) or upper (max) envelope of lines over the integer coordinates over. A line is anything with at(self, x: Int) -> K, so a struct whose at returns (cost, used) breaks ties by its second field with the same tree. Law: two lines cross at most once on xs. add is O(log n) for a whole line and O(log^2 n) on a segment (on: lo..=hi), at and line_at O(log n), for n = xs.len; memory is O(lines) cells, allocated as lines arrive.

Source

LiChao.new

fn new(pick: (K, K) -> K, over: Range<Int>) -> LiChao<L, K>

An empty envelope over the integer coordinates over, keeping at each x the value pick prefers (min for the lower envelope, max for the upper). No cell is allocated until a line arrives.

over may be written half-open (0..n) or closed (0..=hi); the coordinates are its points.

  • cost: O(1)
  • empty: an empty over traps
  • order: no sequence is returned; coordinates run in over's order
  • traps: when over is empty

Examples:

  • LiChao(min, over: 0..=10).at(5) == None

Source

LiChao.clear

fn clear(mut self)

Forget every line, keeping pick and over, so the tree can be reused (between test cases, say) without reallocating.

  • cost: O(1) amortized
  • traps: never

Examples:

  • var t = LiChao(min, over: 0..=10); t.add(Line(1, 0)); t.clear(); t.at(3) == None

Source

LiChao.at

fn at(self, x: Int) -> ?K

The best value at x over every line covering x, as chosen by pick, or None when no line covers x (nothing added yet, or only segments that miss x).

  • cost: O(log n) for n = over.len
  • ties: equal values are one value; which line produced it does not matter
  • traps: when x is not in over

Examples:

  • var t = LiChao(min, over: 0..=10); t.add(Line(1, 0)); t.add(Line(-1, 6)); t.at(1) == Some(1) and t.at(5) == Some(1)

Source

LiChao.line_at

fn line_at(self, x: Int) -> ?L

The line attaining at(x), or None when no line covers x.

When several lines tie at x any of them may be returned; make K carry a tie-breaking second field (as with at returning (cost, used)) when the choice matters.

  • cost: O(log n) for n = over.len
  • ties: unspecified among lines with equal values at x; break ties through K
  • traps: when x is not in over

Examples:

  • var t = LiChao(min, over: 0..=10); t.add(Line(1, 0)); t.add(Line(-1, 6)); t.line_at(8) == Some(Line(-1, 6))

Source

LiChao.add

fn add(mut self, line: L, on: ?Range<Int> = None)

Add line on every coordinate of over, or only on the coordinates of on (on: lo..=hi). Later at(x) calls consider the line only where it was added.

Law: any two lines added cross at most once on over (true for straight lines, and for at functions whose difference changes sign at most once).

  • cost: O(log n) for a whole line, O(log^2 n) on a segment, for n = over.len; at most one new cell per level
  • empty: an empty on adds nothing
  • traps: when on reaches outside over

Examples:

  • var t = LiChao(max, over: 0..=10); t.add(Line(0, 5), on: 2..=4); t.at(3) == Some(5) and t.at(5) == None

Source

LiChao.wins

fn wins(self, a: K, b: K) -> Bool

Source

LiChao.kid

fn kid(mut self, i: Int, right_side: Bool) -> Int

Source

LiChao.settle

fn settle(mut self, at: Int, lo: Int, hi: Int, line: L)

Source

MongePath

pub struct MongePath<N, K>(nodes: List<N>, cost: (N, N) -> K)

O(1) per step; the next cut's optimum after O(1) amortized calls of cost. monge_path one node at a time, for a DP whose next weight depends on the optimum just found. next() returns the optimum at the next node and the node before it; val(i) reads any node already reached.

Source

MongePath.w

fn w(self, j: Int, i: Int) -> K

Source

MongePath.setup

fn setup(mut self)

Source

MongePath.next

fn next(mut self) -> (val: K, prev: Int)

Reach the next node: return the optimum at node len and the index of the node before it, then grow len by one. cost may read values already reached through val, so the weights can depend on earlier optima.

  • cost: O(1) amortized calls of cost
  • ties: among equal totals the predecessor found by LARSCH
  • traps: when every node has been reached (len == nodes.len)

Examples:

  • var p = MongePath([0, 1, 2], (a, b) => (b - a) * (b - a)); p.next(); p.next() == (val: 2, prev: 1)

Source

MongePath.val

fn val(self, i: Int) -> K

The optimum at node i, which must already be reached; val(0) is 0.

  • cost: O(1)
  • traps: when i < 0 or i >= len

Examples:

  • var p = MongePath([0, 1, 2], (a, b) => (b - a) * (b - a)); p.next(); p.val(1) == 1

Source

MongePath.len

fn len(self) -> Int

The number of nodes reached so far, nodes.first included, so a fresh MongePath has len == 1.

  • cost: O(1)
  • traps: never

Examples:

  • MongePath([0, 1, 2], (a, b) => (b - a) * (b - a)).len == 1

Source

MonotoneHull

pub struct MonotoneHull<P>(pick: (Int, Int) -> Int = min)

O(1) amortized per add and per at_next, O(log n) per at. The convex hull trick for lines added in slope order: falling slopes for pick: min, rising for max (an out-of-order slope traps). The online form of LiChao when slopes arrive sorted and no x-range is known. Each line may carry a tag (a photo count, a parent index); best_next returns the winning line's tag, and equal values go to the smaller tag, which is the tie rule aliens needs.

Source

MonotoneHull.sign

fn sign(self) -> Int

Source

MonotoneHull.val_at

fn val_at(self, i: Int, x: Int) -> Int

Source

MonotoneHull.covered

fn covered(self, k: Int, m: Int) -> Bool

Source

MonotoneHull.pop_line

fn pop_line(mut self)

Source

MonotoneHull.add

fn add(mut self, line: Line, tag: P = ())

Add line, with tag. Slopes must arrive in order: non-increasing for pick: min, non-decreasing for max. A line of equal slope keeps only the better intercept, and lines that are never best are dropped.

  • cost: O(1) amortized
  • traps: when the slope goes back

Examples:

  • var h = MonotoneHull<()>(min); h.add(Line(2, 0)); h.add(Line(-1, 3)); h.at(0) == Some(0) and h.at(2) == Some(1)

Source

MonotoneHull.best_next

fn best_next(mut self, x: Int) -> ?(val: Int, tag: P)

The best value at x with the tag of the line attaining it, for an x that never decreases between calls (a pointer walks the hull). None when empty.

  • cost: O(1) amortized
  • ties: equal values go to the smaller tag (the rule aliens needs)
  • traps: when x is less than the previous best_next or at_next argument

Examples:

  • var h = MonotoneHull<Int>(min); h.add(Line(1, 0), tag: 7); h.add(Line(-1, 2), tag: 3); h.best_next(1) == Some((val: 1, tag: 3))

Source

MonotoneHull.at

fn at(self, x: Int) -> ?Int

The best value at any x, by binary search on the hull; None when empty.

  • cost: O(log n)
  • ties: only the value is kept
  • traps: never

Examples:

  • var h = MonotoneHull<()>(min); h.add(Line(2, 0)); h.add(Line(-1, 3)); h.at(5) == Some(-2)

Source

MonotoneHull.at_next

fn at_next(mut self, x: Int) -> ?Int

at(x) for an x that never decreases between calls; None when empty.

  • cost: O(1) amortized
  • ties: only the value is kept
  • traps: when x is less than the previous best_next or at_next argument

Examples:

  • var h = MonotoneHull<()>(min); h.add(Line(2, 0)); h.add(Line(-1, 3)); h.at_next(0) == Some(0) and h.at_next(2) == Some(1)

Source

MonotoneHull.len

fn len(self) -> Int

The number of lines kept on the hull (dominated lines are not counted).

  • cost: O(1)
  • traps: never

Examples:

  • var h = MonotoneHull<()>(min); h.add(Line(2, 0)); h.add(Line(-1, 3)); h.len == 2

Source

MonotoneHull.clear

fn clear(mut self)

Remove every line and reset the at_next pointer, keeping pick.

  • cost: O(1)
  • traps: never

Examples:

  • var h = MonotoneHull<()>(min); h.add(Line(2, 0)); h.clear(); h.at(0) == None

Source

LineContainer

pub struct LineContainer(pick: (Int, Int) -> Int = min)

O(log n) amortized per add, O(log n) per at. The convex hull trick with lines in any order and queries at any x, no coordinate range needed (KACTL's line container). Use LiChao for segment adds or non-line functions.

Source

LineContainer.sign

fn sign(self) -> Int

Source

LineContainer.floor_div

fn floor_div(a: Int, b: Int) -> Int

Source

LineContainer.meet

fn meet(self, x: Int, y: Int) -> Int

Source

LineContainer.split

fn split(mut self, t: Int, k: Int) -> (Int, Int)

Source

LineContainer.merge

fn merge(mut self, a: Int, b: Int) -> Int

Source

LineContainer.end

fn end(self, t: Int, right: Bool) -> Int

Source

LineContainer.drop_end

fn drop_end(mut self, t: Int, right: Bool) -> Int

Source

LineContainer.best

fn best(self, x: Int) -> Int

Source

LineContainer.add

fn add(mut self, line: Line)

Add line; slopes may arrive in any order. Lines that are never best are dropped.

  • cost: O(log n) amortized
  • traps: never

Examples:

  • var c = LineContainer(max); c.add(Line(1, 0)); c.add(Line(-1, 4)); c.at(0) == Some(4) and c.at(3) == Some(3)

Source

LineContainer.at

fn at(self, x: Int) -> ?Int

The best value at x, or None when empty.

  • cost: O(log n)
  • ties: only the value is kept
  • traps: never

Examples:

  • var c = LineContainer(min); c.add(Line(1, 0)); c.add(Line(-1, 4)); c.at(0) == Some(0) and c.at(3) == Some(1)

Source

LineContainer.line_at

fn line_at(self, x: Int) -> ?Line

The line attaining at(x), or None when empty.

  • cost: O(log n)
  • ties: unspecified among lines with equal values at x
  • traps: never

Examples:

  • var c = LineContainer(max); c.add(Line(1, 0)); c.add(Line(-1, 4)); c.line_at(3) == Some(Line(1, 0))

Source

LineContainer.len

fn len(self) -> Int

The number of lines kept (dominated lines are not counted).

  • cost: O(1)
  • traps: never

Examples:

  • var c = LineContainer(max); c.add(Line(1, 0)); c.add(Line(-1, 4)); c.len == 2

Source

Step

pub struct Step<S>(state: S, depth: Int)

One state reached by backtrack.

Source

Step.prune

fn prune(self)

Skip every state below this one: backtrack does not call next on it. Has effect only on the step just yielded, before the for body continues.

  • cost: O(1)
  • traps: never

Examples:

  • with next as x => if x < 4: [2 * x, 2 * x + 1] else: [], a for s in backtrack(1, next) body that calls s.prune() when s.state == 2 sees the states [1, 2, 3, 6, 7]

Source

On this page