Jikka-5.0.11.1: A transpiler from Python to C++ for competitive programming
Copyright(c) Kimiyuki Onaka 2021
LicenseApache License 2.0
Maintainerkimiyuki95@gmail.com
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Jikka.Core.Convert.ConvexHullTrick

Description

\[ \newcommand\int{\mathbf{int}} \newcommand\bool{\mathbf{bool}} \newcommand\list{\mathbf{list}} \]

Synopsis

Documentation

run :: (MonadAlpha m, MonadError Error m) => Program -> m Program Source #

run optimizes a DP which has the recurrence relation \[ \mathrm{dp}(i) = \min a(j) x(i) + b(j) \lbrace \mid j \lt i \rbrace + c(i) \] where only appropriate elements of \(\mathrm{dp}\) are used in \(a, x, b, c\).

internal rules

parseLinearFunctionBody' :: VarName -> VarName -> VarName -> Expr -> Maybe (Expr, Expr, Expr, Expr) Source #

parseLinearFunctionBody` parses the body of a linear function which can be decomposed to convex hull trick. parseLinearFunctionBody' f i j e finds a 4-tuple a, b, c, d where e = a(f[j], j) c(f[< i], i) + b(f[j], j) + d(f[< i], i).

TODO: What is the relation between j and k?