Subiectul III.3: cum proiectezi un algoritm eficient la BAC

Ultimul item al probei valorează 10 puncte și este singurul care testează explicit proiectarea unui algoritm, nu implementarea unuia dat. Este și itemul la care se pierd cei mai mulți elevi de nota 9 — nu pentru că nu găsesc o soluție, ci pentru că găsesc una corectă și lentă.

Ce înseamnă „eficient” în limbajul baremului

Enunțul cere „un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat”. Traducerea practică, dată dimensiunile uzuale ale datelor (n ≤ 10^5, valori în [0, 10^3] sau [0, 10^9]):

• Timp: o singură parcurgere a datelor, sau cel mult o sortare urmată de o parcurgere. Două for-uri imbricate peste n = neeficient.
• Memorie: fie constantă (câteva variabile), fie liniară în raport cu domeniul de valori, nu cu n.

Un semnal important: dacă enunțul îți precizează un interval mic pentru valori (de exemplu [10, 10^3]), aproape sigur soluția presupune un vector de frecvență. Enunțurile de BAC nu dau limite degeaba.

Subpunctul a) valorează 2 puncte și cere descrierea în limbaj natural. Structura care ia punctajul, în trei fraze:

Parcurg fișierul o singură dată și rețin [structura folosită]. Pentru fiecare element actualizez [ce actualizez] în timp constant. Algoritmul este eficient deoarece face o singură parcurgere a celor N valori și folosește memorie suplimentară [constantă / proporțională cu domeniul valorilor], fără a memora întregul șir.

Adaptezi fraza la problemă și ai cele 2 puncte.

Tehnica 1: vector de frecvență

Aplicabilă când valorile sunt într-un interval mic și te interesează câte apariții are fiecare.

Problemă tip: din fișier se citesc N valori din intervalul [0, 1000]. Să se afișeze valoarea care apare de cele mai multe ori; dacă sunt mai multe, cea mai mică.

#include <fstream>
using namespace std;

int f[1001];

int main() {
    ifstream fin("bac.txt");
    int n, x;
    fin >> n;
    for (int i = 0; i < n; i++) {
        fin >> x;
        f[x]++;
    }
    fin.close();

    int val = 0;
    for (int v = 0; v <= 1000; v++)
        if (f[v] > f[val])
            val = v;

    cout << val;
    return 0;
}

Observă ce nu face programul: nu memorează cele N valori. Citește câte una și o consumă imediat. Memoria suplimentară este 1001 întregi, independent de N. Exact asta trebuie să scrii și la subpunctul a).

Comparația f[v] > f[val] (strict mai mare) garantează automat că, la egalitate, rămâne valoarea mai mică — pentru că parcurgem crescător. Este genul de detaliu care aduce sau pierde puncte.

Tehnica 2: sume parțiale (prefix sums)

Aplicabilă când ai nevoie de suma unei subsecvențe și trebuie să răspunzi la mai multe interogări, sau când compari sume de zone.

Ideea: construiești s[i] = v[1] + v[2] + ... + v[i]. Atunci suma pe intervalul [a, b] este s[b] - s[a-1], calculată în timp constant.

int v[100005], s[100005];

// construire: O(n)
s[0] = 0;
for (int i = 1; i <= n; i++)
    s[i] = s[i - 1] + v[i];

// suma pe [a, b]: O(1)
int suma = s[b] - s[a - 1];

Fără sume parțiale, fiecare interogare ar costa O(n), iar Q interogări ar da O(n·Q). Cu ele, O(n + Q).

Atenție la indexare: pornirea de la 1 și definirea lui s[0] = 0 elimină cazul special de la începutul vectorului. Dacă indexezi de la 0, trebuie să tratezi separat a == 0, ceea ce e o sursă de erori pe hârtie.

Tehnica 3: doi indici care avansează simultan

Aplicabilă când ai două șiruri sortate, sau un singur șir sortat în care cauți perechi.

Problemă tip: două șiruri sortate crescător, să se afișeze valorile comune, o singură dată.

int i = 0, j = 0;
while (i < n && j < m) {
    if (a[i] == b[j]) {
        cout << a[i] << " ";
        i++;
        j++;
    }
    else if (a[i] < b[j])
        i++;
    else
        j++;
}

