Training path

Vrem sa intocmim o baza de cunostinte fara precendent! Vrem ca aceasta pagina sa contina o lista cat mai completa cu ce trebuie sa stie un olimpic pentru a avea succes. Ajuta-ne si tu!

Cosmin: ar trebui sa facem o lista mai mica cu chestiile importante ca sa ajungi la ONI, ca sa nu se sperie cei ce abia incep.

Algoritmi si tehnici de programare

Matematica

• Inductie matematica
• Algoritmul lui Euclid
• CMMDC binar
• Ciurul lui Erathostene
• Gray code
• Rezolvare de ecuatii liniare modulare
• Teorema mica a lui Fermat
• Teorema chineza a resturilor
• Numere mari: adunare, scadere, inmultire, impartire, radical
• Recurente si exponentiere rapida de matrici (+evaluare rapida a expresiilor folosind exponentiere in timp logaritmic)
• Principiul includerii si excluderii
  • problema cowfood
• Sisteme de ecuatii liniare (Gauss)
  • Teorie:
    • Gaussian elimination
    • Row echelon form
  • Probleme: SGU 275 To xor or not to xor .campion Xor SGU 260 Puzzle UVA 10808 UVA 326 UVA 10014 BColor Laser TC XORing TC Escape the jail Register CEOI 2003 Tunelul groazei SGU 200 TC CoinGame
• Simplex (pur si simplu un hill climbing pe mai multe variabile)
• Floyd's cycle finding
• Combinatorica
  • Permutari, permutari cu repetitii, aranjamente, combinari, Stirling, Catalan, Bell, Fibonacci
  • Trecere de la combinare/permutare la indexul ei si invers
  • Codul Prufer. Numarare de arbori

Geometrie

(computer graphics FAQ)

• Intersectie a doua segmente
• Punct in interiorul unui poligon
  • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
  • http://tog.acm.org/editors/erich/ptinpoly/
• Punct in poligon convex in O(log n)
  • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm#Monotone%20Polygons
• Teorema lui Pick
  • problema copaci
• Aria unui poligon
• Centrul de greutate al unui poligon
• Triangularizare de poligon in O(n^2)
• Intersectia a doua cercuri
• Minimal enclosing circle
• Convex hull
  • http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
  • http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
  • Aplicatie - onion peeling in O(n²)
• Baleiere verticala / radiala
• Rotating calipers
  • problema rubarba
  • problema popandai2
• Intersectie de poligoane convexe
• Intersectie de semiplane (fara dualizare)
  • problema camera
• Dualizare

• thread pe forum

Sortari si cautari

• Shell sort, merge sort, heapsort, quicksort, counting sort, radix sort
• Statistici de ordine
• Cautare binara/ternara si aplicatii
• Hill climbing

Greedy

• Huffman
• Job scheduling

Programare dinamica

• Parantezare optima de matrici
• Cel mai lung subsir crescator O(N*log N)
• Knapsack
  • Knapsack pe biti
• Cel mai lung subsir comun
• Distanta de editare
• Ciclu hamiltonian in O(n² * 2ⁿ)
  • problema adn
• Dinamicile in 3ⁿ
  • explicatie, problema
• Arbore de cautare optim in O(n^2)
• Dinamici pe arbori
• Numarul posibilitatilor de acoperire a unei table cu dominouri
• Memoizare (trading space for time)

Grafuri

• Parcurgeri
  • dfs, bfs, meet in the middle bfs
  • Componente biconexe
  • Componente tare-conexe
  • Sortare topologica
  • Ciclu eulerian
• Drumuri minime
  • Dijkstra (cu heapuri, cu set-uri, cu AINT-uri, cu coada ca pe TC - Cosmin stie)
  • Dijkstra cu costuri mici ;) cum se foloseste la problema car
  • A* has a lot of intuitive appeal for me. If you compare Dijkstra's vs. A*, Dijkstra's is like a puddle of water flooding outwards on a flat floor, whereas A* is like the same puddle expanding on a bumpy and graded floor toward a drain (the target node) at the lowest point in the floor. Instead of spreading out evenly on all sides, the water seeks the path of least resistance, only trying new paths when something gets in its way. The heuristic function is what provides the 'grade' of the hypothetical floor.
    • A* se foloseste foarte mult in industria jocurilor, fiind un algoritm foarte rapid in practica. Un exemplu unde este folosit este jocul de strategie Starcraft.
  • Floyd-Warshall
  • Bellman-Ford
    • De obicei mai simplu de implementat si cam aceeasi viteza ca si Dijkstra cu heapuri
    • Sistem de inegalitati
    • Ciclu de cost mediu minim
