h2. 'Gbc':problema/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^15^$}. Numerele noastre fiind pana la {$2^30^$} numarul de biti se va calula pe bucati: {$nbit[i&32767] + nbit[i>>15]$} ( $&$ este operatia {$AND$}, $>>$ este operatia de shiftare).
 

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