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 patratul cu colturile in $(i, j), (i + 2^di^, j + 2^dj^)$. Aceasta matrice se poate calcula cu usurinta in $O(logM * logN * M * N)$ calculand valorile incepand cu puterile mai mici ale lui $2$, in stil bottom-up. Putem apoi vedea in $O(1)$ care este gcd-ul elementelor din patratul 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 - dj], V[di][dj][i + h - di][dj], V[di][dj][i + h - di][j + w - dj])$. Nu mai ramane decat sa luam maximul dintre toate patratele 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 optim. 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 patratul 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, j + h - 1)$. Aceasta matrice se calculeaza folosind acelasi rationament. Rezultatul este $max(B[i][j])$, pentru toate perechile $i, j$ a.i $i + h ≤ M$ si $j + w ≤ N$. Acest algoritm ruleaza in $O(logN * N * M)$ timp si $O(N * M)$ memorie.

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

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 $N*logN$ 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.

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

private

public