|
Titlul: StringOfPowers Scris de: Cristian Strat din Ianuarie 08, 2005, 12:34:00 Ce idei aveti pentru problema de mai jos?
click aici (http://www.topcoder.com/stat?c=problem_statement&pm=3006&rd=5886) Titlul: StringOfPowers Scris de: Silviu-Ionut Ganceanu din Ianuarie 09, 2005, 13:54:42 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 :P. Cu bine, Silviu Titlul: StringOfPowers Scris de: Mircea Pasoi din Ianuarie 09, 2005, 23:08:38 Citat din mesajul lui: 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 :P. 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. Titlul: StringOfPowers Scris de: Silviu-Ionut Ganceanu din Ianuarie 09, 2005, 23:25:44 Yeap. Nu merge dinamica mea.
|