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:

• [x] AhoCorasickFixed
• [x] ModIntShort
• [x] ModFact
• [x] OrderStatisticTree
• [x] Segment Tree
• [x] Matrix
  • TODO: probably not worth including + and - in the notebook?
• [x] LazySegmentTree
  • note: kactl's version is dynamic
• [x] ModSqrt
• [x] (uncommon) gp_hash_table
  • TODO: shorten the version here?
• [x] linecontainer (old)
  • TODO: compare vs KACTL, compare vs new version?
• [x] modmulll
• [x] fastmod
• [x] MillerRabin
• [x] FactorFast
• [x] Python3
• [x] Simplex
• [x] Integrate
• [x] IntegrateAdaptive
• [x] DSU
• [x] RMQ
• [x] LinearRecurrence
  • TODO: check if I actually remember what this does
• [ ] LCAjump
• [x] treap
• [ ] Polynomial
• [ ] PolyInterpolate
• [ ] GaussianElimination
• [x] FFT
• [x] 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
• [x] FastIO
• [ ] KMP
• [ ] Z
• [ ] PolyCenArea
• [ ] PolySaVol
• [ ] Manacher
• [ ] SuffixArray
• [ ] (Rare) SuffixTree
• [ ] HashRange
• [ ] LCArmq
• [x] AngleCmp
• [ ] InPolygon
• [ ] Bellman Ford / Negative Cycle
• [x] ConvexHull (Monotone Chain)
• [x] HullDiameter
• [ ] LineHull
• [ ] CircleTangents
• [x] ClosestPair
• [ ] PolygonArea
• [ ] PolygonCenter

Here Only:

• [ ] simple sieve
• [ ] persistent segment tree
• [x] Multiplicative Prefix
  • TODO: remember what this does
• [x] PrimeCnt
• [ ] ModArith
• [ ] DeBruijnSeq
• [ ] Nim Product
  • TODO: Usage
• [ ] matroid intersection
  • TODO: Usage
• [ ] ShermanMorrison
  • TODO: Usage
• [x] 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
• [x] ComplexComp
• [x] HalfPlaneIsect
• [ ] DelaunayIncremental
• [ ] Delaunay3
  • TODO: remove versions of Delaunay that are not preferred
• [ ] ManhattanMST
• [ ] Point3D
• [ ] Hull3DFast
• [x] SuffixArrayLinear
  • TODO: check how fast this really is
• [ ] PalindromicTree
• [ ] (Rare) LyndonFactor
• [ ] (Rare) ReverseBurrowsWheeler
• [x] (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