Ciao a tutti,
avrei bisogno di una mano per risolvere fractal graphs stando nel limite di tempo.
La soluzione che adotto ora è semplicemente un ciclo for che sviluppa la successione ricorsiva:
N(i) = 3N(i-1)+2A(i-1)
A(i)=3N(i-1) + 3A(i-1)
Tuttavia, per input grandi questo metodo ovviamente non può essere applicabile, e personalmente non riesco a trovare il modo di ridurre tale definizione ricorsiva ad una diretta.
provo a metterti sulla strada giusta
se V_i=3V_{i-1}+2E_{i-1} e E_i=3V_{i-1}+3E_{i-1}, possiamo anche dire che
V_i= 3(3V_{i-2}+2E_{i-2}) + 2(3V_{i-2}+3E_{i-2}) = 15V_{i-2} + 12E_{i-2} e E_i= 3(3V_{i-2}+2E_{i-2}) + 3(3V_{i-2}+3E_{i-2}) = 18V_{i-2} + 15E_{i-2}.
Così possiamo muoverci di due in due.
Prova a pensare come muoverci di K in K, con un K molto grande.
1 Mi Piace
La soluzione ottimale funziona sulla falsa riga di fibonacci in logN con la fastexp, dove ovviamente le matrici dovranno avere valori diversi. La soluzione con N/K salti lunghi K nel caso migliore va in sqrt(N), quando K=N/K. Per gli input del problema le due soluzioni sono entrambe valide, si inizierebbe a vedere la differenza con input più grandi, direi almeno N >= 10^{12}
1 Mi Piace
Sorry, ti devo correggere. Non è vero che è meglio scegliere K = \sqrt{K}, sarebbe vero se per calcolare quanto ti sposti con un salto di K lo calcoli in O(K)
1 Mi Piace
Risolto, grazie mille 