qualcuno puo darmi qualche indizio per questo esercizio?
https://training.olinfo.it/#/task/preoii_catene/statement
Il problema è piuttosto difficile( almeno per me), comunque sono riuscito( dopo molti tentativi e tempo) a prendere 45 punti. Come da tag, è un problema di programmazione dinamica: devi quindi cercare di implementare una funzione ricorsiva che possa essere memoizzata. Prova a ragionare sulle scelte che si possono fare da un nodo( da cosa dipendono?) e su un modo per effettuare in modo implicito il teletrasporto. Non provare ad applicare algoritmi noti sui grafi: per quanto il problema possa sembrare simile a un APSP( percorso minimo per tutte le coppie) le differenze sono tali da impedirne l’utilizzo( anche per i subtask più facili).
Provo a darti qualche indizio.
Indizio 1:
Dato che ci sono N nodi e N-1 archi il grafo è un albero.
Indizio 2:
Per un nodo può passare al più una catena. In particolare se un nodo fa parte di una catena, ci sono quattro casi possibili:
- La catena inizia da quel nodo.
- La catena termina su quel nodo.
- La catena passa per due figli del nodo.
- La catena passa per il padre e un figlio del nodo.
Indizio 3:
Con le osservazioni precedenti è possibile utilizzare la programmazione dinamica provando a “simulare” i quattro casi, cercando di massimizzare il valore della catena.
Tuttavia l’implementazione naive porta a una complessità O(N^2), a causa del terzo caso in cui si prova a creare una catena unendo ogni coppia di figli del nodo.
Indizio 4:
Per ottenere una soluzione O(N) è necessaria notare che è sufficiente provare a unire solo le due catene con il valore più grande.
Spero di essere stato chiaro
Grazie ho fatto 100/100. Ma non riesco a capire dove sta la programmazione dinamica in questo problema… mi sembra di aver fatto una normale funzione ricorsiva… ogni nodo lo visito una volta e basta
I tag possono anche riferirsi a soluzioni parziali, in questo caso quella O(N^2) in cui è necessario memoizzare
Be’ in realtà è comunque programmazione dinamica. La programmazione dinamica consiste nello “scomporre” il problema in sottoproblemi, trovare le soluzioni per i sottoproblemi (salvandole in una qualsiasi struttura dati) per poi unire le soluzioni riconducendosi al problema iniziale, trovando la soluzione al problema stesso. Questo ti consente di escludere soluzioni non ottimali rendendo polinomiale la complessità dell’algoritmo.
(Spiegata un po’ a cavolo ma spero renda l’idea 
)
5 Mi Piace