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.
Line.at
fn at(self, x: Int) -> IntEvaluate the line at x: k * x + m.
- cost: O(1)
- traps: when
k * x + moverflowsInt
Examples:
Line(2, 3).at(4) == 11
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.
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
overtraps - order: no sequence is returned; coordinates run in
over's order - traps: when
overis empty
Examples:
LiChao(min, over: 0..=10).at(5) == None
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
LiChao.at
fn at(self, x: Int) -> ?KThe 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
xis not inover
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)
LiChao.line_at
fn line_at(self, x: Int) -> ?LThe 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 throughK - traps: when
xis not inover
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))
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
onadds nothing - traps: when
onreaches outsideover
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
LiChao.wins
fn wins(self, a: K, b: K) -> BoolLiChao.kid
fn kid(mut self, i: Int, right_side: Bool) -> IntLiChao.settle
fn settle(mut self, at: Int, lo: Int, hi: Int, line: L)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.
MongePath.w
fn w(self, j: Int, i: Int) -> KMongePath.setup
fn setup(mut self)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)
MongePath.val
fn val(self, i: Int) -> KThe optimum at node i, which must already be reached; val(0) is 0.
- cost: O(1)
- traps: when
i < 0ori >= len
Examples:
var p = MongePath([0, 1, 2], (a, b) => (b - a) * (b - a)); p.next(); p.val(1) == 1
MongePath.len
fn len(self) -> IntThe 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
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.
MonotoneHull.sign
fn sign(self) -> IntMonotoneHull.val_at
fn val_at(self, i: Int, x: Int) -> IntMonotoneHull.covered
fn covered(self, k: Int, m: Int) -> BoolMonotoneHull.pop_line
fn pop_line(mut self)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)
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
aliensneeds) - traps: when
xis less than the previousbest_nextorat_nextargument
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))
MonotoneHull.at
fn at(self, x: Int) -> ?IntThe 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)
MonotoneHull.at_next
fn at_next(mut self, x: Int) -> ?Intat(x) for an x that never decreases between calls; None when empty.
- cost: O(1) amortized
- ties: only the value is kept
- traps: when
xis less than the previousbest_nextorat_nextargument
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)
MonotoneHull.len
fn len(self) -> IntThe 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
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
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.
LineContainer.sign
fn sign(self) -> IntLineContainer.floor_div
fn floor_div(a: Int, b: Int) -> IntLineContainer.meet
fn meet(self, x: Int, y: Int) -> IntLineContainer.split
fn split(mut self, t: Int, k: Int) -> (Int, Int)LineContainer.merge
fn merge(mut self, a: Int, b: Int) -> IntLineContainer.end
fn end(self, t: Int, right: Bool) -> IntLineContainer.drop_end
fn drop_end(mut self, t: Int, right: Bool) -> IntLineContainer.best
fn best(self, x: Int) -> IntLineContainer.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)
LineContainer.at
fn at(self, x: Int) -> ?IntThe 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)
LineContainer.line_at
fn line_at(self, x: Int) -> ?LineThe 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))
LineContainer.len
fn len(self) -> IntThe 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
Step
pub struct Step<S>(state: S, depth: Int)One state reached by backtrack.
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
nextasx => if x < 4: [2 * x, 2 * x + 1] else: [], afor s in backtrack(1, next)body that callss.prune()whens.state == 2sees the states[1, 2, 3, 6, 7]