# Problema Fractal graphs

**URL:** <https://forum.olinfo.it/t/problema-fractal-graphs/4920>\
**Category:** Aiuto\
**Created:** [7 Dicembre 2017, 2:33pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920 "2017-12-07T14:33:56Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![rego](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e8c25b/32.png) [@rego](https://forum.olinfo.it/u/rego)\
**Post date:** [7 Dicembre 2017, 2:33pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920/1 "2017-12-07T14:33:56Z")

</div>

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) = 3_N(i-1)+2_A(i-1)  
A(i)=3_N(i-1) + 3_A(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.

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [7 Dicembre 2017, 4:03pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920/2 "2017-12-07T16:03:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [7 Dicembre 2017, 4:36pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920/3 "2017-12-07T16:36:09Z")

</div>

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}

---

<div class="post-metadata">

**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\
**Post date:** [7 Dicembre 2017, 5:49pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920/4 "2017-12-07T17:49:58Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![rego](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/e8c25b/32.png) [@rego](https://forum.olinfo.it/u/rego)\
**Post date:** [9 Dicembre 2017, 1:18pm UTC](https://forum.olinfo.it/t/problema-fractal-graphs/4920/5 "2017-12-09T13:18:05Z")

</div>

Risolto, grazie mille 😃