495 Numere 6

[•dornescuvlad]

si eu fac in O(Nr_div(b) * a * 10) si iau doar 80 ?
nu se poate mari timpul de executie ?

[•new_programmer]

O idee cum as putea rezolva problema asta prin backtracking?

[•blasterz]

ideea e ca produsul il poti obtine destul de repede din cifre > 1 (de ex 1024 = 10 de 2)
generezi prin back siruri de cifre > 1 astfel incat sa obtii produsul dorit si celelalte cifre pui 1.
Trebuie sa mai vezi in cate moduri poti aranja ca sa obtii un numar.

[•devilkind]

Nu asa se face problema. Asta mie mi se pare un fel de ciucuiala, desi probabil complexitatea worst-case e buna.
Incearca sa pleci de la dinamica clasica a[ i ][ j ] - numarul de numere de i cifre care dau restul j la impartirea cu B. Asta are complexitate O(A * B) si ar trebui sa o optimizezi.
Hint: memoria folosita e O(log A * B)

[•blasterz]

da, evident ca solutia optima e O(B log A) dar in solutiile oficiale de la OJI existau 2 solutii:
una in O(a * sqrt b) si una cu backtracking... baiatul a intrebat cum se face prin backtracking...

[•new_programmer]

Intai, multumesc de raspunsuri.
@Savin Tiberiu
Nu imi dau seama care valoare din matricea aceea e rezultatul. a[A][0] nu e acela deoarece acest rezultat ia in cont si numerele cu produsul cifrelor g*B, unde g e numar natural.

[•blasterz]

E gresita relatia data de devilkind. (acum am vazut si eu)
Cel mai probabil a vrut sa zica asa:

dp[ i ][ j ] = numarul de numere de i cifre cu produsul cifrelor j

raspunsul e in dp[ A ][ B ]. complexitatea O(A * B) daca se implementeaza direct.

De aici se poate optimiza obtinandu-se O(A * sqrt B) sau optim O(B logA)
 

[•devilkind]

Ah da scz. Nu am citit atent enuntul. Am avut impresia ca trebuie ca produsul sa divida numarul b, nu sa fie egal.

[•new_programmer]

Iau 90 de puncte, din cauza TLEului de la testul 9.Nu imi dau seama cum as putea scoate O(B logA).Nu vad cum as putea folosi cautarea binara aici si vazand complexitatea aia nu imi vine nimic altceva in cap.Un hint?

[•blasterz]

Un numar de i cifre (i = par) poate fi obtinut concatenand 2 numere de i/2 cifre. Iar unul de i cifre (i = impar)
poate fi obtinut dintr-un numar de i-1 cifre adaugand o cifra. (nu are legatura cu cautarea binara)

[•FlorinHaja]

Ma puteti ajuta, va rog, cu niste idei? Am optimizat la maxim problema, luand prima data nr. de solutii pe puterile lui 2, apoi calculand in functie de bitii lui n. De asemenea, aloc memorie doar pt. randurile de matrice de care am nevoie. Nu scot mai mult de 90 de puncte  
http://www.infoarena.ro/job_detail/1771869

[•Bodo171]

Ma puteti ajuta, va rog, cu niste idei? Am optimizat la maxim problema, luand prima data nr. de solutii pe puterile lui 2, apoi calculand in functie de bitii lui n. De asemenea, aloc memorie doar pt. randurile de matrice de care am nevoie. Nu scot mai mult de 90 de puncte  
http://www.infoarena.ro/job_detail/1771869

Ai putea incerca sa nu scrii using namespace std si sa folosesti citirea din C.Eu asa am reusit sa  intru in memorie la alta problema la care nu reuseam cu streamuri din cauza ca avea o limita mica la care se simtea schimbarea.

[•FlorinHaja]

Ai putea incerca sa nu scrii using namespace std si sa folosesti citirea din C.Eu asa am reusit sa  intru in memorie la alta problema la care nu reuseam cu streamuri din cauza ca avea o limita mica la care se simtea schimbarea.

Mersi mult! Esti genial!   Am luat suta  
Dovada: http://www.infoarena.ro/job_detail/1772551

[•krityx]

Eu incerc sa fac un backtracking, si iau WA pe 3 teste.

Practic generez toate combinatiile de cifre care au produsul ala si apoi calculez nr de scrieri ale unui numar de a cifre cu fiecare combinatie.
Sa zicem ca am gasit o combinatie din n cifre care nu-s neaparat distincte.

Calculez Sol = Combinari(a, n) * n! (adica Aranjamente(a, n)) = nr de posibilitati de a scrie un nr de a cifre cu n cifre > 1 distincte.

Apoi pentru fiecare cifra Ai, 1 < i < 10 impart Sol prin fact(Ai), unde Ai e frecventa cifrei i.

E ceva gresit in rationamentul asta ?

Edit:
Problema era de la impartirea modulo ceva. Luam 90p facand (A/B) mod p. Cam mult pentru noroc chior. Cu invers modular am luat 100.

[•Marius7122]

Iau WA pe toate testele, cu toate ca algoritmul meu a mers pentru toate testele pe care l-am incercat(si cele din kitul oji). Mai are cineva problema asta?