Ciao a tutti, avrei bisogno di un piccolo aiuto per quanto riguarda gondola network delle ois.
Ho provato a risolverlo usando una dfs per T volte, ma ovviamente va in tle per la maggior parte dei casi di test. Ho provato ad ottimizzare un po’ la soluzione ma l’unica cosa fattibile mi sembra ordinare i Wi dal più grande al più piccolo e procedere con una union find delle “componenti connesse” in modo da usare ciò che è stato calcolato nei Wi precedenti, non so se mi sono spiegato. In questo modo riesco ad ottenere un subtask in più, ma rimango a 45/100.
Nella UF, usare l’altezza anziché la size dovrebbe dare risultati un pelo migliori
Comunque è inefficiente il modo in cui cerchi i nodi non visitati per fare la dfs, in questo modo solo con i due for hai una complessità di O(TN) che è sufficiente per andare in TLE. Ti consiglio di sfruttare la costruzione dell’MST e di prendere spunto dall’algoritmo di Kruskal
Uhm, ho provato a costruire uno spanning tree usando come “pesi” la larghezza dei canali e come strategia greedy prendo prima l’arco con peso maggiore, in modo da far passare il maggior numero possibile di gondole. Questo è leggermente più veloce, ma risulta WA in alcuni casi e TLE negli stessi casi del vecchio algoritmo ottenendo sempre 45/100, non so proprio dove andare a parare
La logica dietro la mia implementazione con union find è: ordino le gondole in modo decrescente per larghezza, parto da quella più larga e trovo le “componenti connesse” tramite dfs, azzero l’array per le visite e prendo la gondola successiva, faccio una nuova dfs ma ora facendo partire la ricorsione solo per i figli che non appartengono alla stessa componente connessa del nodo che sto considerando, cercando di unire componenti connesse diverse. Questo dovrebbe avere complessità O(TNlogN) più o meno
Prova a far così:
Elimina completamente dalla testa la DFS. Ordina gli archi e le gondole in modo decrescente. Scegli se operare su una gondola o su un arco a seconda di quale sia più largo. In caso sia l’arco unisci i set, in caso la gondola il suo risultato è il numero di set. Poi passa al successivo
Si può contare sul fatto che le isole siano numerate da 1 a N? Non mi pare che il testo lo dica.
Inoltre c’è qualcosa nel testo che non mi è chiaro: nelle spiegazioni si parla anche di laghi da dove scappano fuori?
Explanation
In the first sample case:
• 3 gondolas of width 20 are necessary: one for the group of lakes (2, 3, 5, 6) and one for each of the lakes 1 and 4.
• A gondola of width 90 cannot sail on any canal, so a ship must be rented for every island.
• A gondola of width 3 can sail on all the canals, so one is enough.
• 4 gondolas of width 60 are necessary: one for the group of lakes (3, 5, 6) and one for each of the lakes 1, 2 and 4.
Inoltre:
Notice that if an island is not connected to other islands, Santa will still need to rent a
gondola for that island: the presents need to be dispatched through the island by boat.
Non capisco a cosa serva affittare una barca (non gondola??) per consegnare i regali attraverso l’isola: con una barca non si arriva all’isola e una volta sull’isola a che serve la barca?
Forse si voleva dire che se un LAGO, non è connesso ad altri LAGHI, (o connesso ad altri laghi con canali troppo stretti rispetto alla larghezza della gondola analizzata) allora per consegnare i regali nelle isole all’interno del lago bisognerà affittare una barca della larghezza analizzata e solo per quel lago visto che poi con quella barca non si uscirà dal lago?
Grazie
Credo proprio che ci sia un po’ di confusione, lakes e islands in realtà sono la stessa cosa:sweat_smile:
Probabilmente il problema é una rivisitazione di un altro in cui compaiono i laghi invece che le isole e l’autore del testo si é confuso.
