infoarena informatica de performanta

Vanatoare

Problema se rezolva cu ajutorul programarii dinamice. Sa notam cu M_i multimea {j | al j-lea bit din reprezentarea lui i in baza 2 este 1}. Fie D_i numarul minim de vanatori necesari pentru a omori toti mistretii cu numere de ordine din multimea M_i. Relatia de recurenta va fi D_i = 1 + minim(D_Mi-Mj), dupa toate numerele j cu proprietatea ca multimea M_j este inclusa in multimea M_i si toti mistretii din M_j pot fi omorati de acelasi vanator, situat la o coordonata intre 0 si T. Pentru a stabili daca toti mistretii din M_j pot fi omorati de acelasi vanator, vom realiza o preprocesare. Astfel, A_i va fi true daca si numai daca putem plasa un vanator intre 0 si T care sa omoare toti mistretii din M_i. O optimizare evidenta care imbunatateste cu mult timpul de executie este ca pentru o stare i sa eliminam acele j despre care stim sigur ca A_j va fi false. Astfel, daca la un moment dat alegem un numar j pentru care A_j va fi false nu are rost sa consideram nici un numar k, pentru care M_j inclus in M_k, pentru ca A_k va fi sigur false.
Pentru a calcula valoarea lui A_i trebuie sa determinam cel mai mic numar natural P (daca exista) astfel incat vanatorul plasat in P sa poata omori toti mistretii din M_i. Aceasta relatie este echivalenta cu P % v_j = c_j, pentru orice j inclus in M_i. Pentru a afla numarul P pentru o stare i putem folosi teorema chineza a resturilor. Nu este necesar insa sa aplicam aceasta teorema de la inceput pentru fiecare stare, ci este suficient sa vedem care este ultimul bit j de 1 din i, si sa combinam solutia pentru M_i-{j} si {j}. A_i va fi true daca si numai daca 0 ≤ P ≤ T.
Complexitatea finala va fi O(2^N * N) + O(3^N) = O(3^N).