Principiile cercului de pregătire pentru lot liceu

Generalități

Acest cerc se adresează elevilor care aspiră la calificarea în lotul de seniori. De aceea, vă recomand să participați dacă aveți experiență de concurs și v-ați calificat la ONI în anii recenți.

Programa cercului este construită în jurul programei pentru Baraj ONI (care include toată materia de clasele 9-12). Ocazional vom coborî un nivel sau două ca să vorbim despre noțiuni „cunoscute”, dar în practică uitate sau implementate ineficient. În plus, vom pune accent pe ingineria programării: cum să scriem cod clar și corect, care trece toate testele de la prima rulare (da, aceasta trebuie să fie norma, nu o surpriză plăcută ocazională).

Concursul de admitere

Pentru admiterea la cerc vom da un concurs, probabil în primul weekend după începerea școlii, probabil cu două probleme de rezolvat în 3 ore. Problemele vor fi undeva la nivel de ONI clasa a 9-a sau OJI clasa a 10-a. Voi căuta probleme de dificultate medie ca idee și ca implementare. Intenția este să selectez elevi care au baze solide, fără să cunoască deja (nu neapărat) 90% din materia cercului — de acolo începe misiunea mea. Dacă aceste probleme vă vor da de furcă, probabil participarea la acest cerc nu v-ar face plăcere: ați pierde ritmul, ați sări teme etc.

Despre dopaj

Cînd rezolvăm o problemă, este bine să avem unelte. Arsenalul de algoritmi și structuri de date este important și vă încurajez să asimilați cît puteți. Dar doar dopajul este insuficient.

Prin „dopaj” înțelegem căutarea primei soluții care descompune problema în cărămizi cunoscute, abandonînd orice adaptare specifică problemei date. Dacă vă axați doar pe dopaj, riscați să deveniți uriași cu picioare de lut. Bazele sînt esențiale. Mereu vor exista probleme de bază (numite și „ad hoc”, core etc.), cum ar fi Baba Oarba, GP, Hipersimetrie, Registers, Sniper, Xor. Dacă tot ce știm sînt treap-uri și arbori de intervale persistenți, vom uita să rezolvăm probleme pe care un elev cu o gîndire naturală și robustă le rezolvă imediat.

Spiritul Nerdvana este să formăm informaticieni compleți, care nu vin cu mitraliera la o luptă de cuțite, nu implementează treapuri la olimpiada pe școală și nu se tem să adapteze uneltele din arsenal la nevoile problemei.

De asemenea, scorul mai mare la olimpiadă nu este un scop în sine, dar va fi o consecință pozitivă a acestui cerc. Ocazional vom petrece cîteva minute pe subiecte care vă fac informaticieni mai buni, fără să fie neapărat în programa pentru olimpiadă. Exemple: analiza lexicală prezintă un mod corect de a trata problemele cu intrare de tip șir de caractere; automatele finite ușurează mult înțelegerea algoritmului KMP.

Teme

Fiecare lecție va avea o temă: o problemă de rezolvat pe Codeforces / Kilonova / etc. Majoritatea temelor vă vor cere să adăugați doar una-două observații peste noțiunile discutate în clasă.

Temele sînt modul meu de a mă asigura că implementați cel puțin o dată algoritmii și structurile de date pe care le discutăm. Vă încurajez să lucrați considerabil mai mult decît acest minim necesar! Notele de curs includ mai multe probleme decît acoperim în clasă. Încercați să le rezolvați pe toate.

Temele sînt individuale. Dacă totuși după 60 de minute de gîndire nu aveți soluția, este OK să vorbiți cu colegii sau să citiți editorialul sau surse corecte. În orice caz, implementarea trebuie să fie individuală și de la zero. Nu vă furați căciula singuri!

Code review

Temele îmi dau ocazia să vă citesc codul. Acesta este un obicei indispensabil, pe care din păcate prea mulți profesori îl ignoră. Ei nu văd niciodată codul pe care îl scrie elevul, ci doar se bucură că elevul ia Accepted pe vreun site. De aceea, mulți elevi preiau un stil de codare de te miri unde, din supa culturală a programării competitive. Acest stil duce la programe încîlcite, care pot conține buguri nedetectabile. Este un mod gratuit și absolut evitabil de a rata un concurs.

