Ciorna

Structuri de date

Lista
- cele alocate static sunt des mai eficiente decat std::vector
- Probleme: infinityway
- Dancing links
  - Probleme: Working routine, Souvenirs
Stiva
- All nearest smaller values
- Probleme: matrix2, towers, password1, turnuri2
Cozi
- Probleme: padure
Deque
- Probleme: branza, vila2, struti, sir
Tabele de dispersie
- Cuckoo hashing
Bloom filters
- Probleme: dtcsu
Skiplists
- Probleme: citylog
Arbori indexati binar
- Arhiva Educationala
- Extensie pentru Range Query si Range Update
- Probleme: datorii, pq, distincte, calafat, hapsan, undo
Arbori de intervale
- Arhiva Educationala
- Articol pe infoarena
- Zkw Segment Tree (observatie: atunci cand query-ul nu este comutativ, vezi neapuiu sau namlei)
- Probleme: 3max, flower, flooow
- Probleme lazy update: diapazon, euclid1,
- Probleme baleiere : zoo, cabana2, arbsat
- Probleme 2D: sccm, mess, marmote, bile4
- Probleme dinamic: pentru intervale mari, unde nu se poate normaliza
  - Preferabil ca a doua dimensiune sa fie un aib rar (alaturi de lista de elemente ordonate crescator)
- Probleme persistent: ants, kthvalue, CF 786C
- Li Chao Segment Tree: 1, 2, 3
  - Probleme: euro, Organizing a race, cascaval
Structuri de multimi disjuncte
- e-maxx
- Arhiva Educationala
- Probleme: bile, mexc
- Operatia de undo: unlock
- Smenul pentru dynamic connectivity: probleme, curent
- Algoritmul lui Tarjan pentru LCA offline, la RMQ
- Colorare pe interval: curcubeu, nucleuvaloros
- All nearest smaller values in Nlog*N + sortare
- Determinarea punctelor de articulatie online
Trie
- Arhiva Educationala
Cozi de prioritati
- Heap-uri
  - Probleme: cezar, procesor, bleach, sao, dlboss
- Mergeable Heap
  - Probleme: ktown
- Pentru costuri intregi mici, un array de liste
Treapuri
- Fara rotatii
- Probleme: rotatii, sir8
- Probleme implicit: secv8, rev
- Probleme persistent: Codechef GENETICS
Sparse Table
- Probleme: biomech, euclid, matrice3, zodiac
Sqrt Trick
- Sqrt Trick Lecture
- Algoritmul lui Mo: rangemode, infinitywar
  - Pe arbore: egal, DISTNUM3
  - Update-uri
- Probleme: CF 702 F, CF 342 E, rafaela, Tree of Almost Clean Money, rutier
- Alta idee, triaj
Cautari ortogonale. Quad trees, kD-trees
- Probleme: imagine, grau, mindist
Wavelet Matrix
- Probleme: qxy

Matematica

Inductie matematica
- Probleme: borcane
- Backwards induction
  - Probleme: caraibe
Algoritmul lui Euclid
- Fractii simple continue
- Compararea fractiilor
Ciurul lui Erathostene
- Ciur liniar
- Ciur cu memorie sqrtN
- Numarare divizori in cbrtN
- Factorizare rapida dupa ciur
  - Probleme: sprim
- Ciurul lui Xudyh
  - Probleme: cntgcd, Line counting
Exponentiere rapida
Coduri gray
Teorema chineza a resturilor
- Probleme: eval, resturi, gears in action, resturi2
Operatii pe numere mari
Fast Fourier Transform
- Inmultirea polinoamelor
- Detalii implementare
- Probleme: bacterii2, chimichangas, RPSRobots, SplittingFoxes2, FoxAndSouvenir, Lista pe CF
- Legat de erorile de precizie
- Numeric Theoretic Transform
- Fast Walsh-Hamard transform
- Inversul unui polinom
- Probleme: Random NIM Generator, And-Closure, aiacubiti, Varying Kibibits
- Mixed radix
  - Probleme: POLYEVAL
- Smenul cu divide et impera
  - Probleme: CF 438E, CF 553E, Jetpack
