Diferente pentru algoritmiada-2019/runda-preoji/solutii/tablou intre reviziile #1 si #2

Nu exista diferente intre titluri.

Diferente intre continut:

Scrie aici despre algoritmiada-2019/runda-preoji/solutii/tablou
h1. Solutia problemei Tablou
 
Concurentul ==User(user="theodor.moroianu" type="tiny")== s-a oferit sa descrie solutia sa la aceasta problema:
 
+Subtask 1:+
 
Salvam intr-o matrice tridimensionala tablourile fiecarei fete:
 
$Mat[id][i][j]$ este culoarea de pe pozitia $(i, j)$ din tabloul fetei $id$.
 
In <tex>O(N^2^ * M^2^ * K^2^)</tex> calculam diferenta ceruta.
 
 
 
 
 
+Subtaskurile 2,3:+
 
Majoritatea solutiilor din subtaskurile acestea sunt:
 
 
 
# Optimizari ale solutiei din +Subtaskul 1+
 
# Solutii bazate pe frecventa cifrelor $0...9$
 
# Solutii ne-optimizate din +Subtaskul 4+ bazate pe observatia prezentata tot acolo
 
 
 
 
 
+Subtask 4:+
 
Exista diferite solutii care sa ia $100$ de puncte, complexitatea cea mai proasta care sa intre in timp fiind
 
<tex>O(N*M + 100*Q)</tex>
 
 
 
O sa analizam mai departe o solutie cu complexitatea <tex>O(N*M+Q)</tex>
 
 
 
Observatia de baza pentru aceasta solutie este ca suma <tex>\sum_{B,a,b,p,q}^{} A[a][b]-B[p][q]</tex> poate fi scrisa sub forma <tex>N*M*(\sum_{a,b}^{} A[a][b]-\sum_{p,q}^{} B[p][q])</tex>
 
Raspunsul pentru o anumita poza poate deci fi scris sub forma <tex>\sum_{poza B!=a}^{} {N*M*(\sum_{a,b}^{} A[a][b]-\sum_{p,q}^{} B[p][q])}</tex>
 
<tex>= N*M*Q* \sum_{a,b}^{}{A[a][b]}-N*M*\sum_{poza B!=a}^{} {(\sum_{p,q}^{} B[p][q])}</tex>
 
Astfel, pozitiile / frecventele valorilor din imagini nu ne mai intereseaza, vrem doar sa stim suma lor!
 
 
 
Fie <tex>Stotal</tex> suma tuturor elementelor tuturor pozelor, si <tex>s[i]</tex> suma elementelor din poza i.
 
Raspunsul pentru o poza <tex>k</tex> o sa fie <tex>N*M*(Q*s[i] - (Stotal-s[i]))</tex>.
 
h1. Solutie alternativa
 
Aceasta este solutia autorului.
 
Vom nota cu $S = 10$ numarul de cifre in baza $10$, altfel spus marimea alfabetului cu care sunt descrise tablourile, pentru conturarea complexitatilor solutiilor ce urmeaza:
 
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.
 
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.
 
h2. Pentru $60$ de puncte
 
O alta observatie ce poate fi facuta este ca nu trebuie sa obtinem explicit fiecare tablou pentru a calcula sirul sau $fr[0...9]$. Este suficient sa stim sirul asociat tabloului initial al lui Marcel si cate cifre de $0$, de $1$, ..., respectiv de $9$ se afla in submatricea unde se recoloreaza cu culoarea $cul$. Pentru a cunoaste aceasta, e suficient sa precalculam un tablou de sume partiale pentru fiecare cifra in parte, astfel:
 
$S[ c ][i][j]$ = numarul de cifre $c$ din submatricea cu coltul stanga-sus in celula $(1, 1)$ si coltul dreapta-jos in celula $(i, j)$.
$S[ c ][i][j] = S[ c ][i - 1][j] + S[ c ][i][j - 1] - S[ c ][i - 1][j - 1] + (1 daca T[i][j] = c, 0 daca nu)$
Calculul acestui tablou tridimensional are complexitate <tex> O(N^2 * S) </tex> atat ca timp, cat si ca memorie.
 
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.
 
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(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.

Diferente intre securitate:

private
protected

Topicul de forum nu a fost schimbat.