Această programă este construită în jurul cunoștințelor cerute în anii trecuți la barajele ONI și, în mai mică măsură, la loturi și la ONI clasele 11-12. Ocazional vom relua noțiuni considerate cunoscute pentru a corecta diverse implementări ineficiente sau neelegante care plutesc prin supa culturală.
Pentru elevii care au participat anul trecut și iau în calcul să participe și anul acesta, diferențele sînt:
- O ordonare mai bună a materiei. Anul trecut am construit programa din mers, studiind problemele de la concursuri. Anul acesta o vom parcurge mai sistematic.
- Subiecte noi, marcate cu NOU mai jos.
- Vom lăsa problemele rezolvate anul trecut ca studiu individual și vom căuta probleme noi.
- Exigențele vor fi mai mari. Voi da avertismente nu doar pentru teme nefăcute, ci și pentru teme care nu țin cont de feedbackul anterior (nume irelevante pentru variabile, programare nestructurată etc.).
Bune practici în programare
- cod curat și cod spaghetti, incluzînd
- invarianți de buclă
- programarea prin contract
- adaptarea la nevoile problemei (prin contrast cu cod pictat și apeluri la STL)
- depanarea programelor, incluzînd
- metoda „forță brută + generator + rulare în buclă”
- generatoare de vectori, de permutări, de arbori, de grafuri
Rudimente de GNU/Linux și Bash
- măsurarea timpului și a memoriei
- piping și redirecționarea ieșirii
- rularea în buclă a două programe pentru compararea rezultatelor
- alte unelte:
grep,cut, diff,awk,sed,bc,factor, generarea de numere aleatorii
Structuri de date
Baze necesare: vectori, liste, stive ordonate, structuri de mulțimi disjuncte, preferabil arbori Fenwick.
- arbori Fenwick („aib”)
- construcție în \(\mathcal{O}(n)\)
- actualizări punctuale
- actualizări pe interval
- căutare binară în \(\mathcal{O}(n)\)
- aflarea unei valori punctuale în \(\mathcal{O}(1)\) amortizat
- alte funcții decît adunarea (exemplu: bitset și OR)
- funcții neinversabile (exemplu: max)
- NOU funcții neinversabile și interogări pe interval (Stack Overflow)
- NOU arbori 2D
- arbori de segmente („aint”)
- construcție în \(\mathcal{O}(n)\)
- actualizări punctuale, implementare iterativă
- actualizări pe interval, implementare recursivă
- NOU căutare binară
- heaps, cazuri interesante
- scăderea cheii (utilă în algoritmul lui Dijkstra)
- stivă ordonată, cazuri interesante
- ca suport pentru RMQ (cu ordonarea interogărilor, în \(\mathcal{O}(\log n)\))
- pe calea curentă din arbore, menținută pe durata DFS-ului
- structuri de mulțimi disjuncte, cazuri interesante
- șmenul lui Mars peste vectorul de mulțimi disjuncte
Metode de programare
Baze necesare: programare dinamică.
- probleme core („ad-hoc”)
- descompunere în radical
- evitarea împărțirilor
- alegerea mărimii bucăților cînd operațiile au costuri inegale
- metode pentru probleme de interogare + actualizare
- sortarea operațiilor
- algoritmul lui Mo
- NOU simularea ștergerilor cu un cost extra de \(\mathcal{O}(\log n)\) („aint pe timp”)
- evitarea duplicării codului prin oglindirea/rotirea datelor
- programare dinamică; exemple concrete cînd le întîlnim în probleme
Matematică
- combinatorică
- permutări și combinări, cu și fără repetiții: ranking, unranking,
next() - calculul semnului unei permutări
- permutări și combinări, cu și fără repetiții: ranking, unranking,
- NOU funcția Möbius
- exponențiere prin ridicare la pătrat
- NOU exponențiere în \(\mathcal{O}(1)\) cu precalculare în \(\mathcal{O}(\sqrt{n})\)
- aplicabilă și la permutări, matrice etc.
- exponențiere de permutări în \(\mathcal{O}(n)\) prin descompunere în cicluri
- iterarea prin toți divizorii unui număr
- bit hacks (logaritm în baza doi, popcount)
- inverse modulare
- NOU Teorema chineză a resturilor
- altele, după nevoi
Șiruri de caractere
- sortare ternară
- hashing; rolling hash; căutare cu metoda Rabin-Karp
- paradoxul zilei de naștere
- căutare cu automate finite
- noțiuni teoretice despre automatele finite
- căutare cu metoda Knuth-Morris-Pratt
- NOU funcția Z
- trie, arbori de sufixe
- șiruri de sufixe
- vectorul LCP (longest common prefix)
- NOU algoritmul lui Manacher
Arbori
Baze necesare: reprezentare, DFS.
- reprezentare prin vectori de părinți
- reprezentare („parcurgere”) Euler; aplicații cu interogări + actualizări
- test de strămoș („este \(u\) strămoșul lui \(v\)?”)
- LCA (lowest common ancestor)
- algoritmul cu reprezentare Euler
- algoritmul offline (Tarjan)
- descompunere în radical
- binary lifting cu \(\mathcal{O}(\log n)\) pointeri per nod
- binary lifting cu 2 pointeri per nod
- distanțe în arbore
- acoperire minimă cu noduri
- recurențe pe arbore
- heavy path decomposition
Grafuri
Baze necesare: reprezentare, DFS, BFS, conexitate.
- BFS și DFS: observații teoretice, culori, timpi de vizitare, clasificarea muchiilor
- BFS pe graf implicit (exemplu: Invesort)
- DFS iterativ (cînd memoria este o problemă)
- sortare topologică (doi algoritmi)
- componente tare conexe (doi algoritmi)
- graful componentelor
- 2-SAT
- componente biconexe, punți, puncte de articulație
- distanțe în grafuri; algoritmii lui Dijkstra și Bellman-Ford
- tratarea costurilor în noduri (exemplu: Regate)
- grafuri bipartite
- cuplaje
- teorema lui Kőnig, acoperire minimă, set independent maxim
- fluxuri
- elemente de teorie: Teorema flux maxim – tăietură minimă
- algoritmi bazați pe drumuri de creștere: Ford-Fulkerson, Edmonds-Karp, Dinitz
- NOU algoritmul push-relabel
- flux maxim de cost minim
Geometrie computațională
- deziderate practice: evitarea împărțirilor, a erorilor de precizie a cazurilor particulare
- teorie: puncte, vectori, produse, unghiuri, drepte
- orientare, determinanți
- NOU dualitatea punct-dreaptă
- algoritmi
- înfășurătoarea convexă
- șublerul rotitor
Miscellanea
Un subset din subiectele de mai jos, posibil și altele.
- criptografie
- elemente de aritmetică modulară
- algoritmi de criptare și semnare
- algoritmi pentru jocuri logice
- euristici statice
- alfa-beta
- proof number search
- tabele de finaluri
- servere și site-uri web
- anatomia unui request HTTP
- servere HTTP (sau de email etc.)
- baze de date
- nivelurile de cod ale unui site web
- caching
- backup
- NOU compresia datelor
- NOU analiză lexicală și sintactică (parsare)
- NOU sisteme de control al versiunilor (git etc.)
- NOU noțiuni de programare orientată pe obiect (clase, interfețe etc.)
- NOU noțiuni de design software (testare și altele)
- NOU criptomonede
Discuții filozofice
Ca mici intermezzouri în alte subiecte sau ca dialoguri mai ample:
- Olimpiada nu este scopul suprem.
- Minte sănătoasă în corp sănătos.
- Cariera academică și cariera în industrie.
- Viața la facultate în România, în afara României.
- Software liber, libertăți digitale.
- Abordarea concursurilor.