# Dubbio problemi Scale di Hogwarts e Classifica senza fili **URL:** \ **Category:** Chiarimenti\ **Created:** [30 Maggio 2017, 6:02pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654 "2017-05-30T18:02:15Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![Tredici](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tredici/32/2637_2.png) [@Tredici](https://forum.olinfo.it/u/Tredici)\ **Post date:** [30 Maggio 2017, 6:02pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/1 "2017-05-30T18:02:15Z")
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ù.)? ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [30 Maggio 2017, 6:31pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/2 "2017-05-30T18:31:06Z")
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 ---
**Author:** ![Tredici](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tredici/32/2637_2.png) [@Tredici](https://forum.olinfo.it/u/Tredici)\ **Post date:** [30 Maggio 2017, 9:08pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/3 "2017-05-30T21:08:37Z")
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). ---
**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\ **Post date:** [31 Maggio 2017, 3:20pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/4 "2017-05-31T15:20:31Z")
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) ---
**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\ **Post date:** [31 Maggio 2017, 9:15pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/5 "2017-05-31T21:15:24Z")
> [@lukecavabarrett](#): > > non esiste una soluzione più rapida, ne esiste una in O(|E|+Tmax)O(|E|+Tmax)O(|E|+T\_{max}), e dato che 0≤Ti≤2⋅1090≤Ti≤2⋅1090\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} . ---
**Author:** ![Tredici](https://forum.olinfo.it/user_avatar/forum.olinfo.it/tredici/32/2637_2.png) [@Tredici](https://forum.olinfo.it/u/Tredici)\ **Post date:** [1 Giugno 2017, 9:46am UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/6 "2017-06-01T09:46:52Z")
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? ---
**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\ **Post date:** [1 Giugno 2017, 5:07pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/7 "2017-06-01T17:07:54Z")
Esatto, archi = edges ---
**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\ **Post date:** [1 Giugno 2017, 5:21pm UTC](https://forum.olinfo.it/t/dubbio-problemi-scale-di-hogwarts-e-classifica-senza-fili/4654/8 "2017-06-01T17:21:49Z")
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. 🙇‍♂️