infoarena informatica de performanta

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, 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
  • 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: zoo, 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
  • Determinarea punctelor de articulatie online
• Trie
  • Arhiva Educationala
• Cozi de prioritati
  • Heap-uri
    • Probleme: cezar, procesor, bleach, sao, dlboss
  • 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
  • Alta idee, triaj
• 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
  • 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
• 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, 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
  • Factorizare LU
  • Tridiagonal matrix algorithm
    • Probleme: Simple Calculations, sms
• Recurenta liniara
  • Rezolvarea unei recurente liniare
    • Probleme: CF 446C
  • Exponentiere de matrice
  • 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, 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
    • 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
  • Formula lui Cayley
    • Probleme: zapezi2
  • Trecere de la combinare/permutare la indexul ei si invers
    • Probleme: perm3, perm5, nkperm
  • Reprezentanti in clase de echivalenta
    • Problemele: salaj, Bracket Subsequences, DSUBSEQ
• 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
  • 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: grarb, sate, cifre4, berarii2
  • Stramosi in timp constant
    • Probleme: spiridusi
  • Meet in the middle BFS: POSLOZI
  • Lex BFS
  • DFS cu baleiere: tradare
• 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
  • 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
• Lovasz Toggle

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: egal, rafaela, metro
• Centroid decomposition
  • Probleme: simulare, ecotraseu, treemis
• Longest path decomposition
• Parcurgere Euler
  • Probleme: maimute, arbfind, treesmen, arbore
• Descompunere in numar minim de lanturi
  • Probleme: tree
• Cod Prufer
  • Probleme: New Year and forgotten tree

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
• Aho-Corasick
  • Probleme: rk, xormax, CF 710 F, KC, seti
  • 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

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
• Cel mai lung subsir comun
• Distanta de editare a 2 cuvinte
  • Probleme: note
• Dincamici pe biti
  • Probleme: ciclu hamiltonian de cost minim, coins, sobo, morcovi, poly 
• Dinamici in 3ⁿ
  • Probleme: scara2, colorare, zebughil, ndap, cast, carti2
• Dinamici pe arbori
  • Probleme: color2, sediu, arb2
• Memoizare
  • Probleme: alpin, joc13, bila, maxpal
• Metode de optimizare
  • Functii unimodale'
    • Probleme: IOI 2016 - Aliens
  • Probleme: nucleulvaloros2, euro, costsq
• 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
• Sum over subsets
• Hirschberg trick
  • Probleme: ghiozdan
• Numere pentagonale
  • Probleme: echival2, crescator2