Think About It: Luna Park

È ora disponibile Luna park il settimo episodio della rubrica TAI.

Nell’attesa del prossimo esercizio e quindi l’editoria di questo vi invito a divertirvi cercando di risolverlo.
Dopo 2 esercizi più complessi abbiamo deciso di proporre un problema meno impegnativo.

Buon divertimento!!

5 Mi Piace

Editorial Luna Park

Il prossimo esercizio \texttt{TAI} arriverà in leggero ritardo a causa della sessione d’esami che ha praticamente occupato tutto il tempo sia a me sia a @zJack1342 , nonostante ciò ritengo sia opportuno mostrare l’editorial di Luna Park.

Idea Generale

L’esercizio chiede sostanzialmente: partendo da un grafo bidirezionale pesato formare K alberi in modo che la somma degli archi che li compongono sia massima possibile.
Partiamo analizzando il problema nel caso in cui K sia uguale a 1, in quest’istanza viene quindi chiesto di formare un unico albero con N nodi in modo che la somma degli archi sia massima. Questo problema è noto come \texttt{Maximum Spanning Tree}, che non è altro che una leggerissima modifica del più noto problema \texttt{Minimum Spanning Tree [MST] } del quale è presente anche un esercizio relativo sulla piattaforma: mst .

Per risolvere il problema del Minimum/Maximum Spanning Tree esistono principalmente 2 algoritmi: Prim’s Algorithm e Kruskal’s Algorithm. Entrambi utilizzando un approccio greedy; In certe istanze è più efficiente usare l’algoritmo di Prim (Quando il grafo è completo) in altre, come in questa l’algoritmo di Kruskal garantisce prestazioni migliori.

L’idea base dietro all’algoritmo di Kruskal è: ordinare gli archi in ordine decrescente (ricordo che cerchiamo il Maximum Spanning Tree) e partendo da quello con lunghezza maggiore, finendo con quello minore, prendere l’arco in questione solo se non forma un ciclo con gli archi già scelti precedentemente.

Analizziamo la complessità dell’algoritmo di Kruskal:

Ipotizzando di avere N nodi e M archi nel grafo iniziale.

  1. Ordinamento: bisogna ordinare una lista di M archi, si ha complessità O(MlogM) che equivale a O(MlogN) considerato che M vale al più N^2 e quindi log(M)=log(N^2)=2log(N) .
  2. Per aggiungere gli archi senza formare cicli serve utilizzare una disjoint-set data structure che ci permette di agigungere/scartare ogni arco in O( \alpha (N)) dove \alpha(x) corrisponde all’inversa della funzione di Ackermann, per ottenere quindi O(M \alpha(N)).
    Piccola nota: per ottenere complessità O(M\alpha(N)) è necessario usare Union-By-Rank e Path-Compression.

Adattare Kruskal per Luna Park

Abbiamo visto come l’algoritmo di Kruskal permetta di trovare la somma massima degli archi che formano un solo albero, adattarlo a trovare la somma massima degli archi di K alberi è molto semplice.
Notiamo come ogni volta che l’algoritmo aggiunge un arco allo Spanning Tree diminuisce il numeri di componenti di 1, partendo da N componenti per arrivare, dopo aver aggiunto N-1 archi, ad 1 solo componente. Notiamo anche come gli archi aggiunti siano in ordine decrescente di peso.
Per adattare l’algoritmo basta quindi fermarsi quando si hanno K alberi rimasti.

Velocizzare l’algoritmo

Utilizzare la versione dell’algoritmo di Kruskal che ho appena descritto non permette però di ottenere punteggio pieno ( se ottimizzate veramente bene ottiene comunque 100/100 ). Per velocizzare la soluzione è fondamentale notare le assunzioni del problema che specificano: 1 \le W_i \le 1000.
Il fatto che gli archi abbiano lunghezze inferiori od uguali a mille ci permette di velocizzare la parte di ordinamento, per farlo è sufficiente utilizzare l’algoritmo di ordinamento: Counting Sort.
In questo modo per ordinare gli archi avremo complessità O(M) invece di O(MlogM) ed essendo il numero di archi elevato questa miglioria consente di velocizzare a sufficienza per ottenere punteggio pieno.

Statistiche

Luna Park è attualmente l’unico esercizio, insieme ad hasta a valere 1000 punti nonostante il fatto che l’abbiano risolto 20 persone sulle 23 che l’hanno provato e che delle 532 soluzioni inviate ben 202 siano corrette.

5 Mi Piace