Review Implementations

[bqi343]

Probably worth maintaining a list of implementations included in the notebook here but not in KACTL. Check the corresponding implementation if:

• title is informative
• usage is clear
• impl has been validated
• distracting comments don't appear in the notebook
• impl has been compared against KACTL

Both:

• AhoCorasickFixed
• ModIntShort
• ModFact
• OrderStatisticTree
• Segment Tree
• Matrix
  • TODO: probably not worth including + and - in the notebook?
• LazySegmentTree
  • note: kactl's version is dynamic
• ModSqrt
• (uncommon) gp_hash_table
  • TODO: shorten the version here?
• linecontainer (old)
  • TODO: compare vs KACTL, compare vs new version?
• modmulll
• fastmod
• MillerRabin
• FactorFast
• Python3
• Simplex
• Integrate
• IntegrateAdaptive
• DSU
• RMQ
• LinearRecurrence
  • TODO: check if I actually remember what this does
• LCAjump
• treap
• Polynomial
• PolyInterpolate
• GaussianElimination
• FFT
• FFTMod
  • TODO: make this compatible with ModInt
• ModSum
• Euclid
• FracInterval
• CRT
• MinCostMaxFlow
  • TODO: recheck this
• GomoryHu
  • TODO: check that this works with Dinic
• MaxMatchFast
  • TODO: Usage / Indexing
• Hungarian
  • TODO: Usage / Indexing
• EulerWalk
  • TODO: Usage / Indexing
• SCCT
  • TODO: Usage / Indexing
• TwoSAT
  • TODO: Usage / Indexing
• BCC
  • TODO: Usage / Indexing
• MaximalCliques
• HLD
• LinkCutTree
• DirectedMST
• MatrixTree
• PointShort
  • OnSegment
• SegDist
• SegIsect
• Circle
• CircleIsect
• CircleTangents
• Circumcenter
• MinEnclosingCirc
• EdgeColor
• DelaunayFast
• PolyhedronVolume
• Point3D
• FastIO
• KMP
• Z
• PolyCenArea
• PolySaVol
• Manacher
• SuffixArray
• (Rare) SuffixTree
• HashRange
• LCArmq
• AngleCmp
• InPolygon
• Bellman Ford / Negative Cycle
• ConvexHull (Monotone Chain)
• HullDiameter
• LineHull
• CircleTangents
• ClosestPair
• PolygonArea
• PolygonCenter

Here Only:

• simple sieve
• persistent segment tree
• Multiplicative Prefix
  • TODO: remember what this does
• PrimeCnt
• ModArith
• DeBruijnSeq
• Nim Product
  • TODO: Usage
• matroid intersection
  • TODO: Usage
• ShermanMorrison
  • TODO: Usage
• polynomial inverse / log / exp
  • TODO: clean up
  • what's the difference between exp and expOld?
• Centroid Decomp
• Dinic
• GeneralMatchBlossom
• GeneralWeightedMatch
  • is the time complexity actually $O(N^3)$?
• ChordalGraphRecognition
• DominatorTree
• ComplexComp
• HalfPlaneIsect
• DelaunayIncremental
• Delaunay3
  • TODO: remove versions of Delaunay that are not preferred
• ManhattanMST
• Point3D
• Hull3DFast
• SuffixArrayLinear
  • TODO: check how fast this really is
• PalindromicTree
• (Rare) LyndonFactor
• (Rare) ReverseBurrowsWheeler
• (Rare) TandemRepeats
• (Rare) SuffixAutomaton
• (Rare) CircularLCS
• (Rare) SMAWK

KACTL Only:

• ContinuedFractions
• FracBinarySearch
• minRotation
• (unused) Angle
• (unused) sideOf
• (unused) PolygonCut
• (unused) PointInsideHull
• (unused) LineHullIntersection
• (easy) BIT
• (easy) union find rollback
• (easy) 2D rectangle sums
• (easy) BIT2D
• (easy) MoQueries
• (easy) PolyRoots
• (easy) golden section search
• (easy) hill climbing
• (unused) IntDeterminant
• (easy) SolveLinearBinary
• (never used) Tridiagonal
• (easy) fast subset transform
• (easy) modlog
• (never used) FastEratosthenes
• (easy) PhiFunction
• (unused) IntPerm
• (easy) Multinomial
• (easy) floyd warshall
• (easy) TopoSort
• (rarely used) PushRelabel
• (slow) EdmondsKarp
• (easy) DFS matching
• (easy) MinimumVertexCover
• (easy) CompressTree
• (easy) linearTransformation
• (unused) CirclePolyIntersection
• (easy) IntervalContainer
• (easy) IntervalCover
• (easy) ConstantIntervals
• (easy) Ternary Search
• (easy) LIS
• (slow) Hull3DSlow
• (unused) BumpAllocator
• (unused) SIMD
• (unused) KdTree
• (unused) Spherical Distance
• (unused) GlobalMinCut
• (unused) General Matching - Matrix Version
• (unused) MaximumClique