|
Titlul: 449 Cast Scris de: Filip Cristian Buruiana din Mai 22, 2007, 14:24:29 Aici puteţi discuta despre problema Cast (http://infoarena.ro/problema/cast).
Titlul: Răspuns: 449 Cast Scris de: Ionescu Vlad din Septembrie 03, 2010, 18:33:44 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. Titlul: Răspuns: 449 Cast Scris de: Cezar Mocan din Septembrie 03, 2010, 22:18:58 Ai incercat sa implementezi dinamica cu memoizare? S-ar putea sa mearga ceva mai bine...
Titlul: Răspuns: 449 Cast Scris de: Ionescu Vlad din Septembrie 04, 2010, 13:11:31 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 :D Multumesc! Vlad. |