Convoglio execution timed out


#1

Buongiorno,
ho provato a risolvere l’esercizio convoglio (https://training.olinfo.it/#/task/convoglio/statement) con un backtracking ricorsivo, ma prendo 21/100 per execution timed out.

Qualche suggerimento?


#2

Prova a sfruttare il fatto che ti viene già data una configurazione valida.


#3

Ok…
Però anche se partissi dalla configurazione data non dovrei sempre provare tutte le combinazioni finchè non ne trovo una buona?


#4

Supponi che una soluzione esista, prova a mettere in relazione la soluzione con la configurazione iniziale


#5

Confrontando le configurazioni ho pensato di scrivere un algoritmo con complessità O(N²) in cui prendo due a due tutti i nodi del grafo, e se vedo che il nodo A è collegato al nodo t[B] e il nodo B è collegato al nodo t[A] scambio t[A] e t[B] e stampo la soluzione.
Se non trovo nessuna combinazione valida stampo -1
P.S. il vettore t contiene la soluzione data dal problema, dove il nodo i è collegato a t[i]

Con questa soluzione prendo sempre 21/100, non capisco da dove partire per modificare la configurazione iniziale :sweat_smile:


#6

Supponiamo che una soluzione esista, se creo il grafo composto dagli archi della configurazione iniziale diretti da sinistra verso destra e quelli della configurazione finale da destra verso sinistra allora il grafo conterrà un ciclo.

Ecco l’esempio dal testo:


#7

Non avrei mai pensato di individuare un ciclo per risolvere questo problema… :thinking:
Comunque grazie mille, ora prendo 70/100 (c’è solo un testcase in cui prendo TLE ma ora vedo di sistemare).