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.
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 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
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?