h1. Training path
h1. Training path....
h2. Algoritmi
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':implica-te/scrie-articole si tu!
* Matematica
** 'Algoritmul lui Euclid':algoritmul-lui-euclid
*** binar
** 'Ciurul lui Erathostene':ciurul-lui-erathostene
** Teorema mica a lui Fermat
** 'Teorema chineza a resturilor':teorema-chineza-a-resturilor
** Rezolvare de ecuatii liniare modulare
** Teorema lui Pick
** 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 al excluderii
** Sisteme de ecuatii liniare (Gauss)
** Simplex (pur si simplu un hill climbing pe mai multe variabile)
** Combinatorica
*** Permutari, permutari cu repetitii, aranjamente, combinari, Stirling, Catalan, Bell, Fibonacci
*** Trecere de la combinare/permutare la indexul ei si invers
*** Numarare de arbori (codul Pruffer)
* Geometrie
** Intersectie a doua segmente
** Punct in interiorul unui poligon
** Punct in poligon convex in $O(log n)$
** Aria unui poligon
** Centrul de greutate al unui poligon
** Triangularizare de poligon in $O(n^2)$
** Intersectia a doua cercuri
** 'Minimal enclosing circle':minimal-enclosing-circle
** Convex hull
** Baleiere verticala/radiala
** Rotating calipers
** Intersectie de poligoane convexe
** Intersectie de semiplane (fara dualizare)
** Dualizare (intersectie de semiplane, diagrame Voronoi)
* Sortari si cautari
** Shell sort, merge sort, heapsort, quicksort, counting sort, radix sort
** Statistici de ordine
** Cautare binara/ternara si 'aplicatii':aplicatii-ale-cautarii-binare
* 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
*** **Cosmin**: In $O(n)$ memorie (cum am dat eu la ginfo), in O(d*n) timp unde d este distanta de editare finala (cum a dat Mars la ONI). Paper beton ce contine ambele si un jmen misto: 'http://www.xmailserver.org/diff2.pdf':http://www.xmailserver.org/diff2.pdf
** Ciclu hamiltonian in $O(n^2^ * 2^n^)$
** Dinamicile in $3^n^$
*** 'explicatie':http://forums.topcoder.com/?module=Thread&threadID=512824&start=0, 'problema':http://www.topcoder.com/stat?c=problem_statement&pm=6678&rd=9998&rm=249548&cr=8547850
** 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)
* Siruri de caractere
** Hashuri
** 'KMP':automate-finite-si-kmp
** Siruri de sufixe
*** 'In timp liniar':suffix-array-liniar
** Aho-Corasick
* Limbaje formale si automate finite
** Evaluari de expresii aritmetice
** 'CYK':http://en.wikipedia.org/wiki/CYK
** Matching with wildcards
** Construirea unui automat care sa accepte un set de cuvinte
** Simplificare de automate
** Echivalenta de automate
* Teoria jocurilor
** Nim
** Sprague-Grundy
** Min-max
** Alpha-beta
*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.
Alta lista 'http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus':http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus
h2. Structuri de date
* Structuri liniare
** Liste, stive, cozi
** Jmenul cu deque
** 'Tabele de dispersie':hashing
** Bloom filters
** 'Skiplists':skiplists
* Structuri arborescente
** Arbori indexati binar
** Heaps
** Mergeable heaps
** Structuri de multimi disjuncte
** 'Arbori de intervale':arbori-de-intervale
** Tries
** Arbori binari de cautare (treaps, AVL, red-black trees)
** Quad trees, kd-trees
* Grafuri
** Parcurgeri
*** dfs, bfs, meet in the middle bfs
*** Componente biconexe
*** Componente tare-conexe
*** Sortare topologica
*** Ciclu eulerian
** Drumuri minime
*** A*, iterative deepening
*** Dijkstra (cu heapuri, cu set-uri, cu AINT-uri, cu coada ca pe TC - Cosmin stie)
*** Dijkstra cu costuri mici ;)
**** 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.
*** 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':taietura-minima
*** Dinic
*** Flux maxim de cost minim
*** Flux cu capacitati inferioare
*** Circulatii
*** Problema postasului chinez
** Arbori
*** Diametrul, centrul unui arbore
*** Testare daca doi arbori sunt izomorfi
*** Cod Pruffer
** APM
*** Prim
*** Kruskal
*** Al doilea APM
*** APM in graf orientat
** Pentru grafuri bipartite: cuplaj maxim, suport minim, multime independenta maxima
** 'LCA':lca-lowest-common-ancestor, RMQ, Level Ancestor, 'Path Decomposition':heavy-path-decomposition
** Colorari de muchii, graf complet/bipartit/oarecare (teorema lui Vizing)
** Grafuri planare
** Grafuri turneu/ciclu hamiltonian
h2. Tehnici de programare (TODO: nume mai bun pentru subcategoria asta)
* 'STL @(Standard Template Library)@':stl
** vector, deque, stack, list
** string
** set, map, hash_map
** pair
** sort
** priority_queue
** bitset
** iteratori
* Optimizari
** Parsare
** Lucru cu biti
* Liste, stive, cozi
* 'Deque':deque-si-aplicatii
* 'Tabele de dispersie':tabele-hash-prezentare-detaliata
** 'Cuckoo hashing':http://en.wikipedia.org/wiki/Cuckoo_hashing
* 'Bloom filters':http://en.wikipedia.org/wiki/Bloom_filter
* 'Skiplists':skiplists
* 'Arbori indexati binar':aib
** 'Aplicatie din Arhiva Educationala':problema/aib
* Cozi de prioritati
** 'Heap-uri':heapuri
** Mergeable heaps (maxophobic heaps sunt cel mai simple)
** Pentru costuri intregi mici, un array de liste
* 'Structuri de multimi disjuncte':problema/disjoint
* 'Arbori de intervale':arbori-de-intervale
* 'Tries':problema/trie
* Arbori binari de cautare ('Treapuri':treapuri, AVL, red-black trees)
* 'Cautari ortogonale. Quad trees, kD-trees':cautari-ortogonale
h2. Algoritmi si tehnici de programare
h3. Matematica
* 'Inductie matematica':http://ro.wikipedia.org/wiki/Induc%C5%A3ie_matematic%C4%83
* 'Algoritmul lui Euclid':algoritmul-lui-euclid
* 'CMMDC binar':http://en.wikipedia.org/wiki/Binary_GCD_algorithm
* 'Ciurul lui Erathostene':ciurul-lui-erathostene
* 'Gray code':coduri-gray
* Rezolvare de ecuatii liniare modulare
* Teorema mica a lui Fermat
* 'Teorema chineza a resturilor':teorema-chineza-a-resturilor
** Probleme: 'eval':problema/eval 'resturi':problema/resturi 'gears in action':http://ipsc.ksp.sk/contests/ipsc2005/real/problems/g.php
* "Numere mari: adunare, scadere, inmultire, impartire, radical":lucrul-cu-nr-mari
* Recurente si exponentiere rapida de matrici (+evaluare rapida a expresiilor folosind exponentiere in timp logaritmic), 'al K-lea termen Fibonacci':problema/kfib
* 'Principiul includerii si excluderii':principiul-includerii-si-excluderii
** Probleme: 'cowfood':problema/cowfood, 'indep':problema/indep, 'frac':problema/frac
* Sisteme de ecuatii liniare (Gauss)
** Teorie:
*** 'Gaussian elimination':http://en.wikipedia.org/wiki/Gaussian_elimination
*** 'Row echelon form':http://en.wikipedia.org/wiki/Row_echelon_form
** Probleme: 'SGU 275 To xor or not to xor':http://acm.sgu.ru/problem.php?contest=0&problem=275 '.campion Xor':http://campion.edu.ro/problems/3/323/xor_ro.htm 'SGU 260 Puzzle':http://acm.sgu.ru/problem.php?contest=0&problem=260 'UVA 10808':http://online-judge.uva.es/p/v108/10808.html 'UVA 326':http://online-judge.uva.es/p/v3/326.html 'UVA 10014':http://online-judge.uva.es/p/v100/10014.html 'BColor':problema/bcolor 'Laser':problema/laser 'TC XORing':http://www.topcoder.com/stat?c=problem_statement&pm=4829&rd=8095&rm=246636&cr=270505 'TC Escape the jail':http://www.topcoder.com/stat?c=problem_statement&pm=7353 'Register CEOI 2003':http://ceoi.inf.elte.hu/probarch/03/register-en.pdf 'Tunelul groazei':problema/tunel 'SGU 200':http://acm.sgu.ru/problem.php?contest=0&problem=200 'TC CoinGame':http://www.topcoder.com/stat?c=problem_statement&pm=6005
* Simplex
* "Floyd's cycle finding":http://en.wikipedia.org/wiki/Cycle_detection
* Combinatorica
** 'Generare de permutari':problema/permutari, permutari cu repetitii, aranjamente, 'combinari':problema/combinari, 'Stirling':problema/stirling, Catalan, Bell, Fibonacci
** Trecere de la combinare/permutare la indexul ei si invers
** 'Codul Prufer. Numarare de arbori':http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
h3. Geometrie
'computer graphics FAQ':http://www.faqs.org/faqs/graphics/algorithms-faq/
'cursuri dupa Computational Geometry: Algorithms and Applications, Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf':http://www.cs.umd.edu/class/spring2007/cmsc754/Lects/754lects.pdf
* Intersectie a doua segmente
* 'Cele mai apropiate puncte dintr-un plan':problema/cmap
* 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':http://www.cut-the-knot.org/ctk/Pick_proof.shtml
** problema 'copaci':problema/copaci
* Aria unui poligon
* Centrul de greutate al unui poligon
* 'Triangularizare de poligon in $O(n^2)$':http://people.csail.mit.edu/indyk/6.838-old/handouts/lec4.pdf
* 'Intersectia a doua cercuri':http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/
* 'Minimal enclosing circle':minimal-enclosing-circle
* Convex hull
** 'Aplicatie din Arhiva Educationala':problema/infasuratoare
** http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
** http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
** Aplicatie - onion peeling in O(n^2^)
* 'Baleiere verticala / radiala':algoritmi-de-baleiere
** baleiere radiala
*** Se da un set S de n punct in plan. Sa se determine cercul de raza R fixata care acopera cat mai multe puncte din S. O(n^2 log n)
*** Se da un set S de n puncte in plan. Sa se gaseasca o dreapta ce trece prin nr maxim de puncte din S. O(n^2^) cu hashuri pt unghiuri sau O(n^2 log n) cu baleiere radiala.
*** Se da un set S de n segmente in plan. Sa se gaseasca o dreapta ce intersecteaza numarul maxim de segmente din S. O(n^2 log n) cu baleiere radiala.
*** 'Construirea grafului de vizibilitate.':http://en.wikipedia.org/wiki/Visibility_graph
* 'Rotating calipers':http://cgm.cs.mcgill.ca/~orm/rotcal.html
** problema 'rubarba':problema/rubarba
** problema 'popandai2':problema/popandai2
* Intersectie de poligoane convexe
* Intersectie de semiplane (fara dualizare)
** problema 'camera':problema/camera
* 'Dualizare (intersectie de semiplane, diagrame Voronoi)':http://infoarena.ro/voronoi
* 'thread pe forum':http://infoarena.ro/forum/index.php?topic=3007.0
h3. Sortari si cautari
* Shell sort, merge sort, heapsort, quicksort, counting sort, radix sort, 'sortare prin comparare':problema/algsort
* 'Statistici de ordine':problema/sdo
* 'Cautare binara':problema/cautbin / ternara si 'aplicatii':aplicatii-ale-cautarii-binare
* Hill climbing
h3. Greedy
* 'Huffman':problema/huffman
* Job scheduling
h3. Programare dinamica
* 'Parantezare optima de matrici':problema/podm
* 'Cel mai lung subsir crescator $O(N*log N)$':problema/scmax
* Knapsack
** Knapsack pe biti
* 'Cel mai lung subsir comun':problema/cmlsc
* 'Distanta de editare a 2 cuvinte':http://en.wikipedia.org/wiki/Levenshtein_distance
* Ciclu hamiltonian in $O(n^2^ * 2^n^)$
** problema 'adn':problema/adn , 'aplicatie in arhiva educationala':problema/hamilton
* Dinamicile in $3^n^$
** 'explicatie':http://forums.topcoder.com/?module=Thread&threadID=512824&start=0, 'problema':http://www.topcoder.com/stat?c=problem_statement&pm=6678&rd=9998&rm=249548&cr=8547850
** 'scara2':problema/scara2
** 'colorare':problema/colorare
** 'zebughil':problema/zebughil
** 'ndap':problema/ndap
** 'cast':problema/cast
** 'carti2':problema/carti2
* 'Arbore de cautare optim in $O(n^2)$':http://www.ics.uci.edu/~dan/class/165/notes/OptBST.html
* Dinamici pe arbori
* 'Numarul posibilitatilor de acoperire a unei table cu dominouri':probleme-de-acoperire-2#problema3
* Memoizare (trading space for time)
h3. Grafuri
* Parcurgeri
** 'DFS':problema/dfs, 'BFS':problema/bfs, meet in the middle bfs
** 'Componente biconexe':problema/biconex
** 'Componente tare-conexe':problema/ctc
** 'Sortare topologica':problema/sortaret
** 'Ciclu eulerian':problema/ciclueuler
* Drumuri minime
** 'Dijkstra':problema/dijkstra (cu heapuri, cu set-uri, cu AINT-uri, cu coada ca pe TC - Cosmin stie)
** 'Dijkstra cu costuri mici ;)':http://www.ginfo.ro/revista/13_6/focus2.pdf cum se foloseste la problema 'car':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':problema/royfloyd
** 'Bellman-Ford':problema/bellmanford
*** De obicei mai simplu de implementat si cam aceeasi viteza ca si Dijkstra cu heapuri
*** Sistem de inegalitati
*** 'Ciclu de cost mediu minim':ciclu-de-cost-mediu-minim
* 'Flux':problema/maxflow
** Edmonds-Karp
** 'Taietura minima':taietura-minima
** 'Dinic':http://www.msri.org/about/computing/docs/magma/html/text1499.htm
** 'Flux maxim de cost minim':problema/fmcm
** Flux cu capacitati inferioare
** Circulatii
** Problema postasului chinez
*** problema 'traseu':problema/traseu
* Arbori
** 'Diametrul, centrul unui arbore':http://online-judge.uva.es/board/viewtopic.php?p=36766&highlight=#36766
** 'Testare daca doi arbori sunt izomorfi':http://online-judge.uva.es/board/viewtopic.php?p=22754&highlight=#22754
** Cod Prufer
* 'APM':problema/apm
** Prim
** Kruskal
** Al doilea APM
** APM in graf orientat
** Kirchhoff's matrix tree theorem
* Pentru grafuri bipartite: 'cuplaj maxim':problema/cuplaj, suport minim, multime independenta maxima
* 'LCA':lowest-common-ancestor, 'RMQ':problema/rmq, Level Ancestor, 'Tree decompositions':tree-decompositions
* Colorari de muchii, graf complet/bipartit/oarecare (teorema lui Vizing)
* Grafuri planare
** problema 'count':problema/count
* Grafuri turneu/ciclu hamiltonian
** problema 'plimbare':problema/plimbare
* {'Implication graph si 2-SAT':2-sat}
h3. Siruri de caractere
* 'Hashuri':problema/strmatch
* 'KMP':automate-finite-si-kmp
* 'Siruri de sufixe':siruri-de-sufixe
** 'In timp liniar':suffix-array-liniar
* 'Z-Algorithm':zalgorithm
* 'Aho-Corasick':http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf .
h3. Limbaje formale si automate finite
* 'Evaluari de expresii aritmetice':problema/evaluare
* 'CYK':http://en.wikipedia.org/wiki/CYK
* Matching with wildcards
* Construirea unui automat care sa accepte un set de cuvinte
* Simplificare de automate
* Echivalenta de automate
* 'thread pe forum':http://infoarena.ro/forum/index.php?topic=3005.0
h3. 'Teoria jocurilor':teoria-jocurilor
* 'Nim':teoria-jocurilor/jocul-nim
* 'Numere Sprague-Grundy':numerele-sprague-grundy
* Min-max
* Alpha-beta
h2. Diverse
h3. 'STL @(Standard Template Library)@':stl
* vector, deque, stack, list
* string
* set, map, hash_map
* pair
* sort
* priority_queue
* bitset
* iteratori
h3. Cautari
* backtracking
* iterative deepening
* branch and bound
h3. Optimizari
* Parsare
* Lucru cu biti
* Brute force
** 'dancing links':http://en.wikipedia.org/wiki/Dancing_Links
h3. Lucrul cu memoria
* Bulanit
** Randomizare (2-opt, k-opt)
** Constante
h2. Harababura (TODO)
* hill climbing
* meet in the middle trick
* 2SAT
* jmenu lui batog (+ lca in $sqrt(n)$)
* jmenu lui mars
* gray code
* matrix tree theorem
* Floyd's cycle finding
* (colored range searching)
* pt bulanit: interpolare taylor / gauss (scos din categoria mate)
* ad hoc
* 'Cacheuri de memorie':http://en.wikipedia.org/wiki/CPU_cache
** problema 'stramosi':problema/stramosi
* 'free lists':http://www.memorymanagement.org/glossary/f.html#free.list
** problema 'eprubeta':problema/eprubeta
h3. Bulanit
* Randomizare (2-opt, k-opt)
* Constante
* Interpolare Taylor / Gauss pentru formule polinomiale
h3. 'Smenuri':multe-smenuri-de-programare-in-cc-si-nu-numai
* Smenu' lui Batog (+ lca in $sqrt(n)$)
** probleme: 'schi':problema/schi,
* Smenu' lui Mars
** problema 'cuburi':http://campion.edu.ro/do_download.php?problem_id=122&type=application/pdf&year=2003&lang=ro
* 'Meet in the middle':meet-in-the-middle
h2. 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 (TODO: carti)
* Morzova (TODO: carti)
* 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"
