infoarena informatica de performanta

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
  • 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, reduceri, 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, 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

• General ideas
• E-maxx
• An awesome list for competitive programming
• Algowiki
• 1