Eliminare Gaussiana
- Probleme: network, CF 446D, switch5, maxxor2
- Determinant: afterparty
- Rangul matricei
- Inversa matricei: Por Costel si Bujor
- Tridiagonal matrix algorithm
  - Probleme: Simple Calculations, sms
- Eigenvalues
  - Probleme: Zombie March
Recurenta liniara
- Rezolvarea unei recurente liniare
  - Probleme: CF 446C
- Exponentiere de matrice
- Algoritmul lui Kitamasa
  - Teorema Cayley-Hamilton
  - Explicatie: Aici sau aici
- Algoritmul Berlekamp–Massey pentru recurenta de ordin minim al unui sir
  - Calcularea determinantului
Divizibilitate
- Probleme: maxd, armonica
Algoritmul Rabin Miller
- Probleme: dk, Four Divisors
Simplex
- Duality
- Probleme: echilibrare
Floyd's cycle finding
- Probleme: reactor, robotei
Combinatorica
- Triunghiul lui Pascal
- Triunghiul lui Sierpinski
  - Probleme: magic4, xor3
- Permutari / Combinari cu repetitii
- N ca suma de K valori pozitive
  - Probleme: superbec
- N ca suma de valori K valori strict pozitive $\binom{N - 1}{K - 1}$
- Numarul lui Catalan
  - Triunghiul lui Catalan
  - Probleme: permutare4, colors
- Teorema lui Lucas
  - Generalizare pentru puteri de numere prime
    - Se factorizeaza restul si apoi aplica Teorema chineza a resturilor
  - Probleme: showroom, jap2
- Teorema lui Wilson
  - E-maxx
  - Probleme: jap2
- Numerele lui Stirling
  - Problemele: ex, xnumere, trineq
- Identitatile Hockey-stick si a lui Vandermonde
  - Probleme: nmult
- Lema lui Burnside
- Teorema lui Pólya
- Formula lui Cayley
  - Probleme: zapezi2
- Trecere de la combinare/permutare la indexul ei si invers
  - Probleme: perm3, perm5, nkperm
- Binomial inversion
  - Probleme: pitmutare, derajamente
Reprezentanti in clase de echivalenta
- Problemele: salaj, Bracket Subsequences, DSUBSEQ, camere
Mobius Function
- Probleme: porcjoc
Baze de numeratie
- Probleme: NumberOfPaths, copii2, psychtraining, zimeria, incantatii, sticle
Probabilitati
- Teorema lui Bayes
- Expected value: Tequila, Sms, Expected Velea, Albume, Diapazon
- Ballot theorem
- Markov chains
  - Probleme: Humpty Dumpty, Random Run, Zombie March
Principiul includerii si excluderii
- Probleme: cowfood, indep, frac, CF 451E, light2, trickortreat
Lema lui Abel
- Probleme: Power of Power Partition Function
Taylor series
Formal power series
- Generating Functions
Interpolare polinoame
- Problema: puteri3, The Sum of the k-th Powers
Metoda lui Newton

Grafuri

Parcurgeri

DFS, BFS
- Probleme: grarb, sate, cifre4, berarii2
- Stramosi in timp constant
  - Probleme: spiridusi, Running Away From the Barn
- Meet in the middle BFS: POSLOZI
- Lex BFS
- DFS cu baleiere: tradare
- Metoda drumului critic
  - Probleme: pm2
Ciclu eulerian
- Probleme: cartite, tester, domino
- De Bruijn sequence
- Teorema BEST
Componente biconexe
- Probleme: ro, santa, pamant, clepsidra, sokoban, lianyu, victorie, ostrov
Componente tare-conexe
- Probleme: retele, drum4, plimbare, drumuri5
- 2-SAT
  - Probleme: aladdin, entanglement
Sortare topologica
- Probleme: volum, pang
Dominator Tree
- Probleme: colonii

Drumuri minime

Dijkstra
- Probleme: distante, trilant, camionas, banuti
- Dijkstra cu costuri mici
  - Probleme: car, gravity
- Meet in the middle Dijkstra
  - Probleme: nolife
