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?
Prova a sfruttare il fatto che ti viene già data una configurazione valida.
6 Mi Piace
Ok…
Però anche se partissi dalla configurazione data non dovrei sempre provare tutte le combinazioni finchè non ne trovo una buona?
Supponi che una soluzione esista, prova a mettere in relazione la soluzione con la configurazione iniziale
6 Mi Piace
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 
1 Mi Piace
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:
5 Mi Piace
Non avrei mai pensato di individuare un ciclo per risolvere questo problema… 
Comunque grazie mille, ora prendo 70/100 (c’è solo un testcase in cui prendo TLE ma ora vedo di sistemare).