449 Cast

[•filipb]

Aici puteţi discuta despre problema Cast.

[•vladii]

Salut!
Complexitatea mea la problema aceasta (la fel ca si in solutia oficiala) este de 3^N * N^2 si primesc OK doar pe primele 4 teste, pe restul am TLE. Nu am nici o idee despre ce sa mai optimizez... So, un hint ar fi foarte bine venit! Am vazut ca mai sunt useri care au facut saltul de la 40 la 100 de puncte si as vrea sa stiu si eu cum.

Multumesc!
Vlad.

[•CezarMocan]

Ai incercat sa implementezi dinamica cu memoizare? S-ar putea sa mearga ceva mai bine...

[•vladii]

Cum sa o implementez cu memoizare? Nu stiu, nu ma prind deloc la problema asta... Daca vrei, da-mi te rog un pic mai multe detalii.

LE: Am incercat sa memoizez si cu solve(stare) si cu solve(stare, nod). Cu solve(stare, nod) merge foarte greu pe calculatorul meu, iar cu solve(stare) merge aproximativ la fel ca dinamica fara memoizare. "stare" este un numar in baza 2, iar pentru fiecare "stare" parcurg toate numerele de la 1 la 2^(nrbiti) pentru a-mi forma stari de triti. Cred ca ramin la 40 de puncte la problema aceasta

Multumesc!
Vlad.