Problema kperms, Campion 2009

De curand Gigel a devenit atras de permutari, in special de acele permutari cu N elemente ce contin exact K secvente descrescatoare maximale.

Cerinta

Scrieti un program care sa determine cate permutari de N elemente cu exact K secvente descrescatoare maximale exista?

Date de intrare

Fisierul de intrare kperms.in va contine o singura linie pe care se afla numerele naturale N si K separate printr-un spatiu.

Date de iesire

Fisierul de iesire kperms.out va contine o singura linie pe care va fi scris numarul de permutari de N elemente cu exact K secvente descrescatoare maximale modulo 666013.

Restrictii

• 2 ≤ N ≤ 1000
• 1 ≤ K ≤ N
• Prin secventa se intelege o succesiune de de elemente situate pe pozitii consecutive. O secventa descrescatoare este considerata maximala daca nu mai poate fi adaugat in secventa un element (evident, la unul dintre capetele secventei) astfel incat secventa sa ramana descrescatoare.

Exemple

kperms.in	kperms.out	Explicatie
4 2	11	Cele 11 permutari sunt: 1 4 3 2 2 1 4 3 2 4 3 1 3 1 4 2 3 2 1 4 3 2 4 1 3 4 2 1 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2

Solutie

Aceasta problema are nevoie de o tehnica ce se bazeaza pe programare dinamica. Vom considera
Vom considera :
d[i][j] = cate permutari de i elemente cu j secvente descrescatoare maximale

Presupunem ca avem o permutare cu i-1 elemente si cu j secvente descrescatoare maximale. Observam ca putem insera elementul i intre i pozitii (la inceput, la sfarsit, sau intre oricare 2 elemente consecutive).
Daca introducem pe i inaintea uneia dintre cele j secvente numarul de secvente descrescatoare va ramane la fel
iar daca inseram in celelalte i – j + 1 pozitii numarul de secvente descrescatoare creste cu 1.

Recurenta va ajunge astfel:

d[1][1] =1 
d[i][j] = (i – j + 1) * d[i – 1] [j – 1]  + j * d[i – 1][ j ]  

Rezolvarile mele difera putin, eu am folosit doua abordari mai „ciudate”, ca de obicei. In ambele situatii m-am folosit de faptul ca datorita recurentei dezvoltate mai sus, vom avea nevoie de doar de ultimile doua linii din matrice.

In primul caz am folosit doi pointeri cu care am jonglat pentru a schimba intre ele liniile, prima devenind ultima si invers.Solutia o puteti descarca de aici.
Cea de-a doua situatie se bazeaza pe acelasi lucru, doar ca am folosit doar un singur vector si doua variabile care schimba pozitiile indicilor si muta locatiile la inceputul vectorului sau la pozitia n+ceva .Solutia a doua o puteti descarca aici.