# Taglialegna nazionali 2014 **URL:** \ **Category:** Aiuto\ **Created:** [20 Giugno 2017, 6:55pm UTC](https://forum.olinfo.it/t/taglialegna-nazionali-2014/4682 "2017-06-20T18:55:03Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\ **Post date:** [20 Giugno 2017, 6:55pm UTC](https://forum.olinfo.it/t/taglialegna-nazionali-2014/4682/1 "2017-06-20T18:55:03Z")
Stavo guardando la soluzione di taglialegna e cercavo di capire come costruisse linearmente (sapendo che è O(N) ammortizzato) l’array rep (che indica qual è l’ultimo albero abbattuto dall’albero i) Input di esempio: N = 7 4 1 3 1 3 2 1 Con il mio algoritmo O(N^2) (con cui ho fatto 66 punti, causa timeout) l’array contiene questo: 6 1 6 3 6 6 6 _(nessun messaggio subliminale messo volontariamente)_ Mentre copiando quello del booklet (che semplicemente salta ogni volta da rep[i] a rep[rep[i]]) ottengo 3 1 6 3 6 6 6 Quindi avrei un risultato errato… cos’è che non capisco? ---
**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:** [27 Giugno 2017, 3:40pm UTC](https://forum.olinfo.it/t/taglialegna-nazionali-2014/4682/2 "2017-06-27T15:40:46Z")
hai provato a verificare a mano il tuo risultato? ---
**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\ **Post date:** [27 Giugno 2017, 6:47pm UTC](https://forum.olinfo.it/t/taglialegna-nazionali-2014/4682/3 "2017-06-27T18:47:29Z")
Si, ho concluso che il booklet è sbagliato perché un’altra soluzione in giro mi ha fatto fare 100/100 (prendendo soltanto la parte in cui calcola rep e lep)