h1. 'Problema A':problema/pba

Este evident ca produsul maxim ar fi obtinut prin inmultirea celor mai mari trei numere din sir. Fie $M1, M2, M3$ cele mai mari $3$ numere din sir, iar $P1$, $P2$, $P3$ pozitiile pe care se afla acestea. Pentru simplitatea explicatiei, vom trata cazul in care $P1 < P2 < P3$. Pentru acest caz, vom alege subsecventele: $[1, P1]$, $[P1 + 1, P2]$, $[P2 + 1, P3]$. Cum maximul din prima subsecventa este $M1$, maximul din cea de-a doua subsecventa este $M2$, iar maximul din a treia subsecventa este $M3$, produsul maxim a fost obtinut, si anume $M1 * M2 * M3$. Celelalte cazuri se trateaza analog.
 

h1. 'Problema cu becuri':problema/pcb

Construim un graf cu $N + 1$ noduri in care fiecare nod reprezinta o stare. Starea initiala este reprezentata de nodul $1$. Fiecare nod $i > 1$ va reprezenta starea in care sunt aprinse doar becurile $[1,i-1]$.
 
Pentru fiecare comutator care schimba becurile din intervalul $[a,b]$ adaugam o muchie intre nodurile $a$ si $b+1$. Explicatia este: $a$ reprezinta becurile aprinse in intervalul $[1,a-1]$ la care se adauga cele din intervalul $[a,b]$ si rezulta $[1,b]$, adica nodul $b+1$.
 
Deci, putem aprinde becurile $[1,X-1]$ daca exista un drum de la nodul $1$ la nodul $X$. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o 'parcurgere in latime':problema/bfs (deoarece toate muchiile au costul $1$).
 
Solutia are complexitatea $O(N + M)$.
 

h1. 'Raci':problema/raci

Avand un sir de $N$ cuvinte trebuie sa aflam un subsir care sa respecte proprietatile din enunt.
O prima solutie foloseste programarea dinamica si este asemanatoare celei de la aflarea 'celui mai lung subsir crescator':problema/scmax, difera doar conditia de potrivire a sirurilor.
 
Ne definim o stare $dp[i]$ = cel mai lung subsir care respecta conditiile si se termina in cuvantul $i$. Cand calculam $dp[i]$, incercam sa gasim un cuvant $j < i$, $j >= i - K$ astfel incat ultima litera din cuvantul $j$ este egala cu prima litera din cuvantul $i$.
Valoarea lui $dp[i]$ va fi maximul dintre toate $dp[j]$ care respecta conditia, la care adaugam $1$.
 
Din pacate, o astfel de solutie are complexitatea $O(N * K)$, ceea ce depaseste cu mult limita de timp.
 
Putem imbunatati acest algoritm. Notam prima litera a cuvantului $i$ cu $p$. Observam ca atunci cand potrivim sirurile, cautam doar cuvintele care se termina cu litera $p$. O idee ar fi sa creem o lista de indici pentru fiecare litera. Notam lista pentru litera $p$ cu $L[p]$. Vom cauta in $L[p]$ indicii $j >= i - K$ si luam maximul dintre aceste valori. Putem considera aceste liste ca fiind cozi cu doua capete si putem actualiza maximul din toate cele 26 cozi pe masura ce adaugam indicii (vezi descriere 'deque':problema/deque). Actualizarile au complexitatea $O(N)$ amortizat.
 
Acum solutia are complexitatea optima $O(N)$.
 

h1. 'Suma5':problema/suma5

Problema este o aplicatie clasica a arborilor de intervale cu lazy propagation. Fiecare nod al arborelui de intervale va retine informatii legate de:
 
* Capatul stang al intervalului (st)
* Capatul drept al intervalului (dr)
* Suma elementelor din interval (s1)
* Raspunsul la un query fix pe acel interval (s2)
 
Acum singura problema care ne mai ramane este unirea a doua noduri a si b intr-un singur nod c (altfel spus, unirea a doua jumatati de interval intr-un singur interval, mentinand toate informatiile de mai sus). Informatiile legate de capetele noului interval sunt usor de calculat dupa urmatoarele formule intuitive:
 
== code(cpp) |
c.st = a.st;
c.dr = b.dr;
==
 
Calcularea sumei noului interval se obtine prin adunarea sumelor intervalelor a si b.
 
== code(cpp) |
c.s1 = a.s1 + b.s1;
==
 
Calcularea noului s2 este putin mai complexa:
 
== code(cpp) |
c.s2 = a.s2 + (b.s2 + b.s1 * (a.dr - a.st + 1));
==
 
Problema a fost aleasa drept cea mai grea problema a setului pentru ca rezolvarea presupunea cunoasterea si aplicarea teoriei, dar si o atentie sporita intr-o implementare laborioasa.
 

==include(page="template/monthly-2014/footer")==