Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-04-04 18:04:47.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Training path
Structuri de date
- Lista
- cele alocate static sunt des mai eficiente decat std::vector
- Probleme: infinityway
- Stiva
- All nearest smaller values
- Probleme: matrix2, towers, password1
- Cozi
- Probleme: padure
- Deque
- Tabele de dispersie
- Bloom filters
- Probleme: dtcsu
- Skiplists
- Probleme: citylog
- Arbori indexati binar
- Arbori de intervale
- Arhiva Educationala
- Articol pe infoarena
- Implementare rapida (observatie: atunci cand query-ul nu este comutativ, vezi neapuiu sau namlei)
- Probleme: 3max, flower, flooow
- Probleme lazy update: diapazon, euclid1,
- Probleme baleiere: cabana2, arbsat
- Probleme 2D: sccm, mess, marmote, bile4
- Probleme dinamic: pentru intervale mari, unde nu se poate normaliza, putem avea O(log(VMAX))
- Este preferabil ca a doua dimensiune sa fie un aib rar (alaturi de lista de elemente ordonate crescator)
- Probleme persistent: ants, kthvalue, CF 786C
- 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
- Trie
- Cozi de prioritati
- Heap-uri
- Radix-heap
- Fibonacci Heap
- Pentru costuri intregi mici, un array de liste
- Treapuri
- Fara rotatii
- Probleme: rotatii, sir8
- Probleme implicit: secv8, rev
- Probleme persistent: Codechef GENETICS
- Sparse Table
- Sqrt Trick
- Sqrt Trick Lecture
- Algoritmul lui Mo: rangemode, egal, infinitywar, Codechef DISTNUM3
- Probleme: CF 702 F, CF 342 E, rafaela, Tree of Almost Clean Money, rutier
- Alta idee, triaj
- Cautari ortogonale. Quad trees, kD-trees
- Wavelet Matrix
- Probleme: qxy
- Van Emdge Boas tree
- Scape-goat Tree
Matematica
- Inductie matematica
- Probleme: borcane
- Algoritmul lui Euclid
- Ciurul lui Erathostene
- 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
- Probleme: Random NIM Generator, And-Closure, aiacubiti
- Mixed radix
- Probleme: POLYEVAL
- Smenul cu divide et impera
- Eliminare Gaussiana
- Probleme: network, CF 446D, switch5
- Determinant: afterparty
- Rangul matricei
- Inversa matricei: Por Costel si Bujor
- Factorizare LU
- Recurenta liniara
- Rezolvarea unei recurente liniare
- Probleme: CF 446C
- Exponentiere de matrice
- In general este de ajuns
- Algoritmul lui Kitamasa
- Algoritmul Berlekamp–Massey pentru recurenta de ordin minim al unui sir
- Rezolvarea unei recurente liniare
- Divizibilitate
- Probleme: armonica
- Algoritmul Rabin Miller
- Probleme: dk, Four Divisors
- Simplex
- Floyd's cycle finding
- Combinatorica
- Triunghiul lui Pascal
- Triunghiul lui Sierpinski
- Permutari / Combinari cu repetitii
- N ca suma de K valori pozitive
- Probleme: superbec
- N ca suma de valori K valori strict pozitive
- Numarul lui Catalan
- Triunghiul lui Catalan
- Probleme: permutare4, colors
- Teorema lui Lucas
- Teorema lui Wilson:
- Numerele lui Stirling
- Identitatile Hockey-stick si a lui Vandermonde
- Probleme: nmult
- Lema lui Burnside
- Formula lui Cayley
- Probleme: zapezi2
- Trecere de la combinare/permutare la indexul ei si invers
- Mobius Function
- Probabilitati
- 'Teorema lui Bayes'
- Expected value: Tequila, Sms, Expected Velea, Albume, Diapazon
- Ballot theorem
- Markov chains
- Probleme: Humpty Dumpty, Random Run
- Principiul includerii si excluderii
- Lema lui Abel
- Probleme: Power of Power Partition Function
- Taylor series
- Generating Functions
- Interpolare polinoame
- Problema: puteri3, The Sum of the k-th Powers
- Metoda lui Newton
Grafuri
Parcurgeri
- DFS, BFS
- Ciclu eulerian
- Probleme: cartite, tester, domino
- Teorema BEST
- Componente biconexe
- Componente tare-conexe
- Sortare topologica
- Dominator Tree
- Probleme: colonii
Drumuri minime
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
- Clica maxima
- Cactus graf
- Probleme: special-mvc
- Gomory-Hu Tree
- Probleme: pumping-stations
- Pseudo-Forest
Arbori
- Diametrul unui arbore
- Lowest Common Ancestor
- Izomorfism de arbori
- Smen 2 DFS-uri
- Probleme: razboi, asmin, treesearch
- Heavy path decomposition
- Centroid decomposition
- Longest path decomposition
- Parcurgere Euler
- Descompunere in numar minim de lanturi
- Probleme: tree
- Cod Prufer
- Probleme: New Year and forgotten tree
Flux and related
Flux maxim
- Edmonds-Karp
- Taietura minima
- Probleme: croco, pixels, goods transportation, bilingual
- 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
- Jonker Volgenant
- 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: Little Artem and Graph
