Sto cercando di risolvere questo problema ma la mia soluzione ha qualche problema che non riesco a trovare.
Ho risolto i problema in questo modo:
Prima trovo la distanza minima fra due piazze qualsiasi e salvo i risultati in un array bidimensionale, poi eseguo una binary search per trovare qual’è la distanza massima che si può tenere fra i due cortei.
Il codice per la binary search è questo:
// se i cortei sono già a destinazione restituisco la distanza fra le piazze dove si trovano
if (P1 == D1 && P2 == D2) return dist[P1][P2];
// lower bound per la distanza massima
low = 0;
// dist è l'array bidimensionale dove sono salvate le distanze fra le piazze
// upper bound per la distanza massima
high = min(dist[P1][P2], dist[D1][D2])+1;
while (low+1 != high) {
mid = (low+high)/2;
// la funzione test controlla se si può mantenere la distanza mid
if (test(P1, D1, P2, D2, N, mid)) {
// se si può mantenere la distanza allora il lower bound sale
low = mid;
} else {
// se non si può mantenere la distanza allora l'upper bound scende
high = mid;
}
}
return low;
Questo codice però fa solo 22/100 e sbagli molti testcase.
Il resto del programma sembra funzionare, infatti se sostituisco la binary serch con:
if (P1 == D1 && P2 == D2) return dist[P1][P2];
// controllo direttamente ogni distanza
for (int k = min(dist[P1][P2], dist[D1][D2]); k >= 0; k--) {
if (test(P1, D1, P2, D2, N, k)) return k;
}
Il programma fa 71/100 per timeout ma non sbaglia nessuna subtask.
Inoltre ho controllato che la funzione test non solo restituisca ‘true’ solo per la distanza massima ma anche per quelle inferiori (all’inizio pensavo fosse questo il problema).
Qualcuno saprebbe aiutarmi?