Problema admite o rezolvare triviala de complexitate {$O(N^2^log MAX)$}, unde $MAX$ este maximul dintre cele $N$ numere ale multimii {$M$}: pentru fiecare pereche de numere din multimea data se calculeaza cel mai mare divizor comun folosind algoritmul lui Euclid. O astfel de rezolvare obtine 20-30 de puncte, in functie de prezenta unor optimizari. Rezolvarea optima are complexitatea {$O(MAX log MAX)$} si se baza pe faptul ca {$O(N/1 + N/2 + N/3 ... + N/N)$} = {$O(N log N)$}, pentru orice {$N$}.
Din numarul total de perechi, {$N*(N-1)/2$}, vom scadea numarul de perechi {$(x y)$}, astfel incat $x$ si $y$ nu sunt prime intre ele si vom obtine rezultatul cerut. Notam cu $Res$ numarul de perechi {$(x y)$}, cu {$cmmdc(x, y) > 1$}. Pentru a afla efectiv numarul $Res$ vom folosi procedeul includerii si excluderii. Fie {$x{~i~}$} numarul de numere din $M$ care se divid cu {$i$}. Vectorul $x$ se poate calcula in {$O(MAX log MAX)$}: pentru fiecare numar $i$ de la $1$ la $MAX$ verificam cate din numerele {$i$}, {$2i$}, {$3i$} ... {$[MAX/i]*i$} apartin multimii {$M$}. Consideram toate numerele $P$ ce se scriu ca produs de numere prime, unde fiecare numar prim este folosit cel mult o data. Daca numarul de numere prime din descompunerea lui $P$ este un numar impar, adunam {$x{~P~}$} la {$Res$}. Altfel, din {$Res$} scadem {$x{~P~}$}.

Rezolvarea de complexitate {$O(MAX log MAX$} asigura obtinerea punctajului maxim.

h2(#aliens). 'Aliens':problema/aliens

Problema se rezolva cu ajutorul programarii dinamice. Fiecare fractie din cele date se poate scrie ca un produs de forma {$2^x^*3^y^*5^z^$}, unde {$x$}, $y$ si $z$ sunt numere intregi. Daca codificam fiecare fractie prin tripletul corespunzator, problema revine la a selecta anumite triplete {$(x{~1~}, y{~1~}, z{~1~})$}, {$(x{~2~}, y{~2~}, z{~2~})$}... {$(x{~K~} y{~K~} z{~K~})$} din cele N astfel incat:
 
* {$x{~1~} + x{~2~} + ... + x{~K~} ≥ 0$}
* {$y{~1~} + y{~2~} + ... + y{~K~} ≥ 0$}
* {$z{~1~} + z{~2~} + ... + z{~K~} ≥ 0$}
* 2^x{~1~} + x{~2~} + ... + x{~K~}^*3^y{~1~} + y{~2~} + ... + y{~K~}^*5^z{~1~} + z{~2~} + ... + z{~K~}^ sa fie maxim posibil.
 
Problema se rezolva prin programare dinamica. Fie {$D{~i~}{~x3~}{~x5~}$} valoarea maxim posibila pentru
 
 
 
 
 

h2(#tunel). 'Tunelul groazei':problema/tunel
h2(#nkperm). 'NKPerm':problema/nkperm