Walker_INDICATII

Indicații de rezolvare


Solutia problemei foloseste metoda programarii dinamice.

Pentru primele doua subtaskuri, se poate folosi o recurenta de tipul dp[i][j] = numarul de moduri de a ajunge la nodul i dupa j minute , care poate fi optimizata la O(n * k) folosind sume partiale pe parcurs.

Pentru subtaskul al treilea se observa ca pe noi ne intereseaza doar valorile dp[1][j] si dp[2][j], deoarece celelalte valori sunt identice cu cea de la dp[2][j], ceea ce ne duce la reducerea recurentei la O(k).

Pentru obtinerea scorului maxim se va implementa recurenta de la subtaskul 3 folosind ridicarea la putere în timp logaritmic pe matrice.

ALTA INDICATIE
==============
NOTEZ CU A[K] NUMARUL DRUMURILOR DE LUNGIME K CE PLEACA DIN 1 SI AJUNG IN 1.
NR DRUMURILOR DE LUNGIME K-1 CE PLEACA DIN 1 SI AJUNG INTR-UN NOD J ESTE (N-1)^(K-1).
CEA DE-A K-A MUCHIE ESTE AUTOMAT J->1

DAR J NU TREBUIE SA FIE 1,
DECI DIN (N-1)^(K-1) SCADEM NR DR DE LUNGIME K-1 CE PLEACA DIN 1 SI AJUNG IN 1.
DECI A[K]=(N-1)^(K-1)-A[K-1].
SE SCRIE ACEASTA RELATIE PENTRU K: 1,2,…,K.

SE INMULTESC RELATIILE OBTINUTE CU PUTERILE LUI -1,
APOI SE ADUNA, SI RAMAN DOAR A[K] SI A1=0.
EXPRESIA LUI A[K] VA FI O PROGRESIE GEOMETRICA DE RATIE -(N-1).