Algoritmul general de determinare a submatricei de sumă maximă este prea încet pentru această problemă, având complexitate $O(N ^ 3)$. Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile $(x1, y1, x2, y2)$, observăm că suma sa este $(x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2]$, unde prin $T[a...b]$ am notat suma $T[a] + T[a + 1] + …. T[b]$. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

Î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]$.

Î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")==

Pentru a obţine o soluţie mai rapidă, vom încerca ca pentru fiecare culoare fixată să depunem efort (i.e număr de operaţii) proporţional cu numărul total de celule de această culoare. Deoarece în total acest număr este limitat de $N * M$, complexitatea ar fi şi ea proporţională cu această valoare. Pentru a construi o asemenea soluţie, vom face pentru început nişte parcurgeri care vor identifica zonele conexe de celulele libere. Apoi, pentru fiecare culoare fixată, fie ea $C$, vom face o parcurgere pentru fiecare componentă conexă de culoare $C$ şi vom reţine cu ce zone conexe libere este vecină fiecare astfel de componentă. Dacă o anumită componentă Comp de culoare $C$ este vecină cu zonele libere $“x1, x2 .. xT”$, atunci aceste zone vor deveni conectate în momentul în care o facem pe Comp accesibilă. Astfel, pentru fiecare componentă îi putem uni vecinii cu o structură de date eficientă (de tip păduri de mulţimi disjuncte), iar la final trebuie ca toate zonele libere iniţiale să fie conexe. Pentru a justifica faptul că numărul de operaţii este proporţional cu mărimea componentelor de culoare $C$, observăm faptul că fiecare zonă liberă vecină cu o anumită componentă trebuie să fie adiacentă cu componenta respectivă pe cel puţin o latură a unei celule din componentă. Deoarece numărul de laturi al unei componente conexe este limitat de $4 * (mărimea componentei)$, rezultă că numărul maxim de vecini distincţi posibili este limitat de aceeaşi valoare.

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.

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")==

*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)$.

Î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")==

Daca indicele difera, micsoram pi-ul (mergem in $pi[pi[b]]$) si repetam procedeul pana avem o potrivire
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)$

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)$.

Pornim de la solutia brute, programare dinamica in $O(N^3^)$.

$D[i][j] =$ costul minim al secventei $[i,j]$. Recurenta este data in enunt: fixam un $k$ de la $i$ la $j - 1$ si luam cea mai buna varianta
Notam pentru un interval $[i,j]$, valoarea $k$ pentru acest interval drept $optim[i][j]$.

Intuitiv este foarte usor de vizualizat acest lucru:
Daca am secventa $[i, j - 1]$ si adaug un element nou in dreapta, $k$ se poate muta doar la dreapta
Daca am secventa $[i + 1, j]$ si adaug un element nou in stanga, $k$ se poate muta doar la stanga

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)$.

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.

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")==

private

protected

10712