Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-10 14:44:35.
Revizia anterioară   Revizia următoare  

Solutii Runda 2

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 + 2di - 1, j + 2dj - 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 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.

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 215. Numerele noastre fiind pana la 230 numarul de biti se va calula pe bucati: nbit[i&32767] + nbit[i>>15] ( & este operatia AND, >> este operatia de shiftare).

Hypernet

Vom sorta planetele crescator, in functie de numarul de locuitori. Practic, vom considera o renumerotare a planetelor astfel incat Q1 ≤ Q2 ≤ ... ≤ QN. Sa calculam acum o limita inferioara pentru costul retelei cerute. Vom defini costul unei muchii (i,j) ca fiind valoare Qi+Qj. 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 Qi+QN. Asadar, o limita superioara pentru costul arborelui este CARB=Q1 + QN + Q2 + QN + ... + QN-1 + QN = (Q1 + ... + QN-1) + (N-1) * QN. 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 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.
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)).