NKPerm

Vom presupune ca avem o functie care determina cate (N,K) permutari exista care incep cu un prefix dat putem efecuta ambele operatii intr-un mod relativ simplu. Pentru a rezolva operatia de tip A putem folosi aceasta functie ca sa numaram cate permutari sunt mai mici din punct de vedere lexicografic decat cea data astfel: luam fiecare prefix al permutarii date si determinam cate permutari exista care incep cu acesta si care au urmatorul element mai mic decat elementul respectiv din permutarea data.
Sa luam permutarea din exemplu (1 3 2 1 2 3). Vom adauga rezultatele pentru prefixele:
(1 1 ...)
(1 2 ...)
(1 3 1 ...)
(1 3 2 1 2 1 ...)

Urmeaza pseudocodul pentru algoritmul descris:
rez = 1
aparitii[1..N] = {0}
pentru i = 1, N*K:
   pentru j = 1, P[i]-1:
       daca j!=P[i-1] si aparitii[j] < K:
           rez += numara(P[1..i-1]+[j])
   aparitii[P[i]]++
Cum operatia B este practic inversa operatiei A rezolvarea este foarte asemanatoare. Vom determina prefixul permutarii cautate element cu element, folosind functia de numarare:
rez = 0
aparitii[1..N] = {0}
pentru i = 1, N*K:
   pentru j = 1, N:
       daca j!=P[i-1] si aparitii[j] < K:
           daca rez+numara(P[1..i-1]+[j]) >= X:
               P[i] = j 
               break
           altfel:
               rez += numara(P[1..i-1]+[j]) 
   aparitii[P[i]]++
Ramane doar sa vedem acum cum putem determina in mod eficient cate (N,K) permutari exista cu un prefix dat. O prima observatie ar fi ca putem reprezenta o un prefix ca un vector de aparitii pentru numerele de la 1 la N impreuna cu un numar reprezentand ultimul element pus in permutare. Putem folosi aceasta reprezentare ca sa scriem urmatoarea functie recursiva:
numara(aparitii[], ultim):
    daca rezultatul pentru (aparitii[], ultim) a mai fost calculat:
        returneaza rezultatul stocat
    daca aparitii[1..N] = {K,K,...,K}:
        returneaza 1
    rez = 0
    pentru i = 1, N:
        daca i != ultim si aparitii[i] < K:
            aparitii[i]++
            rez += numara(aparitii, i)
            aparitii[i]--
    stocheaza rez pentru (aparitii[], ultim)
    returneaza rez
Putem observa ca functia folosesete tehnica de memoizare pentru a nu calcula acelasi rezultat de mai multe ori, dar din pacate numarul de stari posibile este mult prea mare (KN*N) pentru a reprezenta o solutie eficienta. Totusi, putem face urmatoarea observatie: pentru un prefix dat nu ne intereseaza efectiv ce numere apar in prefix, ci de cate ori apar fiecare. Spre exemplu rezultatul pentru prefixul (1 2 1 3 2 ...) va fi acelasi cu rezultatul pentru prefixele (2 1 3 1 2 ...), (13 5 13 27 5 ...), etc.. Astfel putem reprezenta un prefix ca un vector cate[0...K] unde cate[i] este numarul de valori care apar de i ori in prefix. De asemenea, mai trebuie sa retinem si de cate ori apare in prefix ultima valoarea pusa. Putem acum rescrie functia de numarare:
numara(cate[], ultim):
    daca rezultatul pentru (cate[], ultim) a mai fost calculat:
        returneaza rezultatul stocat
    daca cate[K] = N:
        returneaza 1
    rez = 0
    pentru i = 0, K-1:
        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]++
    stocheaza rez pentru (cate[], ultim)
    returneaza rez

Putem estima ca numarul de stari in cazul acesta este N(K+1)*(K+1), care este destul de mare pentru N = 20, K = 5 (desi mult mai mic decat in cazul precedent). Cum cate[0]+cate[1]+...+cate[K] ≤ N numarul de stari prin care se trece efectiv este mult mult mai mic decat aceasta prima estimare.

Detalii de implemetare

  • O codificare rapida a starilor poate fi reprezentarea lor sub forma unui numar de lungime K+2 in baza N+1, codificare care incape intr-un intreg pe 32 de biti.
  • In functia de numarare ne putem da seama in momentul in care rezultatul este mai mare de 255 (limita impusa in enunt), si putem returna direct valoarea 255 fara a afecta corectitudinea solutiei. Aceasta optimizare reduce mult numarul starilor care sunt parcurse, deoarece pentru foarte multe stari rezultatul depaseste 255.
  • Pentru a verifica daca un rezultat a mai fost calculat deja se poate folosi o tabela hash, dar mai simplu pentru programatorii C++ ar fi fost sa foloseasca un map (desi nu are complexitate O(1) optimizarile anterioare sunt mai mult decat suficiente pentru a face solutiile care folosesc map sa se incadreze in timp)

Solutia oficiala care implementeaza ideile descrise mai sus ruleaza sub 0.1s si parcurge ~100.000 de stari pe testele cele mai mari.