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.

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

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

* 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 exponentul lui $2$ care se poate obtine din primele $i$ fractii, astfel incat exponentul lui $3$ sa fie $x3$ si exponentul lui 5 sa fie {$x5$}. Tabloul {$D$} poate contine si indici negativi! Relatia de recurenta este urmatoarea:

{$D{~i, x3, x5~}$} = maxim({$D{~i-1, x3, x5~}$}, {$D{~i-1, x3-x3', x5-x5'~} + x2'$}), unde {$(x2' x3' x5')$} este tripletul asociat celei de a {$i$}-a fractii.
 
 

{$D{~i, x3, x5~}$} = maxim({$D{~i-1, x3, x5~}$}, {$x2' + D{~i-1, x3-x3', x5-x5'~}$}), unde {$(x2' x3' x5')$} este tripletul asociat celei de a {$i$}-a fractii.
Se observa ca nu este necesar sa retinem tot tabloul D, fiind convenabil sa retinem doar ultimele doua matrici la fiecare pas. Din considerente de memorie, este necesara retinerea unei singure matrici si actualizarea ei printr-o parcurgere convenabila a indicilor.
Dupa ce avem tabloul $D$ construit, aflam maxim({$2^D{~N, x3, x5~}^ * 3^x3^ * 5^x5^$}), cu $x3 ≥ 0$ si {$x5 ≥ 0$}. Pentru a compara doua numere $2^x1^ * 3^y1^ * 5^z1^$ si $2^x2^ * 3^y2^ * 5^z2^$ vom folosi logaritmarea si vom compara {$x1*ln2 + y1*ln3 + z1*ln5$} cu {$x2*ln2 + y2*ln3 + z2*ln5$}. Atunci cand am aflat o solutie optima, este necesara implementarea operatiilor pe numere mari, deoarece rezultatul nu se incadreaza in nici un tip de date conventional.
Complexitatea problemei este {$O(N^3^)$} de constanta 4*(log{~3~}400 000 000)*(log{~5~}400 000 000). Aceasta solutie obtine 100 de puncte.

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