613 NKPerm

[•wefgef]

Aici puteţi discuta despre problema NKPerm.

[•sima_cotizo]

E corect in articol secventa urmatoare?

Cod:

...
        daca cate[i] != 0:     
            cate[i]--   
            cate[i+1]++   
            daca i = ultim:   
                // fara valori egale pe pozitii adiacente   
                rez += cate[i]*numara(cate, i+1)   
            altfel:   
                rez += (cate[i]+1)*numara(cate, i+1)   
            cate[i+1]++   
            cate[i]--
...

a doua oara nu trebuia sa facem cate[i+1]--, cate[ i]++ ? ... adica nu e un fel de back ce face aici?

[•Marius]

Ba da, cate[i+1] -- si cate[ i] ++. Trebuie sa se revina la valorile initiale.

[•sima_cotizo]

Ok, multumesc!

Eu nu prea am inteles partea asta. Adica : stim ca ultima cifra pusa apare de ultim ori (sau ca ultima cifra e ultim? ... cred ca de fapt apare de ultim ori)... facem un for si stim ca pt o valoare i avem cate[ i] numere care apar de i ori. Luam fiecare numar (teoretic) si il mai bagam o data la sfarsit, deci de aici vine rez += cate[ i] *numara(cate, i+1);... pe pseudocod, asta e cazul in care i!=ultim... dar de unde vine adunarea din else? ... adica dupa mine ar fi exact invers,

Cod:

daca (i!=ultim)
    rez+=cate[i]*numara(cate, i+1);
altfel
    rez+=(cate[i]-1)*numara(cate,i+1);

e corect? 

[•domino]

Pseudocodul din articol e corect deoarece ai decrementat cate[ i ] inainte.

[•sima_cotizo]

  ai dreptate

PS: am modificat eu articolul ca sa fie cum a zis si Marius mai sus...

[•domino]

Foarte bine ca l-ai modificat.

[•C_Ovidiu]

  Imi poate explica cineva cum fac aici memoizarea ? Sunt in total 20^6*6 rezultate care vine cam 1500MB

[•pauldb]

Cu map din STL.

[•C_Ovidiu]

  Si deci daca nu stiu si nici n-am de gand sa invat STL nu am sanse sa fac pb ?

[•wefgef]

Poti sa bagi cu hash-uri