h3. (clasele 11-12)

...
 

Vom construi o procedura cu ajutorul careia vom numara cate secvente exista care contin cel mult $X$ elemente distincte. Folosind aceasta procedura, rezultatul problemei va fi: numarul de secvente cu cel mult $U$ elemente distincte - numarul de secvente cu cel mult $L-1$ elemente distincte.
La primul pas, vom normaliza valorile din sirul de intrare, inlocuind fiecare valoare cu un numar de la $1$ la $N$ (spre exemplu sirul $13 13 47 9 9$ devine $1 1 2 3 3$). Aceasta normalizare se poate face in $O(N*lg N)$ cu o sortare, dar aceasta solutie va obtine doar $80$ de puncte. Pentru $100$ de puncte normalizarea trebuie facuta folosind o tabela 'hash':tabele-hash-scurta-prezentare.
Fie $L{~i~}$ cel mai mic indice astfel incat secventa cu elementele $L{~i~}...i$ contine cel mult $X$ elemente distincte (cu alte cuvinte cea mai lunga secventa cu maxim $X$ elemente distincte care se termina pe pozitia $i$). Numarul total de subsecvente va fi $(1-L{~1~}+1) + (2-L{~2~}+1) + (3-L{~3~}+1) + ... + (N-L{~N~}+1)$.
Este usor de aratat ca $L{~i~} ≤ L{~i+1~}$ pentru orice $i$. Asadar, pe masura ce trecem de la $i$ la $i+1$ vom incepe calculul lui $L{~i+1~}$ de la valoarea $L{~i~}$. Pentru a stii la fiecare moment cate elemente distincte sunt in secventa $L{~i~}...i$ vom mentine un vector $V$ cu proprietatea ca $V{~x~}$ = de cate ori apare $x$ in secventa si o variabila $Nr$ reprezentand numarul de valori distincte din secventa. Valorea lui $Nr$ va creste doar cand $V{~x~}$ se schimba din $0$ in $1$, si va scade doar cand $V{~x~}$ se schimba din $1$ in $0$ (pentru un $x$ oarecare). Complexitatea totala a algoritmului este $O(N)$.

private

public