Ho letto il testo dell’esercizio e la mia idea era quello di usare Dijkstra partendo da tutte le aule delle commissioni e poi calcolare per ogni nodo del grafo il suo valore di insoddisfazione.
Questa soluzione però sono parecchio sicuro che vada fuori tempo perchè possono esserci fino a 30000.
Il mio dubbio è fondato? Qualcuno mi può dare un suggerimento?
Grazie
In effetti usando questo metodo il penultimo testcase va fuori tempo (si ottengono comunque 96 punti). Sono ancora alla ricerca di un’ottimizzazione…
Questa soluzione funziona, visto che K <= 10. La complessità è O(K*(N+M)*logM), più che sufficiente per risolvere il problema. I 96 punti probabilmente li ottieni per un overflow nel calcolo della distanza minima - prova ad usare i long long al posto degli int.
Dario
1 Mi Piace
La tua soluzione dovrebbe funzionare come tempo dato che le commissioni sono poche. Come ha detto dp_1, attento agli overflow!
Non credo il problema sia quello, con la prima soluzione ottenevo 92 punti e un output non corretto nell’ultimo testcase, che ho poi risolto rendendo long long il vettore delle distanze
Ciao, quella soluzione si trova al limite massimo di tempo, impiega in media 1.7 quando il limite é 1.5 questo significa che puoi ottenere 100, cerca di ottimizzare il dettaglio e prova a ricaricare piú volte la soluzione, dipendendo molto anche dalla velocità del server dopo una decina di sottoposizioni dovresti avere il caso fortunato e metterci meno di 1.5 e quindi ottenere 100. Se noti infatti le persone che hanno privato il problema sono relativamente poche, ma il numero di sottoposizioni è enorme
Sí il tuo dubbio é fondato, Dijkstra e basta non é la soluzione ottimale, ma se la implementi molto bene e in modo ottimale puoi ottenere comunque 100 come ho scritto sopra
In effetti dopo aver sottomesso la stessa soluzione un po’ di volte sono riuscito a ottenere 100 punti, grazie dell’aiuto.
Ciao, sono colui che ha scritto i testcase, e ne ho generato uno dove ci sono 30K nodi tutti in fila, con tutti gli archi con peso massimo. Quindi sì, usando gli int ci sarà overflow, ma non serve scomodare tipi lungi come i long long poichè 30000*100000=3000000000, che fitta -si dice, fitta?- in un intero unsigned.
1 Mi Piace
Salve, colui che ha scritto i testcase.
Hai ragione, purtroppo dimentico sempre i poveri unsigned ¯\_(ツ)_/¯
Sta di fatto che questa è comunque la sola distanza, se volessi includere anche il moltiplicatore della pigrizia dentro a dijkstra manderei in overflow anche l’unsigned int
1 Mi Piace
Ah, perfetto, ma dopo l’esperienza del problema Dijkstra mettere i long long è diventato praticamente automatico 
Comunque non c’erano particolari problemi di memoria, quindi amen
Ciao, sono colui che ha messo insieme i testcase con il generatore fatto da lukecavabarrett, e vorrei avvisare che in un subtask le assunzioni non vengono rispettate 
(M è molto più alto di quanto dovrebbe).
È comunque possibile fare 100, e sarà corretto in un paio di giorni.
colui che ha progettato il generatore dei testcase è indinniato.
2 Mi Piace
Ah perfetto, grazie mille
Colui che ha veramente fatto i testcase dice che lukecavabarrett é un vile mentitore.
2 Mi Piace
ma hai sbagliato te a generarli, oppure c’era un qualche bug nel mio generatore?
Ho sbagliato io… 
1 Mi Piace
Nel secondo caso di esempio, ci sono 3 nodi ottimali con distanza 8, dei quali uno è sede di una
commissione.
Vero, però mi sembra che il grafo mostrato subito sotto differisca abbastanza da quello descritto in forma tabellare nell’input di esempio.
Inoltre i nodi “buoni” dovrebbero essere quelli numerati con 1,2,3.
Sbaglio?
Il Grafo dovrebbe essere questo.
Confermo che i nodi che generano un’insoddisfazione minima sono i nodi: 1,2,3
2 Mi Piace
Si anche per me il grafo è quello che proponi tu.
Sarebbe il caso di aggiustare il grafo presente nel testo del task.