Ciao a tutti!
In vista della finale internazionale delle olimpiadi a squadre abbiamo deciso, come forma di allenamento, di proporre ogni settimana un problema da risolvere.
Come funziona il “Problema della settimana”?
Ogni domenica verrà scelto un problema da risolvere dal portale di allenamento. Per risolvere il problema avrete a disposizione una settimana di tempo, durante la quale vi chiediamo di non discutere della soluzione. Una volta terminata la settimana di tempo che avete a disposizione, se non sarete riusciti a risolvere il problema potrete chiedere aiuto qui sul forum; dopo qualche giorno verrà anche pubblicata la soluzione.
La prima osservazione da compiere per risolvere il problema è quella di accorgersi che esiste sempre una soluzione ottima che trasporta i raccolti da un insieme consecutivo di risaie. Supponiamo di voler trasportare il raccolto dalle risaie A, A+1, …, A+K-1, A+K+1, …, A+L ad un magazzino posto al chilometro M, ovvero si considerano tutte e sole le risaie che hanno numero compreso tra A e A+L, escludendo la risaia A+K. Supponiamo, inoltre, che il magazzino sia stato costruito più a destra della risaia A+K (ovvero X_{A+K} \le M). È facile notare come sia possibile migliorare questa soluzione considerando la risaia A+K al posto della risaia A: così facendo il numero di risaie non cambia ma il costo per pagare i camion diminuisce, essendo la risaia A+K più vicina al deposito rispetto alla risaia A. Questa stessa osservazione vale anche nel caso in cui il deposito sia posto a sinistra della risaia A+K, con l’unica differenza che in questo caso si rimuove la risaia A+L invece di rimuovere la risaia A. Si può concludere, quindi, che non serve considerare soluzioni in cui non vengono considerate tutte le risaie comprese fra la prima e l’ultima risaia.
Seconda osservazione
Supponiamo di considerare l’insieme insieme di risaie consecutive A, A+1, ..., A+L, ovvero tutte le risaie comprese fra la risaia A e la risaia A+L. Grazie alla prima osservazione sappiamo che esiste sicuramente una soluzione ottima di questo tipo. Volendo minimizzare i costi per il trasporto, si dimostra che la scelta migliore è sempre quella di costruire il deposito in corrispondenza della risaia “mediana” fra le risaie A e A+L (nel caso in cui le risaie siano in numero pari è facile convincersi che sia indifferente costruire il magazzino in qualunque posizione compresa fra le due “mediane”). Intuitivamente, infatti, se si considera di posizionare il deposito, ad esempio, in una posizione più a sinistra rispetto alla mediana si avrà un numero maggiore di risaie a destra rispetto a quelle che si trovano alla sua sinistra; conviene, quindi, spostare il magazzino verso destra, dato che la diminuzione di costo dovuta all’avvicinamento del magazzino alle risaie a destra è maggiore rispetto all’aumento di costo dovuto all’allontanamento del magazzino dalle risaie di sinistra. Analogo il caso in cui il magazzino viene posto più a destra della mediana.
Implementazione
Grazie alle due osservazioni effettuate, si può risolvere il problema in tempo lineare usando una sliding window. In particolare, si riesce a calcolare il costo di una certa sottosequenza di risaie contigue in tempo costante precomputandosi l’array delle somme prefisse delle distanze delle risaie dall’inizio della superstrada.
