Eccone un altro 
4 4
3 4 1
4 2 1
2 3 3
3 1 3Adesso anche quello va bene… Sempre un altro errore banale. Se il predecessore comune fosse stato “v” stesso, l’algoritmo di prima non avrebbe funzionato.
Modificando opportunamente l’input creato da te me lo fa bene, ma ancora sono a 80 punti 
Sto perdendo le speranze ahahah http://pastebin.com/tN9v2eSh
4 5
3 1 3
2 1 3
4 2 2
3 4 1
2 3 3
Eccolo finalmente, l’input che fa crollare definitivamente l’algoritmo ahahah
E vabbè ripiegherò sull’eliminazione dell’arco.
Grazie per la pazienza 
1 Mi Piace
Domanda: ma ai fini della Selezione Territoriale, qual’è il tempo massimo di esecuzione?
In altre parole, una soluzione che enumera i cammini certamente non prende 100/100 qui nel sito. Ma quanto prende alla Territoriale?
Cosa intendi per enumerazione??
Credo si riferisca alla bruteforce, cioè trovare tutti i cammini! 
Comunque per il 40% dei punti N è abbastanza basso da stare dentro ad 1sec con la bruteforce.
Se poi consideri che hai 5 minuti e che non necessariamente le provi tutte (magari usando qualche accorgimento come fermare la DFS quando sei sicuro di andare oltre la soluzione ottima) è probabile che arrivi anche ad un 60/70%.
con una “bruteforce” ho preso 100 punti con il limite di un secondo
Ovviamente c’era qualche ottimizzazione.
Sì intendevo “bruteforce”.
Il testo dice che nel 40% dei casi il peso degli archi è 1, non che N e/o M sono piccoli.
Comunque sì, se il limite è 5 minuti allora si può prendere un punteggio buono.
Quello che non mi è chiaro è questa questione del limite alle Territoriali, che ufficialmente non esiste, ma in pratica esiste ma dei 5 minuti non l’ho visto scritto da nessuna parte.
Poi quando ho visto che qui sul sito il limite è 1 sec. mi sono preoccupato.
Comunque mi intriga parecchio il risultato di CarlaZZ, voglio cercare di migliorare la mia soluzione (qui sul sito prendo 30/100)
Uuuups ho confuso il testo con qualche altro problema! Comunque sì pure io sono curioso della soluzione di CarlaZZ! 
una volta finita la visita da un dato nodo, lo “rimuovo”, oltre a fermarmi se la soluzione parziale non è più ottima.
Ce l’ho fatta anche io, grazie al suggerimento di CarlaZZ ma anche no!
Infatti è andata un pò stranamente:
-
sono partito da un’implementazione che avevo fatto subito dopo la gara, tanto per provare, che per memorizzare gli archi usa una molto inefficente lista globale di archi (praticamente il formato di input). 30/100
-
Ho aggiunto il pruning in caso la soluzione parziale sia peggiore di quella già calcolata: 80/100
-
Ho aggiunto il pruning suggerito da CarlaZZ, fiducioso che mi desse il boost finale per arrivare a 100 ma invece è rimasto a 80/100 (anche se i tempi in molti casi si sono abbassati)
-
A questo punto mi sono reso conto che usavo una struttura dati inefficiente. L’ho sostituita con una matrice di adiacenza, sempre usando entrambe le strategie di pruning. A questo punto pensavo di arrivare a 100 ma invece: 90/100
-
C’ero rimasto un pò male, mentre cercavo di pensare qualche nuova strategia di pruning, quasi per caso ho riprovato togliendo il pruning di CarlaZZ e lasciando solo il primo e… 100/100
e anche agevolmente, l’istanza più lenta viene calcolata in circa 0.8
Non mi è chiaro come mai il secondo pruning in questo caso rallentava la ricerca, ma tant’è.
Comunque grazie mille CarlaZZ, senza il tuo post non ci avrei neppure provato a prendere 100 con una soluzione enumerativa! 
Bisogna vedere com’è implementato il pruning 
Scusate la domanda, ma che cos’è il pruning? Non ne ho mai sentito parlare, e magari può essere utile per qualcosa
Letteralmente vuol dire “potatura”, il che ha senso se si pensa all’albero di una ricorsione 
.
In parole povere il pruning è quando, in una funzione ricorsiva che cerca il modo migliore di fare una certa cosa (provando tutte le possibilità), scrivi un if del tipo:
se si verifica questa condizione, allora siamo sicuri che continuando su questo “ramo ricorsivo” non otterremo nulla di utile (ad esempio, perché notiamo che “anche essendo ottimisti” la soluzione che possiamo sperare di produrre è comunque peggiore di quella trovata fin ora), quindi usciamo subito dalla funzione senza proseguire (“tagliando” quindi il ramo ricorsivo e tornando al chiamante, che potrà proseguire per una “strada più promettente”).
Suggerisco di guardare la spiegazione ed il codice del problema cercalesomme qui: http://www.disp.uniroma2.it/users/italiano/gator/2015/booklet.pdf
Confronta anche le due soluzioni “esponenziale” ed “esponenziale_ottimizzata” per footing che trovi qui: oii/2016/territoriali/footing/sol at master · olimpiadi-informatica/oii · GitHub
In effetti forse non ho capito il pruning suggerito da CarlaZZ, nelle mie soluzioni è inefficace.
Ciò non toglie che la mia implementazione con il solo pruning “classico” ottiene 100/100
Io ho interpretato il suggerimento di CarlaZZ così: dopo aver calcolato il ciclo migliore avendo come punto di partenza V, sono sicuro che se partendo da altri nodi ho un ramo che raggiunge V, tale ramo non può produrre una soluzione migliore di quella già calcolata nella chiamata in cui V era il punto di partenza. Quindi poto il ramo. È giusto o l’idea era più complessa?
Grazie mille, ho capito
l’idea è semplicissima.
Trovo il ciclo più corto che passa per il punto p.
Nei cicli successivi non dovrà più esserci p, altrimenti ricadrei nel ciclo precedente ( essendo il più corto contenente p). L’ho implementato con un array di boolean
infatti questo avevo capito. Eppure a me taglia poco. Ci deve essere qualcosa che ho sbagliato…