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:

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.

* 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~}$}, {$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.

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~}, x2' + D{~i-1, x3-x3', x5-x5'~}$}), unde {$(x2' x3' x5')$} este tripletul asociat celei de a {$i$}-a fractii.
Din considerente de memorie nu vom retine tot tabloul {$D$}. Deoarece elementele de pe pozitii de forma ({$i, a, b$}) depind doar de elemente de pe pozitii de forma ({$i, a', b'$}) vom retine o singura matrice in locul unui tablou tridimensional si vom actualiza elementele din aceasta matrice 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 logaritma 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~}MAX)*(log{~5~}MAX)$}, unde {$MAX = 400.000.000$}. Aceasta solutie obtine 100 de puncte.
h2(#tunel). 'Tunelul groazei':problema/tunel