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?