h1. 'Soluţia':jc2020/solutii/aparate problemei 'Aparate':problema/aparate

h1(#aparate). 'Soluţia':jc2020/solutii/aparate problemei 'Aparate':problema/aparate
 
h2. Subtask 1 (10 puncte) - $Q ≤ 1.000$
 
Putem simula direct toate operaţiile cu brute-force. La un $update$, luăm toate coloanele şi le rotim în $O(N)$ cu $k$ poziţii, iar la un $query$ luăm toate elementele de pe linia $k$ cu coloanele de la $l$ până la $r$ şi le facem suma. Complexitatea pe un $query$ este $O(M)$, iar complexitatea unui $update$ este $O(N * M)$, deci complexitatea totală o să fie $O(Q * N * M)$ pe cel mai rău caz.
 
h2. Subtask 2 (20 puncte) - $M ≤ 1.000$
 
Putem să nu facem rotaţiile fizice şi să ţinem minte pentru fiecare coloană cu câte poziţii a fost rotită în sus. Dacă o coloană $c$ a fost rotită în sus cu $k$ poziţii, ca să accesăm elementul de pe linia $l$, putem defapt să accesăm din matricea iniţială elementul de pe linia $(l + k) % N$ şi coloana $c$ (cu precizarea că în soluţie indexăm liniile şi coloanele de la $0$, nu de la $1$).
 
La un $update$ trebuie doar să actualizăm pentru fiecare coloană cu câte poziţii am rotit-o în sus, iar la un $query$ putem direct să facem suma elementelor cerute.
 
Astfel complexitatea unui $update$ devine $O(M)$, iar complexitatea unui $query$ devine tot $O(M)$. Astfel, complexitatea finală o să fie $O(Q * M)$.
 
h2. Subtask 3 (30 puncte) - $N = 2$
 
Dacă $N = 2$, atunci $M ≤ 50.000$. La acest subtask avem două soluţii.
 
Prima ar fi să folosim un arbore de intervale pentru a simula operaţiile. Pentru fiecare nod din arborele de intervale (care ţine minte date despre intervalul de coloane $[l, r]$), trebuie să ţinem minte suma elementelor de pe linia 1 cu coloanele din intervalul respectiv, suma elementelor de pe linia 2 cu coloanele din intervalul respectiv, şi un lazy care să ne spună dacă trebuie să interschimbăm cele două linii pe care îl propagăm in fiii nodului. Această soluţie va avea complexitatea $O(Q * logM)$.
 
O altă soluţie mai uşor de implementat ar fi să grupăm coloanele în grupe de câte $B$ coloane. La un $update$, dacă o grupă este complet inclusă în intervalul respectiv, putem să ţinem minte ca şi la subtaskul 2 o valoare care să ne spună cu cât am rotit toate acele coloane din grupa respectivă. Dacă o grupă de coloane este doar parţial inclusă într-un $update$, putem să rotim fizic (ca şi la subtaskul 1) coloanele care sunt afectate de operaţie. Pentru fiecare grupă trebuie să menţinem şi sumele elementelor de pe fiecare linie. Ca să răspundem la un $query$ luăm toate grupele: dacă o grupă este total inclusă, putem să facem ca şi la subtaskul 2, să vedem care este poziţia adevărată a liniei pe care o vrem, altfel dacă o grupă este inclusa parţial, atunci putem să luăm cu brut elementele din $query$. Complexitatea pentru un $update$ sau un $query$ va fi $O(B * N + M / B)$. Deoarece $N = 2$, complexitatea finală va fi $O(Q * (B * N + M / B))$. Dacă fixăm $B = sqrt(M)$, vom obţine complexitatea finală $O(Q * sqrt(M))$.
 
h2. Subtask 4 (40 puncte)
 
La momentul acesta avem foarte multe soluţii care se încadrează în limita de timp pe anumite clase de teste: soluţia de la subtaskul 2 merge bine pe testele cu $M$ mic, dar iese din timp pe celălalte teste, prima soluţie de la subtaskul 3 merge pe teste cu $M$ mare (dacă îl adaptăm să meargă pe teste cu $N > 2$ în complexitate $O(Q * N * logM))$, iar a doua soluţie de la subtaskul 3 merge bine pe testele cu $M$ mare, dar merge prost pe teste cu $M$ mic (asta dacă ne fixăm $B$ la început ca şi o constantă, precum 300, 500 sau 420).
 
Putem să combinăm mai multe soluţii între ele pentru a obţine soluţii care să se încadreze în limita de timp.
 
**Cum combinăm soluţiile între ele?**
 
Dacă avem o complexitate de forma $N * B + M / B$, şi trebuie să ne alegem convenabil un $B$, cel mai eficient este să egalăm cei doi termeni şi să aflăm astfel $B-ul$. Astfel o să obţinem:
$N * B = M / B <=>$
$B^2 = M / N => B = sqrt(M / N)$
Varianta aceasta este optimă. Putem demonstra asta folosind inegalitatea mediilor care spune că $(a + b) / 2 &ge; sqrt(a * b)$, iar egalitatea se obţine dacă $a$ şi $b$ sunt egale. Astfel, dacă înlocuim termenii cu expresia noastră iniţială, o să obţinem că $(N * B + M / B) / 2 &ge; sqrt(N * M)$, deci $(N * B + M / B) &ge; sqrt(N * M)$ care este o constantă. Deci dacă egalăm cei doi termeni (aşa cum am procedat mai sus), vom obţine complexitatea optimă.
 
Acuma putem să combinăm toate soluţiile între ele şi să vedem ce obţinem:
 
# Putem combina soluţia de la subtaskul 2 cu prima de la subtaskul 3
# Putem combina soluţia de la subtaskul 2 cu a doua de la subtaskul 3
 
Totuşi, din punct de vedere al implementării ar însemna să implementăm două soluţii independente şi ar ieşi mult mai greoi implementarea. În continuare vom analiza mai mult soluţia de la subtaskul 3.
Complexitatea soluţiei este $O(Q * (N * B + M / B))$. Dacă folosim formula de mai sus, vom obţine că $B$ trebuie să fie $sqrt(M / N)$. Complexitatea finală va fi $O(Q * (N * sqrt(M / N) + M / sqrt(M / N))) = O(Q * sqrt(M * N))$.
 
De menţionat că $sqrt(M / N)$ poate fi mai mic decât $1$. Cum nu putem fixa un bucket cu 0, putem folosi funcţia $ceil()$ pentru a evita astfel de probleme. În cazul acesta, practic soluţia noastră care face mai multe bucketuri imită soluţia de la subtaskul 2.
 
Altă menţiune ar mai fi faptul că aici mărimea bucketului variază, şi este esenţial să avem grija de acest lucru şi să nu fixăm mărimea lui ca şi o constantă în cod.