1006 CCM

[•stef2n]

Aici puteți discuta despre problema CCM.

[•Florian]

Referitor la solutia postata in sectiunea Articole. Recurenta pentru best [ i ][ stare ], nu ar trebui sa fie    max( bst[ i-1 ][ stare ], bst[ i-1 ][ stare  - 2^j ] + 1 ), cu j vecin pt i ? Suma aia mi se pare un pic dubioasa. Imi cer scuze daca gresesc.

[•andrei-alpha]

Referitor la solutia postata in sectiunea Articole. Recurenta pentru best [ i ][ stare ], nu ar trebui sa fie    max( bst[ i-1 ][ stare ], bst[ i-1 ][ stare  - 2^j ] + 1 ), cu j vecin pt i ? Suma aia mi se pare un pic dubioasa. Imi cer scuze daca gresesc.

Partea cu calculatul lui bst nu e necesara ca bst[ i ][ stare ] = numarul de biti de 1 din stare. Nu are sens sa tii pentru alte stari.
Cred ca aia cu suma se referea la ccm[ i ][ stare ].

[•xtreme]

Poate cineva sa-mi scrie inapoi exact ce semnficatie are best[stare] si ccm[stare] cu i=1,n si stare=2^1, 2^16 din solutia oficiala?

L.E.: stare-2^j(2 la puterea j) inseamna stare cu bitul j egal cu 0?

[•PlayLikeNeverB4]

In solutia oficiala nu ar trebui sa fie [stare - 2^(j-1)] ? Daca j=1, atunci nu ultimul bit va fi cel eliminat ? (stare - 1). Si daca e asa, atunci am niste probleme la implementare, de exemplu cand stare=2 si j=1, pentru ca 2-1=1 (10 - 01 = 01 ) si ar trebui sa ramana 2 ( 10 ).

[•StarGold2]

Pentru cine ia TLE pe la ultimele 6 teste hint: puneti D(mask, i) in loc de D(i, mask) (adica incercati sa inversati indicii). Chestia asta este foarte folositoare pt ca accesul la memorie se face mult mai rapid. Asa am sarit eu de la 40 la 100 fara optimizari