kactl

Do zrobienia

• kth-competitive-programming/kactl#63
• Cleanup weighted blossom?
• kth-competitive-programming/kactl#137
• Zredagować ściągi, pewnie wywalić większość
• Naprawić spacing po spisie treści i w ściągach
• Generalnie prawie wszystko modulo powinno być na mintach
• Podzielić duże pliki/hasze przedziałów (fft, fftpoly)
• Cleanup fftpoly?
• Zrobić żeby cachowanie library-checker-problems było mądrzejsze
• 4 KOLUMNY!!!

Do weryfikacji w KACTL

Stan	Nazwa
✔️	Contest
❌	Mathematics
✔️	Data structures
❌	Numerical
✔️	Number theory
❌	Combinatorial
❌	Graph
❌	Geometry
❌	Strings
✔️	Various

Struktury danych

Stan	Nazwa
✔️	gp_hash_table
✔️	ordered_set
✔️	Line container
✔️	Sparse table
⚠️	Lazy segtree
❌	Persistent segtree
⚠️	Treap
✔️	Fenwick
⚠️	Fenwick 2D
❌	Drzewo lichao (z dodawaniem i maxowaniem)
❌	Persistent treap
❌	Wavelet tree
⚠️	DSU z rollbackami
⚠️	Mo on array, on tree
❌	Segment tree beats

Matma

Stan	Nazwa
✔️	Mint
❌	Silnie i odwrotności
❌	ModMul double
⚠️	Barret
✔️	Pierwiastek mod
✔️	Floor sum
⚠️	Mod sum
✔️	Sito z bitsetem
✔️	Sumy prefiksowe funkcji multiplykatywnej
✔️	Miller rabin
✔️	Pollard rho
❌	Ułamek między a i b o najmniejszym mian.
⚠️	Rozszerzony euklides
⚠️	CRT
⚠️	Min mod linear, first mod linear
⚠️	Ciąg debruijna
✔️	Nim product
⚠️	Przecięcie matroidów
❌	Szybkie mnożenie (simd) i potęgowanie (frobenius) macierzy
✔️	Macierz (wyznacznik, odwrotność)
❌	Sherman Morrison
✔️	Operacje na wielomianach (inv, exp, pow, log, interp, eval, chirpz)
✔️	NTT
✔️	NTT Garner
✔️	Berlekamp-Massey
⚠️	Simpson
⚠️	Adaptive simpson
⚠️	Simplex
⚠️	Binsearch na ułamkach
✔️	Logarytm dyskretny
✔️	Generator mod
✔️	Sploty AND, OR, XOR
❌	Splot SUBSET
❌	Interpolacja Lagrange'a dla jednego punktu z 0...n
✔️	Rozwiązywanie niekwadratowego SLAE
❌	Mobius i Phi
❌	Rozwiązania równania Pella
❌	Sumy potęgowe
❌	Generowanie trójek pitagorejskich
⚠️	Przedziały równości dzielenia floor/ceil
❌	XOR basis
✔️	Mnożniki lagrange'a
✔️	Wyznacznik macierzy (black box z berlekampem)
❌	Kod graya i odwrotność
❌	Schreier-Sims
✔️	Twierdzenie pentagonalne eulera
⚠️	Ułamek

Grafy

Stan	Nazwa
✔️	DSU
❌	Ujemny cykl
❌	LCA skok
❌	LCA rmq z kompresją
❌	HLD
✔️	Centroidy
✔️	Cykl eulera
✔️	SCC
⚠️	2-SAT
✔️	Dwuspójne
⚠️	Maksymalne kliki
⚠️	Dinic
⚠️	Gomory-Hu
⚠️	MCMF
✔️	Hungarian
✔️	General matching blossom
✔️	General weighted matching
✔️	Hopcroft-Karp
❌	Chordal Graph Recognition
✔️	Drzewo dominatorów
⚠️	Kolorowanie krawędzi w D+1
✔️	DMST
⚠️	Link-cut tree z różnymi rzeczami
❌	Dynamic connectivity
❌	Twierdzenie Koniga
⚠️	Ściany grafu planarnego
❌	Test planarności grafu
✔️	Największa klika
❌	Trójkąty
❌	5-kolorowanie grafu planarnego
❌	Max matching Tutte
❌	Incremental SCC
⚠️	Reroot DP
✔️	Twierdzenie BEST
✔️	Twierdzenie Kirchoffa
✔️	Liczba chromatyczna
❌	Wielomian chromatyczny
❌	Kolorwanie krawędzi grafu dwudzielnego w D
✔️	K-ta najkrótsza ścieżka
❌	Incremental bipartite matching
❌	SPFA smu