Filozofia mea este că, la nivelul de ONI și Baraj ONI la care operează acest cerc, ideile problemelor nu sînt principala dificultate. Desigur, la loturi și la concursuri internaționale nivelul este altul. Fiecare dintre noi s-a gîndit uneori 2-3 zile o problemă de lot și tot n-a știut să o rezolve. Dar la ONI și la Baraj ONI contează mai mult capacitatea de a exprima clar, în cod, niște idei teoretice de dificultate medie. Am constatat că majoritatea elevilor nu pierd puncte pentru că n-au știut un anume algoritm sau o anume structură de date, ci pentru că n-au reușit să le exprime corect în cod și s-au lovit de buguri sau de ineficiență (TLE).

De aceea, pentru fiecare temă veți primi feedback individual pe marginea programului: ce este bine și ce aș schimba eu ca să reduc riscul de complicații și buguri. Mă aștept să țineți cont de acest feedback și să vă însușiți schimbările de stil pe care vi le recomand (exemple: fără funcții de 80 de linii; fără variabile cu nume criptice). Dacă veniți la cerc ca să creșteți ca programatori, atunci lăsați-mă pe mine să decid cum se va întîmpla asta, nu alegeți doar ce credeți voi că este suficient. 🙂 Două programe care rezolvă aceeași problemă pot diferi radical ca lizibilitate, robustețe, ușurință a implementării.

Depanare și alte elemente de inginerie software

Un program scris, dar care nu merge, nu este „99% gata, am doar un bug”. Depanarea poate ocupa între 0% și 99% din timpul de implementare, în funcție de calitatea codului. Iar la final, tot ce rămîne este punctajul.

Bugurile nu sînt o pedeapsă divină. Sînt o parte normală din viața de programator. Ce contează este că avem mecanisme prin care (1) să le reducem pe cît se poate frecvența și (2) să le depistăm sistematic și rapid cînd apar. Vom învăța aceste mecanisme în primele lecții, apoi le vom regăsi aplicate în programele pe care le vom citi de-a lungul anului.

Din experiența anilor trecuți, la fiecare temă cam 2-3 elevi nu reușesc să ducă problema la capăt. Aceasta este OK, și este parte din datoria mea ca instructor să vă înarmez cu uneltele necesare. Dar și voi trebuie să vă faceți treaba! Mă aștept să trimiteți surse lizibile, ca eu să nu pierd 30 de minute încercînd să înțeleg ce face programul vostru.

Voi considera tema făcută parțial dacă sursa trece toate testele mici. Voi considera nefăcută o temă a cărei sursă pică pe teste mici. Un test mic este un ajutor prețios în izolarea unui bug. Este parte din acest cerc să vă obișnuiți să vă depanați programele.

Raportul cu anul trecut

Pentru elevii care au participat la cercul de anul trecut și se întreabă dacă să revină și anul acesta: din păcate, nu vă pot da un răspuns înainte să văd componența grupelor. Îmi dau seama că avem o problemă circulară. 🥲 Hm, oare de aceea întrunirile noastre se numesc „cerc”?

Cercul se axează pe materia de baraj descrisă mai jos. Sper să putem urca ocazional la nivel de lot (exemple: șiruri de sufixe și alți algoritmi pe stringuri; structuri de date persistente; fluxuri de cost minim). Dar trebuie să mă asigur că toți elevii au bazele pe care le-am parcurs și cu voi în anul trecut.

De aceea, singura programă pe care o pot garanta este 90% identică cu cea din anul trecut. Voi căuta probleme noi pentru teme și, posibil, pentru cursuri. În special, voi încerca să includ mai puține probleme educaționale și mai multe probleme reale de la baraje și loturi din ultimii 2-3 ani.

Avertismente

Este bine să nu ne îmbătăm cu apă rece: nici voi că participați la un curs de elită și nici eu că am elevi de top. Dacă doar stăm unii în prezența celorlalți nu rezolvăm nimic. Trebuie să urmăm regulile de mai sus.

De aceea, la Nerdvana avem un sistem de trei avertismente. După al treilea avertisment, trecem la un ultimatum cînd, de regulă, cerem să vorbim cu părintele. Apoi, ne despărțim prieteni.

Din experiența anilor trecuți, principala sursă de avertismente vor fi temele nefăcute (temele făcute parțial nu generează avertismente, ci doar vă știrbesc din glorie). Fiecare temă nefăcută înseamnă un avertisment. Facem excepții rare pentru motive bine întemeiate: concursuri, pregătiri pentru Bac și facultăți (la clasa a 12-a) etc.

