h1. Solutii Runda 1
h1. Solutii Runda 2
h2. 'Euclid':problema/euclid
Problema se poate rezolva calculand gcd-ul patratelor ce au lungimile laturilor puteri ale lui $2$. Astfel tinem o matrice $V[0..LOGM][0..LOGN][1..M][1..N]$, unde $V[di][dj][i][j]$ reprezinta gcd-ul numerelor din dreptunghiul cu colturile in $(i, j), (i + 2^di^ - 1, j + 2^dj^ - 1)$. Aceasta matrice se poate calcula cu usurinta in $O(logM * logN * M * N)$ incepand cu puterile mai mici ale lui $2$, in stil bottom-up. Putem apoi vedea in $O(1)$ care este gcd-ul elementelor din dreptunghiul cu colturile in $(i, j), (i + w - 1, j + h - 1)$. Pentru aceasta, mai intai sa luam $di = [log h]$ si $dj = [log w]$. Numarul cautat este $gcd(V[di][dj][i][j], V[di][dj][i][j + w - 2^dj^], V[di][dj][i + h - 2^di^][dj], V[di][dj][i + h - 2^di^][j + w - 2^dj^ ])$. Nu mai ramane decat sa luam maximul dintre toate dreptunghiurile posibile. Aceasta solutie foloseste $O(logN * logM * N * M)$ spatiu si timp.
Desi solutia de mai sus ar fi obtinut punctaj maxim, problema se poate rezolva si mai elegant. Astfel, in loc sa tinem tabela cu toate puterile lui $2$ putem calcula $A[1..M][1..N]$ unde $A[i][j]$ e gcd-ul elementelor din dreptunghiul cu colturile in $(i, j), (i, j + w - 1)$. Aceasta matrice poate fi calculata in $O(logN * N * M)$ folosind acelasi rationament ca mai sus. De asemenea, trebuie sa mai calculam o matrice $B[1..M][1..N]$ unde $B[i][j]$ tine gcd-ul elementelor din $A$ din dreptunghiul $(i, j), (i + h - 1, j)$. Aceasta matrice se calculeaza analog cu matricea A. Rezultatul este $max(B[i][j])$, pentru toate perechile $i, j$ a.i $i + h - 1 ≤ M$ si $j + w - 1 ≤ N$. Acest algoritm ruleaza in $O((logN + logM) * N * M)$ timp si $O(N * M)$ memorie.
h2. 'Gbc':problema/gbc
Sunt in total combinari de $k$ luate cate $n$ in care putem alege nodurile multimii {$A$}. Pentru fiecare din aceste modalitati se face un $AND$ intre toate liniile din matricea de adianceta corespunzatoare nodurilor alese. Nodurile ramase cu $1$ in urma {$AND$}-ului sunt noduri care pot fi alese in multimea {$B$}, avand drumuri catre toate nodurile din multimea {$A$}. Pentru o selectie a multimii $A$ vom avea combinari de $X$ luate cate $M$ posibilitati de a alege multimea {$B$}, unde $X$ este numarul de $1$ ramas in urma {$AND$}-ului. Matricea de adiacenta se va retine codificata pe biti, deci {$AND$} pe linii se reduce la {$AND$} intre numere. Pentru a numara usor cati de $1$ avem intr-un numar se preproceseaza {$nbit[i]$} numarul de biti ai numarului $i$ pentru toate numerele pana la {$2^15^$}. Numerele noastre fiind pana la {$2^30^$} numarul de biti se va calula pe bucati: {$nbit[i&32767] + nbit[i>>15]$} ( $&$ este operatia {$AND$}, $>>$ este operatia de shiftare).
h2. 'Hypernet':problema/hypernet
Vom sorta planetele crescator, in functie de numarul de locuitori. Practic, vom considera o renumerotare a planetelor astfel incat {$Q{~1~} ≤ Q{~2~} ≤ ... ≤ Q{~N~}$}. Sa calculam acum o limita inferioara pentru costul retelei cerute. Vom defini costul unei muchii ({$i,j$}) ca fiind valoare {$Q{~i~}+Q{~j~}$}. Reteaua consta dintr-un arbore avand $N-1$ muchii si inca {$K-(N-1)$} muchii suplimentare. Vom privi arborele ca avand radacina in nodul {$N$}. In acest fel, fiecare nod de la $1$ la $N-1$ va fi legat de o muchie catre tatal lui. Aceasta muchie are un cost de cel mult {$Q{~i~}+Q{~N~}$}. Asadar, o limita superioara pentru costul arborelui este {$CARB=Q{~1~} + Q{~N~} + Q{~2~} + Q{~N~} + ... + Q{~N-1~} + Q{~N~} = (Q{~1~} + ... + Q{~N-1~}) + (N-1) * Q{~N~}$}. O limita superioara pentru costul tuturor celor $K$ muchii este data de $CARB$ + costul celor mai mari $K-(N-1)$ muchii din cele ramase (fara muchiile {$i - N$}). Sa consideram aceasta limita superioara pentru costul celor $K$ muchii ale retelei ca fiind {$CK$}.
Acum, costul retelei are o limita inferioara data de {$CK + 2 * (suma_totala_a_costurilor_muchiilor - CK) = 2 * suma_totala_a_costurilor_muchiilor - CK$}. Este clar ca doar $K$ perechi de noduri au distanat $1$ intre ele, celelalte perechi avand distanta de cel putin {$2$}. Si din formula se observa ca este de dorit sa avem un cost cat mai mare pentru cele $K$ muchii alese ca facand parte din retea.
Cu aceste considerente, reteaua va fi reprezentata de muchiile {$(1,N), (2,N), .., (N-1,N)$} si cele mai mari {$K-(N-1)$} muchii din cele ramase. Aceasta retea are distanta $2$ intre oricare pereche de noduri care nu sunt legate direct si are costul egal chiar cu limita inferioara precizata mai sus.
Asadar, problema ramasa este aceea de a alege cele mai mari {$K-(N-1)$} muchii avand ambele capete in multimea {${1,2,..,N-1}$}. Doua variante simple au complexitate $O(N*K)$ si {$O(K*logN)$}, insa vor depasi limita de timp.
O solutie acceptabila ar consta in a cauta binar valoarea celei mai mici muchii din cele $K-(N-1)$ pe care mai dorim sa le alegem si sa calculam in $O(N)$ cate perechi de noduri au costul mai mare sau egal cu valoarea fixata in cautarea binara. Vom alege cea mai mare valoare pentru care exista {$X >= K-(N-1)$} muchii cu cost mai mare sau egal cu ea.
Daca {$X=K-(N-1)$}, am gasit muchiile cautate. Daca $X>K-(N-1)$ este din cauza ca exista prea multe muchii cu acelasi cost maxim gasit. In aceasta situatie, putem scadea din costul total al muchiilor gasite {$costul_maxim_gasit * (X - (K - (N-1)))$} pentru a obtine costul total al celor mai mari $K-(N-1)$ muchii.
Solutia finala afisata va fi {$CK + 2 * (suma_totala_a_costurilor_muchiilor - CK)$}, unde $CK$ a fost definit anterior. Complexitatea algoritmului este {$O(N * log(N) * log(CMAX))$}.
