StringOfPowers

[•wickedman]

Ce idei aveti pentru problema de mai jos?

click aici

[•silviug]

O idee:

Se iau toate puterile lui B care au mai putin de DIGITS cifre si se elimina cele care se pot obtine prin concatenare de puteri mai mici ca lungime. Dupa ce am facut acest lucru cred ca se face o dinamica simpla:

Count = Count[i - len[j]], cu i = 1, DIGITS si j = 1, Numarul de elemente din set (dupa eliminare)

Normal, cu observatiile de rigoare (len[j] <= i, etc)

Nu stiu daca e bine dar e un punct de pornire. Ar trebui sa implementez ce zic eu si apoi sa mai fac si un brute force care sa-mi verifice rezultatele. Asa poate ca as fi mai sigur pe ce zic, dar azi am altceva de facut .

Cu bine,

Silviu

[•domino]

O idee:

Se iau toate puterile lui B care au mai putin de DIGITS cifre si se elimina cele care se pot obtine prin concatenare de puteri mai mici ca lungime. Dupa ce am facut acest lucru cred ca se face o dinamica simpla:

Count = Count[i - len[j]], cu i = 1, DIGITS si j = 1, Numarul de elemente din set (dupa eliminare)

Normal, cu observatiile de rigoare (len[j] <= i, etc)

Nu stiu daca e bine dar e un punct de pornire. Ar trebui sa implementez ce zic eu si apoi sa mai fac si un brute force care sa-mi verifice rezultatele. Asa poate ca as fi mai sigur pe ce zic, dar azi am altceva de facut .

Cu bine,

Silviu

Din cate zici tu numarul 164 il numeri de doua ori ca e 1+64 si 16+4 (in baza 2), nu? Solutia oficiala se gaseste la http://www.topcoder.com/tc?module=Static&d1=tournaments&d2=tco04&d3=alg_finals_analysis si din cate am citit eu este un backtracking care pune cifrele pas cu pas cu ceva optimizari.

[•silviug]

Yeap. Nu merge dinamica mea.