h1. Solutia problemei Tablou

h1(#tablou). 'Solutia problemei Tablou':problema/tablou

Concurentul ==User(user="theodor.moroianu" type="tiny")== s-a oferit sa descrie solutia sa la aceasta problema:

h2. Pentru $10$ puncte

Solutia de complexitate <tex> O(Q^2 * N^4) </tex> timp si <tex> O(Q * N^2) </tex> memorie nu face decat sa creeze cele $Q$ tablouri si sa calculeze conform enuntului costul fiecaruia. Se fixeaza tabloul caruia vrem sa ii calculam costul, de unde un factor de <tex> O(Q) </tex>, se fixeaza tabloul cu care il comparam, alt <tex> O(Q) </tex>, se fixeaza pozitia $(a, b)$ in <tex> O(N^2) </tex> si pozitia $(p, q)$ in <tex> O(N^2) </tex>, si se adauga la raspuns diferenta intre cele $2$ caractere.

Solutia de complexitate <tex> O(K^2 * N^4) </tex> timp si <tex> O(K * N^2) </tex> memorie nu face decat sa creeze cele $K$ tablouri si sa calculeze conform enuntului costul fiecaruia. Se fixeaza tabloul caruia vrem sa ii calculam costul, de unde un factor de <tex> O(K) </tex>, se fixeaza tabloul cu care il comparam, alt <tex> O(K) </tex>, se fixeaza pozitia $(a, b)$ in <tex> O(N^2) </tex> si pozitia $(p, q)$ in <tex> O(N^2) </tex>, si se adauga la raspuns diferenta intre cele $2$ caractere.

h2. Pentru $30 - 50$ de puncte
Prima observatie ce poate fi facuta e ca putem scurta mult calculul dereglarii a doua tablouri daca, in loc sa consideram toate pozitiile cu toate poitiile, le grupam in functie de cifra lor. Cu alte cuvinte, e suficient sa cunoastem sirul $fr[t][0...9]$ care ne spune, pentru tabloul $t$, cate cifre de $0$, de $1$, ..., de $9$ are in el.

Astfel, putem calcula, parcurgand fiecare tablou, acest sir $fr[t][0...9]$. Cand vrem sa calculam dereglarea dintre tablouri, e suficient sa fixam cifra $c1$ din primul tablou $t1$ si cifra $c2$ din al doilea tablou $t2$ si sa adunam la valoarea primului tablou $fr[t1][c1] * fr[t2][c2] * (c1 - c2)$. Complexitatea este <tex> O(Q * N^2 + Q^2 * S^2) </tex> timp si <tex> O(N^2 + Q * S) </tex> memorie.

Astfel, putem calcula, parcurgand fiecare tablou, acest sir $fr[t][0...9]$. Cand vrem sa calculam dereglarea dintre tablouri, e suficient sa fixam cifra $c1$ din primul tablou $t1$ si cifra $c2$ din al doilea tablou $t2$ si sa adunam la valoarea primului tablou $fr[t1][c1] * fr[t2][c2] * (c1 - c2)$. Complexitatea este <tex> O(Q * N^2 + K^2 * S^2) </tex> timp si <tex> O(N^2 + K * S) </tex> memorie.

h2. Pentru $60$ de puncte

Atunci cand vrem sa calculam sirul $fr[0...9]$ al unui anumit tablou, putem copia frecventa cifrelor din cel initial, apoi putem scadea din $fr[ c ]$ numarul de cifre egale cu $c$ din submatricea recolorata, adica $S[ c ][lin2][col2] - S[ c ][lin2][col1 - 1] - S[ c ][lin1 - 1][col2] + S[ c ][lin1 - 1][col1 - 1]$. La final, adaugam $(lin2 - lin1 + 1) * (col2 - col1 + 1)$ la $fr[cul]$.

Complexitatea solutiei este <tex> O(N^2 * S + Q^2 * S^2) </tex> timp si <tex> O(N^2 * S + Q * S) </tex> memorie, intrucat pentru calculul valorii fiecarui tablou vom proceda asemanator cu solutia precedenta.

Complexitatea solutiei este <tex> O(N^2 * S + K^2 * S^2) </tex> timp si <tex> O(N^2 * S + K * S) </tex> memorie, intrucat pentru calculul valorii fiecarui tablou vom proceda asemanator cu solutia precedenta.

h2. Pentru $100$ de puncte
Observatia finala se bazeaza pe faptul ca dereglarea dintre doua tablouri $t1$ si $t2$ este egala cu deregalarea dintre $t1$ si tabloul lui Marcel $minus$ dereglarea dintre $t2$ si tabloul lui Marcel. (Vectorial, am putea spune ca <tex> $$\vec{AB} = $$\vec{AC} - $$\vec{BC} </tex>).

Astfel, putem calcula in <tex> O(Q * S^2) </tex> dereglarea dintre fiecare tablou si tabloul lui Marcel, pe care o notam cu $V[t]$. Fie $sum$ suma tuturor acestor dereglari $V[t]$. Atunci valoarea unui tablou este egala cu $V[t] * K - sum$.

Astfel, putem calcula in <tex> O(K * S^2) </tex> dereglarea dintre fiecare tablou si tabloul lui Marcel, pe care o notam cu $V[t]$. Fie $sum$ suma tuturor acestor dereglari $V[t]$. Atunci valoarea unui tablou este egala cu $V[t] * K - sum$.

Complexitate finala: <tex> O(N^2 * S + Q * S^2) </tex> timp si <tex> O(N^2 * S + Q) </tex> memorie.

Complexitate finala: <tex> O(N^2 * S + K * S^2) </tex> timp si <tex> O(N^2 * S + K) </tex> memorie.