În schimb, este adevărat că dacă submatricea optimă va avea $X$ linii şi $Y$ coloane, ne intereseaza doar subsecvenţele de lungime $X$, respectiv $Y$ care au suma maximă posibilă în $A$ şi $B$. Putem precalcula uşor şirul $bestA[Length]$ = “suma maximă a unei subsecvenţe din $A$ de lungime $Length$ ” în timp $O(N^2^)$, analog pentru şirul $bestB[]$. Apoi vom itera peste toate cele $N ^ 2$ dimensiuni posibile ale submatricei şi vom reţine maximul expresiei $LineCount * bestB[ColumnCount] + ColumnCount * bestA[LineCount]$.

Numarul de echipe care au rezolvat problema: *73*
Prima echipa care a rezolvat problema: ==User(user="geniucos" type="tiny")==
 

*B. Avioane2*
Construim $3$ tipuri de evenimente:

* Eveniment de Aterizare (aeroportul $B$): selectam pentru nodul in care aterizam (nodul $B$) cea mai buna varianta (ori pastram costul minim de pana acum, ori costul obtinut prin intermediul avionului care tocmai a aterizat, cost calculat la evenimentul de tip Decolare)
Problema poate fi vizualizata ca si un caz particular al algoritmului de Bellman-Ford. Din moment ce avem si axa timpului, este suficient sa trecem o singura data prin muchii deoarece o muchie cu un cost mic la un anumit moment de timp nu poate afecta alte configuratii la timpi mai mici

Numarul de echipe care au rezolvat problema: *29*
Prima echipa care a rezolvat problema: ==User(user="geniucos" type="tiny")==
 

*C. MinLcm*
Folosim proprietatea: $cmmmc(a, b) = a * b / cmmdc(a, b)$

Obsevatie: Algoritmul fixeaza in realitate doar un divizor al celor $2$ numere (fără a avea vreo garanţie că este cmmdc-ul real), dar dacă divizorul respectiv nu este într-adevăr cel mai mare posibil al celor două numere, va produce un rezultat mai mare decât cel real, deci răspunsul problemei nu va fi afectat.

Numarul de echipe care au rezolvat problema: *32*
Prima echipa care a rezolvat problema: ==User(user="forsakenAwe" type="tiny")==
 

*D. Unlock*
O primă soluţie posibilă este cea de a itera pe rând prin toate cele $K$ culori şi a efectua câte o parcurgere a matricei pentru a verifica dacă celulele libere sunt conexe. Această soluţie are complexitate worst-case $O(N * M * K)$, iar date fiind limitările lui $K$, este echivalentă cu $O((N * M) ^ 2)$. Deşi la prima vedere ar părea că este puţin probabil ca atât $K$ cât şi zonele atinse de fiecare parcurgere să fie de mărime $Theta(N * M)$ simultan, există teste în care acest lucru se întâmplă, iar soluţia descrisă depăşeşte cu mult limita de timp, care, mai mult, este calibrată pentru a procesa $25$ de teste, nu unul singur.

Este nevoie de o implementare atentă pentru a menţine complexitatea dorită. Spre exemplu, reiniţializarea completă a pădurilor de mulţimi disjuncte pentru fiecare culoare poate duce din nou la timp $O((N * M) ^ 2)$, chiar dacă restul algoritmului este eficient.

Numarul de echipe care au rezolvat problema: *15*
Prima echipa care a rezolvat problema: ==User(user="UNIBUC_Costan_Iordache_Magureanu" type="tiny")==
 

*E. MinMaxStore*
Se observa faptul ca proprietatea este independenta pentru minim si maxim.

La sfarsit proprietatea este adevarata daca avem un singur posibil minim si acesta se afla pe pozitia indicata. Analog facem si pentru maxim si raspundem la fiecare din cele $4$ cazuri in functie de corectitudinea celor $2$ raspunsuri.

Numarul de echipe care au rezolvat problema: *30*
Prima echipa care a rezolvat problema: ==User(user="echipa_BoSSilor" type="tiny")==
 

*F. Pokemon3*
În ciuda enunţului mai complex, aceasta este una dintre cele mai simple probleme la nivel algoritmic. Deoarece numărul de tipuri de pokemon este mic, putem itera prin toate submulţimile posibile de pokemoni şi verifica pentru fiecare submulţime dacă aceasta asigură victoria. Pentru a se încadra în timp, soluţia trebuie să codeze submulţimile ca măşti de biţi şi să facă verificarile folosind operaţii pe biţi pe aceste valori. Complexitatea finală este $O(2 ^ N * N)$.

Numarul de echipe care au rezolvat problema: *69*
Prima echipa care a rezolvat problema: ==User(user="team_name" type="tiny")==
 

*G. Puzzle2*
Problema admite multe soluţii, care variază mai ales ca dificultate a implementării. O soluţie rezonabilă vine din observaţia că o dată ce am aflat prima linie a matricei, restul matricei se poate reconstitui cu uşurinţă, linie cu linie. Pentru a construi prima linie, putem începe dintr-un colţ (un nod cu $2$ vecini) şi parcurge numai noduri de margine (care au $3$ vecini) până găsim un alt colţ. Dacă alegem să facem acest lucru, trebuie să tratăm special cazul matricelor cu $2$ linii (sau coloane), deoarece în acest caz parcurgerea nodurilor de margine poate alterna haotic între cele două linii, fără ca lanţul obţinut în final să fie o linie reală a matricei. Cazul se tratează uşor, observând că acum un colţ este vecin direct cu cel puţin un alt colţ. Cele două colţuri vor forma singure prima linie, iar acum putem reconstitui restul matricei ca în cazul general.

Numarul de echipe care au rezolvat problema: *21*
Prima echipa care a rezolvat problema: ==User(user="geniucos" type="tiny")==
 

*H. Subpermutari*
Consideram toate cele $N^2^$ subsecventele are permutarii noastre. Observam faptul ca daca pentru o secventa $[a,b]$ determinam cea mai lunga subpermutare care este atat prefix, cat si sufix a secventei noastre, putem foarte usor marca sufixul ca fiind o secventa care a mai aparut deja si crestem frecventa prefixului.

Pentru a determina al catelea element se afla o valoare intr-o secventa putem usor precalcula cu un simplu aib.
Complexitate: $O(N^2 log N)$

Numarul de echipe care au rezolvat problema: *2*
Prima echipa care a rezolvat problema: ==User(user="geniucos" type="tiny")==
 

*I. Nucleul Valoros Season 2*
Pornim de la solutia brute, programare dinamica in $O(N^3)$.

O sa demonstram ca daca facem for dupa $k$ de la $optim[i][j - 1]$ pana la $optim[i + 1][j]$, in loc sa il facem de la $i$ la $j$, obtinem complexitate $O(n^2)$.
Demonstratie: Consideram toate intervalele de lungime $x$. Avem proprietatea $optim[a][b - 1] <= optim[a][b] <= optim[a + 1][b]$ si $optim[a + 1][b] <= optim[a + 1][b + 1] <= optim[a + 2][b + 1]$, unde $b - a + 1 = x$. Observam ca sfasitul unui interval de lungime $x$ este inceputul urmatorului interval de lungime $x$. Amortizat, obtinem $O(N)$ pentru fiecare lungime $x$ de interval, $O(N ^ 2)$ in total.

 
Numarul de echipe care au rezolvat problema: *13*
Prima echipa care a rezolvat problema: ==User(user="team_name" type="tiny")==