Training path

La problemele se adauga cele gasite pe infoarena la tag-urile respective.

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
• 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: pq, distincte, calafat, hapsan, undo
• 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
  • Arhiva Educationala
  • Aho-Corasick, smen pentru operatii de insert si erase
  • Probleme: rk, xormax, CF 710 F, KC, seti
• 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
  • Probleme: biomech, euclid, matrice3, zodiac
• 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
• Cautari ortogonale. Quad trees, kD-trees
  • Probleme: imagine, grau
• Wavelet Matrix
  • Probleme: qxy
• Van Emdge Boas tree
• Scape-goat Tree

Matematica

• Inductie matematica
  • Probleme: borcane
• 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
• 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
  • Mixed radix
    • Probleme: POLYEVAL
  • Smenul cu divide et impera
    • Probleme: CF 438E, CF 553E, Jetpack
• Eliminare Gaussiana
  • Probleme: network, CF 446D, switch5
  • Determinant: afterparty
  • Rangul matricei
  • Inversa matricei: Por Costel si Bujor
• Recurenta liniara
  • Rezolvarea unei recurente liniare
    • Probleme: CF 446C
  • Exponentiere de matrice
    • In general este de ajuns
  • Algoritmul lui Kitamasa
    • Teorema Cayley-Hamilton
    • Explicatie
  • Algoritmul Berlekamp–Massey pentru recurenta de ordin minim al unui sir
    • Calcularea determinantului
• Divizibilitate
  • Probleme: armonica
• Algoritmul Rabin Miller
  • Probleme: dk, Four Divisors
• Simplex
  • Duality
• Floyd's cycle finding
  • Probleme: reactor
• 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
  • Numarul lui Catalan
    • Triunghiul lui Catalan
    • Probleme: permutare4, colors
  • Teorema lui Lucas
    • Probleme: showroom, jap2
  • Teorema lui Wilson:
    • E-maxx
    • Probleme: jap2
  • Numerele lui Stirling
    • Problemele: ex, xnumere
  • 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
    • Probleme: perm3, perm5, nkperm
• Mobius Function
• Probabilitati
  • Expected value: Tequila, Sms, Expected Velea, Albume, Diapazon
  • Ballot theorem
  • Markov chains
    • Probleme: Humpty Dumpty, Random Run
• Principiul includerii si excluderii
  • Probleme: cowfood, indep, frac, CF 451E, light2, trickortreat
• 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
    • Probleme:
    • Meet in the middle BFS
      • Probleme:
    • Lex BFS
  • Ciclu eulerian
    • Probleme:
    • Teorema BEST
  • Componente biconexe
    • Probleme:
  • Componente tare-conexe
    • Probleme:
    • 2-SAT
      • Probleme:
  • Sortare topologica
    • Probleme:
  • Dominator Tree

• Drumuri minime
  • Dijkstra
    • Probleme:
    • Dial's method for small costs
    • Dijkstra cu costuri mici
      • Probleme: car
  • Bellman-Ford
    • Probleme:
  • Roy-Floyd
    • Probleme:
  • SPFA
  • Sistem de inegalitati
  • Ciclu de cost mediu minim

• Colorare

• Grafuri planare
  • Probleme: count

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

• Clica maxima
• Cactus graf
• Gomory-Hu Tree
• Pseudo-Forest

Arbori

• Diametrul unui arbore
• Lowest Common Ancestor
  • Probleme:
  • Tarjan offline
  • Schieber Vishkin
  • Doubling
• Izomorfism de arbori
  • RNG Hash
• Smen 2 DFS-uri
  • Probleme:
• Heavy path decomposition
• Cod Prufer

Flux and related

Flux maxim

* Edmonds-Karp
** Probleme:
* Taietura minima
* Dinic
* Push-relabel
* Flux maxim de cost minim
** Probleme:
* Flux cu capacitati inferioare
* Circulatii
* Problema postasului chinez
** Probleme: traseu

Cuplaj

• Cuplaj maxim de cost minim
  • Probleme:
• Suport minim
  • Probleme:
• Jonker volgenant
• Algoritmul ungar
• Dilworth's theorem
• Konig's theorem
• Hall's marriage theorem
• Algoritmul lui Blossom
• Tutte Matrix

APM

• Prim
• Kruskal
  • Probleme:
• Al doilea APM
• APM in graf orientat
• Arborescenta
• APM de diametru minim
• APM cu grade restrictionate
• Kirchhoff's matrix tree theorem