Traseu de învățare — Clasa a X-a

Clasa a X-a este anul algoritmilor clasici. Pleci de la șiruri de caractere și structuri de date liniare (stivă, coadă, deque, liste), stăpânești STL-ul complet (de la pair la priority_queue, set, map, bitset), apoi intri în inima informaticii de concurs: recursivitate, divide et impera și — la extensia națională — backtracking, geometrie și programare dinamică. Până la final nu mai rezolvi probleme cu o singură tehnică, ci construiești algoritmi din mai multe idei combinate.

Harta nivelurilor

Clasa a X-a finalizează Nivel 4 — Structuri și generări și acoperă tot Nivel 5 — Algoritmi clasici.

1. Nivel 4 — Structuri și generări: stringuri, structuri liniare, STL complet.
2. Nivel 5 — Algoritmi clasici: recursivitate, divide et impera, backtracking, geometrie, programare dinamică.

Traseul pe capitole

1. Șiruri de caractere

• Ce înveți / de ce contează: string, funcții, parcurgeri, frecvențe, prefixe/sufixe, palindroame, căutări. Consolidare în C++ a prelucrării de text.
• Deblochează: algoritmii pe șiruri și problemele de parsare.

2. Structuri de date liniare

• Ce înveți / de ce contează: stiva, coada, algoritmul lui Lee, deque, liste simplu/dublu înlănțuite. Înveți când folosești fiecare.
• Deblochează: BFS-ul, deque-ul monoton și structurile dinamice; lecția-punte „când folosim fiecare structură" e ghidul de decizie.

3. STL

• Ce înveți / de ce contează: pair, vector, list, deque, queue, priority_queue, stack, set/multiset, map, bitset. Trusa standard, cu complexitățile ei.
• Deblochează: aproape orice soluție eficientă; priority_queue și map apar în grafuri, Greedy, DP. Lecția-punte despre complexități te ferește de alegeri lente.

4. Numere mari

• Ce înveți / de ce contează: reprezentare, adunare, scădere, înmulțire/împărțire cu un număr natural. Calcul exact dincolo de tipurile native.
• Deblochează: combinatorica cu rezultate uriașe și problemele „afișați numărul exact".

5. Combinatorică și modulară

• Ce înveți / de ce contează: numărarea submulțimilor/permutărilor/aranjamentelor/combinărilor, parantezări, partiții, număr de ordine, aritmetică modulară, invers modular pentru modul prim.
• Deblochează: problemele de numărare modulo și DP-urile combinatoriale.

6. Recursivitate

• Ce înveți / de ce contează: funcții recursive, caz de bază, apel recursiv, stiva apelurilor, relații de recurență. Lecția-punte: desenarea arborelui de recursie.
• Deblochează: divide et impera, backtracking și DP — toate sunt recursivitate disciplinată.

7. Divide et Impera

• Ce înveți / de ce contează: împarți problema, rezolvi subproblemele, combini rezultatele, exemple clasice (căutare binară, merge sort).
• Deblochează: gândirea „sparge și combină" și pregătirea pentru structurile arborescente.

8. Geometrie — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: sistem cartezian, distanțe, ecuația dreptei, panta, intersecții, arii, algoritmi de baleiere, înfășurătoare convexă. Geometrie computațională serioasă.
• Deblochează: problemele de geometrie de la națională, printre cele mai discriminante.

9. Backtracking — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: backtracking elementar, în plan, generarea soluțiilor, tăierea ramurilor inutile. Explorarea sistematică cu renunțare inteligentă.
• Deblochează: problemele de generare/căutare exhaustivă și intuiția de „spațiu de stări".

10. Programare dinamică — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: idee, stări, tranziții, inițializare, probleme de numărare și de optimizare, memoizare. Tema cu cel mai mare randament la concurs.
• Deblochează: tot DP-ul avansat de clasele XI–XII; lecția-punte „cum alegi starea" e abilitatea-cheie.

Borne / checkpoints

• După Structuri liniare + STL: alegi corect între set, map, priority_queue și rezolvi o problemă cu deque monoton.
• După Combinatorică modulară: numeri configurații modulo un prim și folosești inversul modular.
• După Recursivitate + Divide et Impera: desenezi arborele de recursie al unei probleme și implementezi un merge sort.
• După Backtracking + DP: generezi toate soluțiile unei probleme cu tăiere de ramuri și rezolvi un rucsac / o numărare de căi — exact ce cere națională clasa a X-a.

Traseul olimpicului

Capitolele 1–7 sunt nucleul. Geometrie, Backtracking și Programare dinamică sunt extensii naționale și sunt zonele care decid clasamentul. Sfat: nu trata DP-ul ca pe o colecție de rețete — investește în lecția-punte „cum alegi starea", pentru că în XI–XII vei modela singur stările (pe arbori, pe grafuri, cu bitmask). Iar înainte de backtracking, asigură-te că recursivitatea și arborele de recursie îți sunt naturale.

Capcane de parcurs

• Sari la DP fără recursivitate și fără să știi alege starea. E capcana #1 de liceu. Roadmap-ul pune recursivitatea înaintea DP-ului și insistă pe alegerea stării.
• Folosești structura STL greșită. Un map unde ajungea un vector, sau o căutare liniară unde ajungea un set, strică complexitatea. Lecția-punte despre complexitățile STL e exact pentru asta.
• Backtracking fără tăierea ramurilor. Fără pruning, explodează timpul. Tema „tăierea ramurilor inutile" e parte din capitol tocmai ca să nu cazi în brute-force pur.