Programa

Bune practici în programare

• cod curat și cod spaghetti, incluzînd
  • designul codului pentru claritate
  • invarianți de buclă
  • programarea prin contract
• adaptarea la nevoile problemei (prin contrast cu dopajul / rețetele)
• depanarea programelor, incluzînd
  • metoda „forță brută + generator + rulare în buclă”
  • generatoare de vectori, de permutări, de arbori, de grafuri

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)
  • arbori Fenwick 2D
• arbori de segmente („aint”)
  • construcție în $\mathcal{O}(n)$
  • actualizări punctuale, implementare iterativă
  • actualizări pe interval, implementare recursivă
    • nou actualizări pe interval, implementare iterativă
  • căutare binară
• structuri de date echilibrate
  • treaps
  • exemple de alte structuri (skip lists, arbori roșu-negru etc.)
  • comparație cu structurile din STL și PBDS
• 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
• bit hacks (compactarea variabilelor, logaritm în baza 2, popcount)

Metode de programare

Baze necesare: programare dinamică.

• probleme core („ad-hoc”)
• descompunere în radical
  • evitarea împărțirilor
  • alegerea mărimii blocurilor cînd operațiile au costuri inegale
• metode pentru probleme de interogare + actualizare
  • sortarea operațiilor
  • algoritmul lui Mo
  • simularea ștergerilor cu un cost extra de $\mathcal{O}(\log n)$ („aint pe timp”)
• evitarea duplicării codului prin oglindirea/rotirea datelor
• tehnica meet in the middle
• analiză sintactică (cu gramatici)
• 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
• algoritmul lui Euclid extins
• funcția Möbius
  • principiul includerii și excluderii expus rapid, doar ca suport
• exponențiere prin ridicare la pătrat
  • aplicabilă și la permutări, matrice etc.
  • exponențiere de permutări în $\mathcal{O}(n)$ prin descompunere în cicluri
  • exponențiere în $\mathcal{O}(1)$ cu precalculare în $\mathcal{O}(\sqrt{n})$
• iterarea prin toți divizorii unui număr
• inverse modulare
• Teorema chineză a resturilor

Șiruri de caractere

Șirurile nu mai sînt în programă, dar anumiți algoritmi au aplicabilitate generală.

• sortare ternară
• hashing; rolling hash; căutare cu metoda Rabin-Karp
  • paradoxul zilei de naștere
• trie

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
• arbori parțiali minimi
• acoperire minimă cu noduri
• recurențe pe arbore
• tehnica small-to-large
• heavy-light decomposition
• descompunere în centroizi

Ultimele două subiecte depășesc programa, dar sînt tehnici foarte puternice și generale.

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
  • algoritmul lui Dial
  • 0-1 BFS
  • tratarea costurilor în noduri (exemplu: Regate)
• drumuri și circuite euleriene
• 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
  • algoritmul push-relabel
  • flux maxim de cost minim

Geometrie computațională

• deziderate practice: evitarea împărțirilor, a erorilor de precizie a cazurilor particulare
• puncte, vectori, produse, unghiuri, drepte
• orientare, determinanți
• posibil: dualitatea punct-dreaptă
• Teorema lui Pick
• algoritmi
  • baleiere
  • înfășurătoarea convexă, convex hull trick
  • șublerul rotitor

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

Miscellanea

În limita timpului, putem explora cîteva dintre subiectele de mai jos (voi alegeți).

• stringuri
  • căutare cu automate finite
    • noțiuni teoretice despre automatele finite
  • căutare cu metoda Knuth-Morris-Pratt
  • funcția Z
  • arbori de sufixe
  • șiruri de sufixe
    • vectorul LCP (longest common prefix)
  • algoritmul lui Manacher
• criptografie
  • elemente de aritmetică modulară
  • algoritmi de criptare și semnare
• algoritmi pentru jocuri logice
  • euristici statice
  • alfa-beta
  • Proof Number Search
  • Monte Carlo Tree 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
• compresia datelor
• analiză lexicală și sintactică (parsare)
• sisteme de control al versiunilor (git etc.)
• noțiuni de programare orientată pe obiect (clase, interfețe etc.)
• noțiuni de design software (testare și altele)
• 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.