infoarena informatica de performanta

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₁, y₁, z₁), (x₂, y₂, z₂)... (x_K y_K z_K) din cele N astfel incat:

• x₁ + x₂ + ... + x_K ≥ 0
• y₁ + y₂ + ... + y_K ≥ 0
• z₁ + z₂ + ... + z_K ≥ 0
• 2^{(x₁ + x₂ + ... + x_K)} * 3^{(y₁ + y₂ + ... + y_K)} * 5^{(z₁ + z₂ + ... + z_K)} sa fie maxim posibil.

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' ×3' 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-1, 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 D_{N, x3, x5} ≥ 0, 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³) de constanta 4*(log₃MAX)*(log₅MAX), unde MAX = 400.000.000. Aceasta solutie obtine 100 de puncte.