Traseu de învățare — Baraj gimnaziu

Barajul de gimnaziu este puntea dintre gimnaziu și liceu. Aici ai trecut deja prin tot ce înseamnă vectori, matrice, structuri liniare și generări — acum primești pachetul de tehnici care, până ieri, păreau „de liceu": operații pe biți, recursivitate adevărată, flood-fill, algoritmul lui Lee, Square Root Decomposition și prima ta programare dinamică. E traseul celor care nu se mulțumesc cu materia clasei, ci vor să intre în liceu deja gândind ca un olimpic.

Harta nivelurilor

Barajul de gimnaziu sare direct în Nivel 5 — Algoritmi clasici și atinge Nivel 7 — Performanță.

1. Nivel 5 — Algoritmi clasici: recursivitate, fill/Lee, programare dinamică.
2. Nivel 7 — Performanță: Square Root Decomposition.

Presupune ca date deja stăpânite tot Nivelul 1–4 (clasele V–VIII), inclusiv extensiile naționale (coadă, deque, biți la nivel de bază).

Traseul pe capitole

Toate temele de mai jos formează un singur capitol — Baraj — și sunt extensii peste întreaga materie de gimnaziu. Ordinea recomandată de învățare:

Operații pe biți

• Ce înveți / de ce contează: AND, OR, XOR, shift, setarea/ștergerea unui bit, măști. Înveți să reprezinți o mulțime mică drept un singur număr.
• Deblochează: DP-ul pe stări exponențiale (bitmask) și indicatorul lui Euler.

Indicatorul lui Euler

• Ce înveți / de ce contează: câte numere mai mici decât n sunt prime cu n, prin descompunere în factori primi. Leagă divizibilitatea de combinatorică.
• Deblochează: aritmetica modulară avansată și problemele de teorie a numerelor de la concurs.

Difference Arrays 2D

• Ce înveți / de ce contează: actualizezi un dreptunghi întreg dintr-o matrice în O(1) și aplici toate actualizările cu o sumă parțială 2D la final. Extensia naturală a difference arrays 1D.
• Deblochează: probleme de „adaugă pe zonă, întreabă la final" pe matrice mari.

Recursivitate

• Ce înveți / de ce contează: caz de bază, apel recursiv, stiva apelurilor. Înveți să rezolvi o problemă apelând-o pe ea însăși, pe instanțe mai mici.
• Deblochează: flood-fill, backtracking, divide et impera și DP-ul (toate sunt recursivitate cu un strat în plus).

Algoritmul de fill

• Ce înveți / de ce contează: umpli o zonă conexă dintr-o matrice (flood-fill), recursiv sau cu coadă. Marchezi „tot ce e legat".
• Deblochează: numărarea componentelor / zonelor — pas direct spre BFS/DFS pe grafuri.

Algoritmul lui Lee

• Ce înveți / de ce contează: distanța minimă pe o grilă, parcurgere în val cu coada (BFS pe matrice). Cel mai des întâlnit „drum minim" de gimnaziu.
• Deblochează: BFS-ul pe grafuri din liceu — Lee este BFS pe o grilă.

Square Root Decomposition

• Ce înveți / de ce contează: împarți vectorul în blocuri de mărime ~√n ca să răspunzi la interogări și actualizări mai rapid decât liniar. Primul tău compromis inteligent timp/structură.
• Deblochează: Fenwick/Segment Tree și algoritmul lui Mo din liceu — aceeași idee, dusă mai departe.

Programare dinamică

• Ce înveți / de ce contează: stări, tranziții, inițializare; rezolvi o problemă reținând rezultatele subproblemelor. Lecția-punte „stări și tranziții" îți dă tiparul de gândire.
• Deblochează: tot DP-ul de liceu (rucsac, numărări, DP pe arbori, bitmask) — cea mai importantă temă de la concurs.

Borne / checkpoints

• După biți + Euler: lucrezi cu măști de submulțimi și calculezi indicatorul lui Euler prin factorizare.
• După recursivitate + fill + Lee: numeri zonele conexe dintr-o matrice și afli distanța minimă pe o grilă cu obstacole.
• După Square Root Decomposition: răspunzi la interogări de tip „suma pe interval cu actualizări" mai rapid decât în O(n) per întrebare.
• După DP: rezolvi o problemă de tip rucsac sau de numărare a căilor pe o grilă — exact ce cere un baraj de gimnaziu.

Traseul olimpicului

Barajul este deja traseul olimpicului: nu există „minim" aici, totul e extensie. Strategia corectă: stăpânește întâi recursivitatea (fără ea, fill/Lee/DP rămân magie), apoi flood-fill + Lee (puntea spre grafuri), și abia la final programarea dinamică, tema cu cel mai mare randament la concurs. Square Root Decomposition îți deschide ușa structurilor avansate de liceu. După baraj, treci direct și fără frică la clasa a IX-a.

Capcane de parcurs

• Sari la DP fără recursivitate solidă. DP-ul e recursivitate cu memorie; dacă arborele de recursie nu îți e clar, stările și tranzițiile vor părea aleatoare. De aceea recursivitatea vine înaintea DP-ului în traseu.
• Înveți Lee mecanic, fără să vezi că e BFS. Dacă-l tratezi ca „o rețetă de matrice", ratezi legătura cu grafurile din liceu. Roadmap-ul îl prezintă explicit ca parcurgere în val.
• Tratezi biții ca pe un truc izolat. Măștile de biți sunt limbajul DP-ului pe stări exponențiale; învață-le ca pe „mulțimi compacte", nu ca pe operatori ciudați.