h1. Solutii

h2. Maxsecv
h3. (clasele 9-10)

...

Se observa ca secventa maxima de $1$ care se poate obtine are lungimea egala cu suma primelor doua secvente maxime din vectorul original. Printr-o operatie descrisa se pot alatura cu usurinta cele doua secvente.
Pentru obtinerea unei solutii liniare e suficient sa parcurgem vectorul de la stanga la dreapta si sa updatam la fiecare pas lungimea secventei curente de $1$. In momentul in care ajungem la capatul unei astfel de secvente facem un update pentru primul si al 2-lea maxim, dupa caz.
 

h2. Chernel
h3. (clasele 9-10)

Considerandu-se sirul $a{~1~} a{~2~} ... a{~N~}$ pentru un $N$ fixat, se observa ca dupa $N-1$ transformari, acesta devine $a{~1~} * C{~N-1~}^0^ + a{~2~} * C{~N-1~}^1^ + a{~3~} * C{~N-1~}^2^ + ... + a{~N~} * C{~N-1~}^N-1^$ . De aici reiese ca elementele sirului initial a calor valoare nu influenteaza numarul caracteristic (numarul din ultimul sir obtinut $modulo M$) sunt cele ai caror coeficienti sunt multipli ai lui $M$. Astfel problema se reduce la numararea combinarilor de $N-1$ luate cate $i$ (cu $i$ intre $0$ si $N-1$) care sunt multipli de $M$. Aceasta se realizeaza simplu "generand" combinarile respective: ne bazam pe recurenta $C{~N~}^k+1^ = C{~N~}^k^ * (n-k) / (k+1)$ si verificam cate dintre acestea sunt divizibile cu $M$. Problema este ca aceste valori vor deveni uriase destul de rapid, iar stocarea lor in memoria calculatorului este ineficienta. Din acest motiv nu se vor retine numerele propriu zise, ci doar exponentii factorilor primi ai lui $M$, (numarul maxim de factori primi ai lui fiind maxim aproximat la $O(ln ln M)$, si $9$ pentru datele de test ale problemei) care se vor actualiza pentru fiecare combinare procesata.

Considerandu-se sirul $a{~1~} a{~2~} ... a{~N~}$ pentru un $N$ fixat, se observa ca dupa $N-1$ transformari, acesta devine $a{~1~} * C{~N-1~}^0^ + a{~2~} * C{~N-1~}^1^ + a{~3~} * C{~N-1~}^2^ + ... + a{~N~} * C{~N-1~}^N-1^$ . De aici reiese ca elementele sirului initial a calor valoare nu influenteaza numarul caracteristic (numarul din ultimul sir obtinut $modulo M$) sunt cele ai caror coeficienti sunt multipli ai lui $M$. Astfel problema se reduce la numararea combinarilor de $N-1$ luate cate $i$ (cu $i$ intre $0$ si $N-1$) care sunt multipli de $M$. Aceasta se realizeaza simplu "generand" combinarile respective: ne bazam pe recurenta $C{~N~}^k+1^ = C{~N~}^k^ * (n-k) / (k+1)$ si verificam cate dintre acestea sunt divizibile cu $M$. Problema este ca aceste valori vor deveni uriase destul de rapid, iar stocarea lor in memoria calculatorului este ineficienta. Din acest motiv nu se vor retine numerele propriu zise, ci doar exponentii factorilor primi ai lui $M$, (numarul maxim de factori primi ai lui fiind aproximat la $O(ln ln M)$, si $9$ pentru datele de test ale problemei) care se vor actualiza pentru fiecare combinare procesata.

Complexitatea finala a algoritmului devine astfel $O(N * ln ln M)$.
h2. Amenzi

Problema se poate rezolva folosind metoda programarii dinamice. Se construieste matricea $A{~t,i~}$ in care se retine valoarea totala a amenzilor ce poate fi data pana la momentul $t$ astfel incat la momentul $t$ sa fim in intersectia {$i$}. Pentru toate muchiile ({$j,i$}) de cost $c$ vom compara {$A{~t,i~}$} cu {$A{~t-c,j~}$} alegand maximul dintre aceste valori. De fapt ar trebui inspectate toate valorile {$A{~t-c,j~}$} {$A{~t-c-1,j~}$} ... {$A{~1,j~}$} {$A{~0,j~}$} dar este clar ca maximul acestor valori se afla in {$A{~t-c,j~}$}. Deasemenea trebuie considerat cazul cand politistul sta pe loc deci ne vom uita si la valoarea din {$A{~t-1,i~}$}. Apoi politistul va da toate amenzile posibile la momentul respectiv in intersectia respectiva deci vom aduna respectiva suma la {$A{~t,i~}$}.
Avand construita aceasta matrice se poate raspunde in $O(1)$ la fiecare intrebare.

Complexitatea totala va fi $O(Tmax * M)$ ca timp si $O( Tmax * N )$ ca memorie.

Complexitatea totala va fi $O(Tmax * M)$ ca timp si $O(Tmax * N)$ ca memorie.

h2. Secventa 5
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