Problema kperms, Campion 2009
3De 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 4 2 3 1 |
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.
Pff… mi-e dor de campion… cate nopÈ›i nedormite si cate petreceri neonorate din cauza campionului (imi placea mai mult sa stau cu „echipa†de matefizinformaticieni decat sa-i fi vazut pe alÈ›ii cum dau la raÈ›e si la colÈ›u blocului)
Da e frumos. De ce nu mai lucrezi? Cine te opreste?Nu e neaparat nevoie sa intri la finala ci doar sa te „incalzesti”.Mai este algoritmiada pe infoarena care este si pentru studenti. 🙂
[…] This post was mentioned on Twitter by Avadanei Andrei and Avadanei Andrei, Andrei Avadanei. Andrei Avadanei said: Problema kperms, Campion 2009 http://bit.ly/dvtg5G #WorldIT […]