Bellman-Ford
- Probleme: zmeu2, dmin, lanterna, ciclu
- Sistem de inegalitati
  - Probleme: import
Roy-Floyd
- Probleme: coach, rfinv, rf, risc

Diverse

Grafuri planare
- Probleme: count, nowhere-zero

Grafuri turneu/ciclu hamiltonian
- Probleme: plimbare
- Ciclu hamiltonian in grafuri cu conditia lui Ore

Havel-Hakimi
- Probleme: grade
Compresia grafurilor
- Probleme: centrale, substring-restrictions , field-activation , legacy, Apple Market
Clica maxima
Cactus graf
- Probleme: special-mvc
Gomory-Hu Tree
- Probleme: pumping-stations
Pseudo-Forest

Arbori

Diametrul unui arbore
Lowest Common Ancestor
- Probleme: pirati, concurs,
- Tarjan offline
- Schieber Vishkin
- Stramosi
Izomorfism de arbori
- Probleme: divizori2
- RNG Hash
Smen 2 DFS-uri
- Probleme: razboi, asmin, treesearch
Heavy path decomposition
- Probleme: rafaela, metro
- Pe subarbori
Centroid decomposition
- Probleme: simulare, ecotraseu, treemis
Longest path decomposition
Parcurgere Euler
- Probleme: maimute, arbfind, treesmen, arbore, cli, radare
Descompunere in numar minim de lanturi
- Probleme: tree
Cod Prufer
- Probleme: New Year and forgotten tree
Virtual Tree
- Probleme: hardtask, kdist

Flux and related

Flux maxim

Edmonds-Karp
- Probleme: joc4, ghizi, teroristi, mingiute, tarnacop
Taietura minima
- Probleme: croco, pixels, goods transportation, bilingual, sabotaj
Dinic
- Probleme: alt, Captain America
Push-relabel
- Probleme: tero
Flux maxim de cost minim
- Probleme: traseu, naveplanare, smart
Flux cu capacitati inferioare

Cuplaj

Hopcroft - Karp
- Probleme: senat, gandaci java, revolutie, circulatie, album, caroiaj, ciocolata2, drumuri2
Cuplaj maxim de cost minim
- Probleme: atac2, terenuri3d, cc, smen, padurari
Suport minim
- Probleme: felinare
Algoritmul ungar
- Probleme: echilibrare
Dilworth's theorem
Konig's theorem
Hall's marriage theorem
- Probleme: Ice Skates
Algoritmul Blossom
Tutte Matrix

APM

Probleme: yamstp, metrou4
Prim
- Probleme: cablaj
Kruskal
- Probleme: online, elicoptere, ninjago
Al doilea APM
- Probleme: meta
Arborescenta
APM de diametru minim
APM cu grade restrictionate
Kirchhoff's matrix tree theorem
- Probleme: Join, Little Artem and Graph

Stringuri

String matching
- KMP
  - Probleme: prefix, zlego, map, potrivire
- Z-algorithm
  - Probleme: arbfind, x, aparitii2, potriveala
- Rabin-Karp
  - Probleme: ratina, partialmatch, per, parpal
Manacher
- Probleme: pscpld, numarare, origami2
Aho-Corasick
- Probleme: rk, xormax, CF 710 F, KC, seti, cenzura
- smen pentru operatii de insert si erase
Rotatie lexicografica minima
- Probleme: password
EERTree
- Problema: pal2
Suffix Array
- Probleme: ghicit, substr, seti, jocs, revsecv, klsecv, parb2
- Prefix doubling
- SA-IS
- Kasai LCP
Suffix tree
Suffix automaton
- Probleme: prefix2
Synchronizing word
CYK
- Probleme: minerale

Geometrie

Teorie

Basics
- Probleme: triang, cerc3, poligon6, trapez
Teorema lui Pick
- Probleme: copaci, nperechi
Suma Minkowski
Coordonate Baricentrice
Rotire plan
- Manhattan - Chebychev
  - Probleme: distancesum

Intersectii

