in primo luogo, durante la prova il mio referente ha chiarito che (stranamente) i segmenti possono anche “tornare indietro”, ovvero puoi fare cose tipo A-B-A. Ciò è importante per poter implementare l’algoritmo in DP, altrimenti avresti ottenuto una ricerca completa (che comunque non sarebbe stata troppo lenta in quanto la sequenza si sarebbe interrotta prematuramente con al più 8 segmenti, mentre k può essere molto più grande…)
Do l’approccio bottom-up. Spero ti piaccia.
Sia A_k una matrice 3\times3 che indica, per ogni a_{i,j} \quad (0 \leq i,j <3), il numero di percorsi che iniziano in a_{i,j} e hanno lunghezza k. Poniamo che a_{i,j} = 1 \quad \forall a_{i,j} \in A_0 (un percorso a k segmenti deve avere k+1 vertici, quindi tanti percorsi da 0 segmenti contano un vertice solo).
In altre parole avremo questo:
A_0 =
\begin{pmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1
\end{pmatrix}
Vediamo come costruire la soluzione di A_{k+1} dato A_k. Sia (i,j) una coppia di coordinate. Il numero di possibili percorsi che iniziano lì e sono lunghi k+1 è la somma dei percorsi che partono da un vertice adiacente di lunghezza k.
Quindi avremo:
A_1 =
\begin{pmatrix}
3 & 5 & 3 \\
5 & 8 & 5 \\
3 & 5 & 3
\end{pmatrix}
E se fai la somma di ogni elemento ottieni 40.
Continuo per k = 2:
A_1 =
\begin{pmatrix}
18 & 24 & 18 \\
24 & 32 & 24 \\
18 & 24 & 18
\end{pmatrix}
la cui somma fa 200. Il problema ti chiede di inserire la somma cumulata delle matrici quindi avresti 240.
Se non ti va di memorizzare una matrice, osserva che gli angoli e i lati sono uguali, quindi basta che memorizzi il valore di angoli, lati e centro e sei a cavallo.
Ad esempio, se chiamiamo c_k uno dei 4 valori “in angolo” alla matrice a_k, s_k uno dei valori a lato e m_k il valore centrale, abbiamo:
\begin{align}
c_k &= 2\cdot s_{k-1} + m_{k-1} \\
s_k &= 2\cdot c_{k-1} + 2\cdot s_{k-1} + m_{k-1} \\
m_k &= 4\cdot s_{k-1} + 4\cdot c_{k-1}
\end{align}
Poiché ti interessa sempre e solo lo stato precedente, puoi pure memorizzare una riga per k dispari, una per k pari e usare quindi solo O(1) di memoria.
Sono stanco per controllare ma penso che si potrebbe fare binary lifting e calcolare in O(\log N) la soluzione. Tuttavia onestamente penso che già l’approccio O(K) spaziale fosse sufficiente in quanto K dovrà essere basso perché il risultato, che è esponenziale rispetto a K, stia in un int (o long long), e il risultato non era in modulo.