Geometria

Stan	Nazwa
❌	Zdecydować postępowanie co do templatów i doubli
⚠️	Punkt
✔️	Angle cmp
⚠️	Segment dist, line dist
⚠️	Przecięcie prostych/odcinków
⚠️	Środek ciężkości wielokąta
⚠️	Test czy jest w środku wielokąta
✔️	Otoczka wypukła
❌	Suma minkowskiego
✔️	Najdalsze punkty na otoczce
⚠️	Styczne do otoczki
⚠️	Przecięcie otoczki z prostą
⚠️	Przecięcie półpłaszczyzn
❌	Online przecięcie półpłaszczyzn
⚠️	Suma wielokątów
❌	Okrąg
⚠️	Przecięcie okrąg okrąg
❌	Pole przecięcia okrąg okrąg
⚠️	Przecięcie okręgu i prostej
⚠️	Wspólne styczne okręgów
⚠️	Okrąg opisany na trójkącie
⚠️	Min enclosing circle
✔️	Najbliższa para punktów
⚠️	Delaunay triangulation
✔️	Manhattan MST
⚠️	Punkt 3D
⚠️	Otoczka 3D O(n^2)
❌	Otoczka 3D O(n log n)
❌	Pole powierzchni
⚠️	Objętość
⚠️	Test czy punkt w otoczce
⚠️	Obcięcie wielokąta prostą
⚠️	Pole wielokąta
❌	Online otoczka wypukła
❌	Generowanie SVG wielokąta z punktów
❌	Diagram Voronoia
❌	Konwersja między postaciami prostych
❌	Test czy odcinek jest w środku wielokąta
❌	Zamiatanie cykliczne półprostą
❌	Convex poly periodic min comp (zamienic z hull tangents, dodac min/max dot) (maspy)
❌	Jakiś point location albo przynajmniej tutorial lol
❌	Geo 3d (op na liniach, płaszczyznach, sferach itp)

Teksty

Stan	Nazwa
⚠️	KMP
✔️	Z
✔️	Manacher
✔️	Duval
⚠️	Haszowanie
❌	Reverse Burrows-Wheeler
⚠️	Aho
✔️	Tablica sufiksowa
❌	Liniowa tablica sufiksowa
✔️	Substringi cykliczne (Main-Lorentz)
✔️	Drzewo palindromów
❌	Automat sufiksowy
⚠️	Drzewo sufiksowe
✔️	Wildcard matching
❌	Znajdowanie przedziału wystąpień w tablicy sufiksowej
❌	Inty zamiast stringów?
❌	LCS miedzy wszystkimi substringami
❌	Monge (range LIS query)
⚠️	Szybkie modulo 2^61-1

Inne

Stan	Nazwa
❌	Circular LCS
❌	SMAWK
⚠️	Fast IO
❌	Python, decimal
⚠️	Divide and conquer DP
⚠️	Knuth DP
⚠️	Pragmy
⚠️	Subset sum dynamic bitset
❌	CHT
❌	Subset sum modulo m w O(m log m)
❌	Dobre ściągi, w szczególności UJ, UW1, stare UW, bardzo stare UW
❌	Szybkie sortowanie

Źródła

• https://github.com/ecnerwala/cp-book/
• https://github.com/dacin21/dacin21_codebook
• https://github.com/nealwu/competitive-programming
• https://github.com/the-tourist/algo
• https://github.com/bqi343/cp-notebook
• https://github.com/kth-competitive-programming/kactl
• https://github.com/cuber2460/acmlib07/
• https://mimuw.edu.pl/~ms360974/treningi/ACMLib.pdf
• https://github.com/tonowak/acmlib
• https://github.com/maspypy/library
• https://github.com/Stonefeang/librewoosh
• https://github.com/KacperTopolski/kactl
• https://github.com/ecnerwala/icpc-book