h2. 'Expresii algebrice':problema/expresii

Vom calcula o matrie $T[i][j]$ reprezentand numarul de arbori de evaluare a sub-expresiei dintre pozitiile $i$ si $j$. Daca sub-expresia dintre aceste pozitii nu este valida (nu este parantezata corect, nu are o structura corespunzatoare de operanzi si operatori etc.), atunci $T[i][j]$ va fi 0. In caz contrar, daca expresia dintre pozitiile $i$ si $j$ este inclusa intre paranteze, atunci $T[i][j]=T[i+1][j-1]$. Daca nu este complet inclusa intr-o pereche de paranteze, atunci exista cel putin un operator care nu este inclus in vreo paranteza. Se cauta intai operatorii '+' care nu sunt inclusi intre paranteze si pentru fiecare astfel de operator aflat pe o pozitie $k$, $T[i][j]$ se incrementeaza cu valoarea $T[i][k-1]*T[k+1][j]$. Daca nu se gaseste nici un '+' neinclus intre paranteze, atunci se cauta un '*' si se realizeaza aceleasi operatii.
 

h2. 'Calatorie interplanetara':problema/calatorie

Vom calcula $C[i][j]$ reprezentand consumul minim pentru ca nava spatiala sa ajunga la planeta $i$ si sa fi parcurs $j$ unitati de timp cu superviteza. Valoarea lui $j$ este cel mult $500$. $C[i][j]$ se calculeaza pe baza lui $C[i-1][j]$ (daca intre planetele $i-1$ si $i$ nava a calatorit cu viteza normala) sau pe baza lui $C[i-1][j-H{~i-1~}]$ (daca intre planetele $i-1$ si $i$ nava a calatorit cu superviteza), alegandu-se varianta minima dintre cele doua posibilitati.
 

h2. 'Razboiul lumilor':problema/razboi
Solutia optima are complexitate $O(N)$ si se realizeaza parcurgand arborele de $2$ ori. La prima parcurgere fixam radacina arborelui in nodul $1$. Vom calcula pentru fiecare nod $i$ cate $2$ valori: lungimea maxima a unui drum de la orasul $i$ la orice alt oras din subarborele acestuia, {$L{~1~}[i]$}, si lungimea maxima a unui drum de la orasul $i$ la un oras din subarborele acestuia, dar care este diferit de primul drum, {$L{~2~}[i]$} (practic, a doua lungime maxima a unui drum, care poate fi, eventual, egala cu lungimea primului). In a doua parcurgere vom calcula distanta maxima de la fiecare oras $i$ la orice alt oras si vom alege orasele pentru carea aceasta distanta maxima este minima. Pentru radacina arborelui am calculat deja aceasta valoare din prima parcurgere. Pentru orice alt nod $i$, distanta maxima de la $i$ la orice alt oras este ori {$L{~1~}[i]$}, ori un drum ce trece prin parintele lui $i$. Cel mai lung drum ce trece prin parintele lui $i$ are lungimea egala cu distanta de la $i$ la parintele lui $i$ plus {$L{~1~}[parinte[i]]$}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]$} nu trece prin orasul $i$, respectiv plus {$L{~2~}[parinte[i]]$}, in cazul in care drumul corespunzator lui {$L{~1~}[parinte[i]]$} trece prin orasul $i$.

h2. 'Divizor si multiplu':problema/divmul

Se vor determina toti divizorii primi ai lui $x$ si ai lui $y$, impreuna cu puterile la care apar. Fiecare divizor prim al lui $x$ trebuie neaparat sa fie un divizor prim si al lui $y$, la o putere mai mare sau egala. Vom calcula $D$=numarul de divizori primi care apar la o putere mai mare in $y$ decat in $x$ (inclusiv acei divizori care apar in $y$ si nu apar deloc in $x$). Numarul de perechi ordonate care il au pe $x$ ca cel mai mare divizor comun si pe $y$ ca cel mai mic multiplu comun este $2^D^$.
 

h2. 'Palindroame':problema/palind
Pentru a avea solutie este necesar ca cel mult un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval $(a,b)$, $a$ reprezentand pozitia caracterului din stanga din cadrul perechii, iar $b$ reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a $2$ intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime $0$ sau $1$.