Complexitate O(n + m), față de O(n·m) pentru soluția cu două for-uri imbricate. Fiecare indice avansează cel mult o dată per element, deci total cel mult n + m pași — asta e justificarea pe care o scrii la a).

Tehnica 4: o singură parcurgere cu stare minimă

Aplicabilă când răspunsul se poate actualiza incremental, pe măsură ce citești datele.

Problemă tip: subsecvența de sumă maximă (algoritmul lui Kadane).

int sumaCurenta = 0, sumaMax = v[0];
for (int i = 0; i < n; i++) {
    if (sumaCurenta < 0)
        sumaCurenta = 0;
    sumaCurenta += v[i];
    if (sumaCurenta > sumaMax)
        sumaMax = sumaCurenta;
}

Ideea centrală: dacă suma acumulată până acum este negativă, nu are sens să o duci mai departe — orice subsecvență viitoare e mai bună fără ea. O parcurgere, două variabile, memorie constantă.

Aceeași schemă acoperă: cea mai lungă secvență crescătoare consecutivă, numărul de „vârfuri” dintr-un șir, cea mai lungă secvență de elemente egale.

Tehnica 5: greedy local pe perechi consecutive

Aplicabilă când constrângerea se aplică între elemente vecine, iar tu poți doar să scazi (sau să adaugi).

Problemă tip (variantă de simulare 2026): N cutii cu bomboane, așezate în linie. Nicio pereche de cutii alăturate nu trebuie să conțină, împreună, mai mult de X bomboane. Care este numărul minim de bomboane care trebuie extrase?

Soluția greedy: parcurgi de la stânga la dreapta și, ori de câte ori a[i-1] + a[i] > X, scazi excesul din elementul din dreapta, a[i].

De ce din dreapta și nu din stânga? Pentru că a[i-1] a fost deja validat cu vecinul său din stânga, iar reducerea lui a[i] ajută și la perechea următoare (a[i], a[i+1]). Reducerea din stânga ar fi la fel de costisitoare acum, dar fără beneficiu viitor. Acesta este exact tipul de justificare care valorează cele 2 puncte de la a).

#include <fstream>
using namespace std;

int main() {
    ifstream fin("bac.txt");
    int n, x, ant, cur;
    long long total = 0;

    fin >> n >> x;
    fin >> ant;
    for (int i = 1; i < n; i++) {
        fin >> cur;
        if (ant + cur > x) {
            int exces = ant + cur - x;
            if (exces > cur)
                exces = cur;      // nu putem scoate mai mult decât există
            total += exces;
            cur -= exces;
        }
        ant = cur;
    }
    fin.close();

    cout << total;
    return 0;
}

Verificare pe exemplul din enunț: N = 6, X = 3, șirul 1 6 1 2 0 4.

Rezultat: 5. Corect.

Observă din nou: nu am memorat șirul. Două variabile, ant și cur. Memorie constantă, o parcurgere. Aceasta este forma pe care baremul o recompensează integral.

Cum recunoști tehnica din enunț

Greșeala care anulează tot

Citirea întregului fișier într-un vector, când problema nu o cere. Dacă poți răspunde citind valorile una câte una, fă-o. Memoria suplimentară proporțională cu N, când nu e necesară, este exact ce sancționează cerința de eficiență.

Întreabă-te înainte să declari vectorul: am nevoie să revin la valorile deja citite? Dacă răspunsul e nu, nu declara vectorul.

Întrebări frecvente

Trebuie să scriu complexitatea cu notația O(n)? Nu este obligatoriu, dar ajută. Baremul cere justificarea eficienței în limbaj natural. „O singură parcurgere a celor N valori” este suficient; „complexitate O(n) timp și O(1) memorie suplimentară” este mai puternic și mai scurt.

Dacă nu găsesc soluția eficientă, scriu soluția lentă? Absolut. O soluție corectă dar neeficientă ia o parte substanțială din cele 8 puncte de la b). Zero rânduri iau zero puncte.

Sortarea contează ca neeficientă? Nu. O sortare O(n log n) urmată de o parcurgere liniară este acceptată ca soluție eficientă la BAC.

---

Lucrăm acest tip de item la fiecare ședință de pregătire, cu accent pe justificarea scrisă. Vezi și structura completă a probei și greșelile frecvente de C++. Programează o ședință →