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, |
| ✔️ | 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