dreapta - dreapta
dreapta - segment
- Probleme: elicoptere
segment - segment
- Probleme: geometry
cerc - cerc
- Probleme: cuiburi
poligon convex - poligon convex
semiplan - semiplan (fara dualizare)
- Probleme: camera, copacsmenar

Poligoane

Punct in poligon
- Probleme: dreapta
- Punct in poligon convex
  - Probleme: combl
Aria unui poligon
- Probleme: qtri
Triangularizare Delaunay

Algoritmi

Infasuratoare convexa
- Probleme: mosia, ydist, tri3, geometrie, oypara, biathlon
- Dinamic: terenuri
Cele mai apropiate puncte din plan
- Probleme: harta2
- Algoritm Las Vegas
Minimal enclosing circle
- Solutia cu Hill Climbing
Diagrame Voronoi

Baleiere

Verticala / orizontala
- Probleme: drept3, cabana2
Radiala
- Probleme: cangurix, flori2
Rotating calipers
- Probleme: rubarba, popandai2

Progrmare Dinamica

Parantezare optima de matrici
- Probleme: palin3, redu, stiva
Cel mai lung subsir crescator
- Probleme: subsiruri, euro2, move
Knapsack
- Probleme: energii, jocul, piete, pusculita
- Knapsack pe biti
- Knapsack pe arbore
  - Probleme: lianyu, arbkset, cli
- Bounded Knapsack trick
  - Probleme: ghiozdan
Cel mai lung subsir comun
- Algoritmul Hunt-Szymanski este cel mai rapid in practica
- Cyclic
Distanta de editare a 2 cuvinte
- Probleme: note
Dinamici pe stari
- Codificare pe biti
  - Probleme: ciclu hamiltonian de cost minim, coins, sobo, morcovi, poly, datorii2, aby
  - Sum over subsets
  - Dinamici in 3ⁿ
    - Probleme: scara2, colorare, zebughil, ndap, cast, carti2
- Probleme: cabane, kcity, parcare, clear
Dinamici pe arbori
- Probleme: color2, sediu, arb2
Memoizare
- Probleme: alpin, Mr. Kitayuta, the Treasure Hunter, aby
Metode de optimizare
- Functii Monge convexe / concave
  - Probleme: Aliens, Exam Cheating, Building a Tall Barn, popcorn, April Fools Problem
- Probleme: nucleulvaloros2, euro, costsq, easyvect
- Hirschberg trick
  - Probleme: ghiozdan
- Numere pentagonale
  - Probleme: echival2, crescator2
- Slope trick
  - Problema: ktown, cascaval
Dinamici pe cifre
- Probleme: peluzanord, simpla, cifre
Dinamici pe permutari
- Probleme: kangaroo, Ant man
Dinamici pe cuplaj
- Probleme: LittleElephantAndPermutationDiv1
Dinamici pe frecvente
- Probleme: raco, produse

Teoria jocurilor

NIM
- Probleme: cartonase
- Staircase Nim
  - Probleme: joc3
Sprague - Grundy
Min - Max
Alpha - Beta

Diverse

Cautare binara
- Probleme: transport, grupuri, lumanari, sume2
- Cautare binara pe eroare relativa
- In paralel
  - Probleme: luff, termite, matrice2
Sortare
- Probleme: permut, sport, secv
- Quick-sort
  - Probleme: invsort
- Merge-sort
  - Probleme: inv
- Heap-sort
  - Probleme: triangles
- Radix-sort
  - Probleme: binar, specsort
- Quicksort Ternar
  - Probleme: incantatii, zimeria
Statistici de ordine
- Probleme: beri, toys
Cautare ternara
- Probmele: rubarba
Smenul lui Mars
- Probleme: geamuri, ben, plaja, sahara, inception
Evaluare de expresii
- Probleme: expresie2, dir, bool, eval, evaluare2
Meet in the middle
- Probleme: alianta, sipet, overdrive, colectie
Euristici
- Heavy-path trick
  - Probleme: egal, Online Xor-Max
- Lovasz Toggle
Optimizari
- Parsarea citirii / iesirii
- Barrett Reduction, Montgomery multiplication
- Random Shuffle
- Hill-Climbing, Simulated Annealing

Link-uri utile