• Flux
  • Edmonds-Karp
  • Taietura minima
  • Dinic
  • Flux maxim de cost minim
  • Flux cu capacitati inferioare
  • Circulatii
  • Problema postasului chinez
    • problema traseu
• Arbori
  • Diametrul, centrul unui arbore
  • Testare daca doi arbori sunt izomorfi
  • Cod Prufer
• APM
  • Prim
  • Kruskal
  • Al doilea APM
  • APM in graf orientat
  • Kirchhoff's matrix tree theorem
• Pentru grafuri bipartite: cuplaj maxim, suport minim, multime independenta maxima
• LCA, RMQ, Level Ancestor, Path Decomposition
• Colorari de muchii, graf complet/bipartit/oarecare (teorema lui Vizing)
• Grafuri planare
  • problema count
• Grafuri turneu/ciclu hamiltonian
  • problema plimbare
• Implication graph si 2-SAT
  • problema aladdin

Siruri de caractere

• Hashuri
• KMP
• Siruri de sufixe
  • In timp liniar
• Aho-Corasick

Limbaje formale si automate finite

• Evaluari de expresii aritmetice
• CYK
• Matching with wildcards
• Construirea unui automat care sa accepte un set de cuvinte
• Simplificare de automate
• Echivalenta de automate
• thread pe forum

Teoria jocurilor

• Nim
• Numere Sprague-Grundy
• Min-max
• Alpha-beta

Structuri de date

• Liste, stive, cozi
• Smenul cu deque
• Tabele de dispersie
  • Cuckoo hashing
• Bloom filters
• Skiplists

• Arbori indexati binar
• Cozi de prioritati
  • Heap-uri
  • Mergeable heaps (maxophobic heaps sunt cel mai simple)
  • Pentru costuri intregi mici, un array de liste

• Structuri de multimi disjuncte
• Arbori de intervale
• Tries
• Arbori binari de cautare (treaps, AVL, red-black trees)
• Cautari ortogonale. Quad trees, kD-trees

Diverse

STL (Standard Template Library)

• vector, deque, stack, list
• string
• set, map, hash_map
• pair
• sort
• priority_queue
• bitset
• iteratori

Cautari
** backtracking
** iterative deepening
** branch and bound

Optimizari

• Parsare
• Lucru cu biti
• Brute force
  • dancing links

Lucrul cu memoria

• Cacheuri de momorie
  • problema stramosi
• free lists
  • problema eprubeta

Bulanit

• Randomizare (2-opt, k-opt)
• Constante
• Interpolare Taylor / Gauss pentru formule polinomiale

Smenuri

• Smenu' lui Batog (+ lca in sqrt(n))
• Smenu' lui Mars
  • problema cuburi
• Meet in the middle

Carti utile

• Ioan Tomescu
  • "Probleme de combinatorica si teoria grafurilor" (din care s-a dat la ONI sau lot aproape in fiecare an cate o problema sau mai multe)
  • "Combinatorica si teoria grafurilor"
• Ioan Cuculescu
  • "Olimpiadele Internationale de Matematica ale Elevilor"
• E. A. Morozova, I. S. Petracov, V. A. Skvortov
  • "Olimpiade internationale de matematica"
• "Probleme de matematica traduse din revista sovietica KVANT"
• A. M. Iaglom, I. M. Iaglom
  • "Probleme neelementare tratate elementar"
• Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
  • "Introducere in algoritmi"
• D. E. Knuth
  • "Arta programarii calculatoarelor" ("The Art of Computer Programming")
  • "Concrete Mathematics"
• Jon Bentley
  • "Programming Pearls"
• Steven Skiena
  • "The Algorithm Design Manual"
• W. Rytter
  • "Jewels of Stringology"
• Mark de Berg
  • "Computational geometry"