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 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.

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¹⁵. Numerele noastre fiind pana la 2³⁰ 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 Q₁ ≤ Q₂ ≤ ... ≤ 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₁ + Q_N + Q₂ + Q_N + ... + Q_N-1 + Q_N = (Q₁ + ... + 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)).