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

Solutii Runda 2

Euclid

Gbc

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