Testi e soluzioni delle OII 2014


#1

Come vi avevo promesso posto il link ad una bozza delle soluzioni dei problemi delle OII 2014, in attesa della versione finale.


Trovate tutto qui :slight_smile:

Ci farebbe piacere avere vostri commenti e suggerimenti.

EDIT: Ho caricato la versione finale del documento.

#2

Nel problema bottleneck, perchè iterate sugli archi e non sui vertici?


#3

Uhm… in che senso? L’obiettivo è cercare, tra gli archi che appartengono ad almeno uno dei percorsi buoni (buono = di lunghezza minima in termini di archi), quello di peso minimo. Dato che i vertici non hanno un “peso” non puoi fare molto quando li stai iterando… ma forse non ho capito cosa intendi.


#4

Giusto, io in gara per iterare sui nodi mi salvavo anche il costo dell’arco con peso minimo nel cammino da L e da W del nodo che stavo considerando :wink:


#5

Probabilmente dico una cavolata, ma la soluzione di Taglialegna non è esponenziale? Per renderla dinamica, non si dovrebbero salvare le soluzioni parziali da qualche parte, per poi andarle a ripescare nelle chiamate successive?


#6
Probabilmente dico una cavolata, ma la soluzione di Taglialegna non è esponenziale? Per renderla dinamica, non si dovrebbero salvare le soluzioni parziali da qualche parte, per poi andarle a ripescare nelle chiamate successive?

cip999

“Volendo privilegiare la trasparenza nella spiegazione, abbiamo volutamente ignorato la parte di memoizzazione (memoization), che non può invece essere trascurata inuna implementazione reale.”

Pag19


#7

Ops, mi era sfuggito… :S Grazie :slight_smile: