Salve a tutti,
stavo dando un’occhiata (e provando a risolvere) i problemi delle OII 2016 “Scale di Hogwarts” e “Classifica senza fili” quando ho notato che per entrambi i problemi il limite di tempo massimo indicati nei file .pdf differiscono dal limite di tempo indicato dal correttore. Nello specifico:
Scale di Hogwarts:
limite cms 3 sec limite .pdf 1 sec
Classifica senza fili:
limite cms 2 sec limite .pdf 0.8 sec
Qualcuno saprebbe dirmi quale dei due limiti è quello corretto (anche perché la mia soluzione di “Scale di Hogwarts” impiega circa 1.4 secondi nell’ultimo testcase e vorrei capire se è effettivamente “sufficiente” oppure mi devo impegnare di più.)?
La differenza nei limiti di tempo è dovuta alle differenze tra i server che usavamo in gara e il server del cms, meno potente. Il limite da usare è quello del cms.
btw, anche la mia soluzione fa 1.4s sull’ultimo testcase. Se vai a leggere il booklet esiste una soluzione più rapida, ma dijkstra era sufficiente a fare 100/100
Dario
2 Mi Piace
Capito, grazie mille per la spiegazione.
P.S.: Non ho usato Dijkstra perché non ho ben capito come funzioni (anche se effettivamente non ho mai voluto applicarmi per capirlo) ma ho tirato fuori un vecchio algoritmo che mi ero inventato tempo fa per cercare il cammino minimo tra due punti e l’ho adattato alla situazione (in un modo veramente indecente se devo essere sincero).
non esiste una soluzione più rapida, ne esiste una in O(|E|+T_{max}), e dato che 0\leq T_i \leq2\cdot10^9, non mi pare più ragionevole di Dijkstra in O(NlogN)
Nel testo non dice che T_i ≤ 2 ⋅ 10^6 ? 
Comunque Dijkstra nella sua implementazione più standard dovrebbe essere O(ElogV + V), quindi O(E + T_{max}) dovrebbe essere ottimale (siccome T_{max} = 2⋅E possiamo considerarla asintoticamente uguale a O(E)).
Considerando i limiti del problema la stessa cosa dovrebbe valere anche se facciamo riferimento all’implementazione O(E + VlogV) di Dijkstra, dato che VlogV > T_{max} .
1 Mi Piace
Perdonate la mia ignoranza in fatto di notazioni ma potreste dirmi cosa rappresentano “E” e “V”? Il numero di archi e di vertici del grafo?
Esatto, archi = edges
Dijkstra in O(|E|+|V|\log|V|) è una faccenda controversa. Teoricamente parlando è possibile poiché utilizza i Fibonacci Heap, che hanno insertion in O(1) e estrazione in O(\log N). Di fatto, hanno fattori costanti proibitivi, quindi nella vita pratica è sempre più vantaggioso usare un Binary Heap e quindi un Dijkstra in O(N\log N) con N = |V|+|E|.
Riguardo ai limiti di T_{max} ricordavo 2\cdot 10^9, ma potrei sbagliarmi. Appena ho tempo ricontrollo.
EDIT
Hai ragione, ricordavo male. Chiedo perdono in ginocchio. 