Problema "Giro di boe"

Per risolvere questo problema ho provato a lanciare una dfs, che si ferma dopo 2 nodi, e controlla se il nodo di partenza è presente tra i figli del nodo attuale. il problema è che va in TLE negli ultimi 2 task. Come potrei fare per renderlo più veloce?

Prova a pensare come può essere la distanza fra 3 boe adiacenti rispetto ad una boa scelta a caso. :wink:

Non ho ben capito quali sono le varie strategie usate nelle soluzioni inviate, tuttavia sospetto che alcune di quelle che hanno preso 100/100 non siano ottimali :confused: purtroppo abbiamo dovuto tenere basso il limite sul numero n di boe (altrimenti il tempo di lettura dell’input era troppo alto). Appena ho un po’ di tempo cerco di creare una versione grader-izzata del task con degli input più grandi, in modo da far passare solo le soluzioni ottimali :stuck_out_tongue_winking_eye:

Comunque, la soluzione ottimale ha complessità O(n^2). Un’indizio per trovare questa soluzione è:

Supponiamo di aver trovato un ciclo “generico”, quindi anche più lungo di 3 boe. Possiamo in qualche modo usare le assunzioni date dal testo per provare ad “accorciarlo”?

Ciao, anch’io ho lo stesso problema per gli ultimi due task.
Cosa intendi per distanza?