300 Diviz

[•DITzoneC]

Aici puteţi discuta despre problema Diviz.

[•gurney]

            N-am inteles prea bine evitarea numararii de mai multe ori a unui subsir identic. In solutia oficiala scrie "pentru a numara subsirurile distincte ( adica sa nu numaram subsiruri egale de doua ori ), daca suntem in starea (j, i, r) actualizam starea (j+1, first[cif][i+1], (r*10+cif) mod K) daca si numai daca intre pozitiile i+1 si first[cif][i+1]-1 in numarul N nu mai apare nici o cifra cif", dar daca first[cif][i+1] indica prima pozitie a cifrei cif in numar, atunci conditia de mai sus sigur e indeplinita. Iau numa 20p pt ca nu implementez bine chestia asta. 

[•bogdan2412]

Nu stiu exact ce vroia sa zica autorul articolului, nici eu nu am inteles cand am citit

Starile (j, i, r) inseamna numarul de subsiruri care se termina fix la pozitia i, au lungimea j si dau restul r. Trebuie sa initializezi pentru subsirurile de lungime 1 doar primele aparitii ale fiecarei cifre, pentru a nu le numara de mai multe ori. Astfel starile (1, first[cif][0], cif % K) sunt initializate cu 1 pentru cif de la 1 la 9 (subsirurile trebuie sa fie nenule si trebuie sa nu inceapa cu 0), iar de la o stare (j, i, r) actualizezi tot timpul starea (j + 1, first[cif][i + 1], (r * 10 + cif) % K). Aduni pe parcurs toate starile cu j cuprins intre A si B si cu r == 0 si ai solutia.

[•gurney]

           -Dap. Asa iese. Ar trebui modificat articolul cu pricina. Totusi iau un tle pe ultimu test. [working on it...]

[•domino]

           -Dap. Asa iese. Ar trebui modificat articolul cu pricina. Totusi iau un tle pe ultimu test. [working on it...]

E wiki, poate modifica oricine.

[•pocaitu]

   E ceva special pe testele 3,4,6,7,8,9,10 ?? Ca iau la toate incorect

[•astronomy]

Nu cred ca sunt speciale atatea teste, ai un bug ceva in program. Uite un test mai mic, poate te ajuta

Cod:

10 3 7
100102010

Cod:

60

[•pocaitu]

   da, imi da 60

[•astronomy]

In cazul asta da-ti teste singur, fa un brute-force si compara rezultatele cu programul tau. Ar trebui sa gasesti repede ca la prea multe teste ai WA.

[•vendetta]

Salut ! Am facut si eu o dinamica in B*N*K*10 dar iau TLE pe ultimul test; ceva idei de optimizare : http://infoarena.ro/job_detail/779421?action=view-source .

[•StarGold2]

Stiu ca nu s-a mai postat de mult timp la problema aceasta, dar nu cumva limita de timp este cam mica? Adica initial era mai mare de 0.2 secunde, iar acum sunt foarte multe surse (printre care si a mea) care primesc 90 pct cu tle pe ultimul test. Daca se poate sa se mareasca limita cu 0.05 secunde ar fi nemaipomenit 

[•freak93]

Da, am marit cu 0.05 ca sa pastram regula cu limite de timp de 2 ori cat sursa oficiala. Am reevaluat toate surseled in 2013 incoace.