h2. 'Gbc':problema/gbc
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 $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))$}.