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 ...)
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]]++
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]]++
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
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.