[FINE][07/04] Problema della Settimana (Trabucco)


#1

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.

Il problema di questa settimana è Trabucco.

Buon lavoro!


[FINE][31/03] Problema della Settimana (Ricehub)
appuntato #2

#3

Con l’arrivo del nuovo problema della settimana mi permetto di proporre le due soluzioni che ho trovato, anche perché ho trovato questo problema molto istruttivo.

La prima osservazione fondamentale da fare è: per arrivare dalla cella di partenza a quella di destinazione con un numero minimo di mosse è necessario muoversi solamente verso l’alto e verso destra.

Per rendere tutto più chiaro bisogna dividere la soluzione in 3 parti fondamentali:

  1. Innanzitutto bisogna calcolare per ogni cella della matrice la distanza dalla postazione di guardie più vicina ad essa. Il modo migliore per farlo è, tramite una bfs, analizzare una cella alla volta in ordine di distanza. Mettendo come celle di partenza le K postazioni di guardie ed analizzare le varie direzioni evitando di passare su una casella già incontrata, in quanto ci si era arrivati con una distanza sicuramente minore od uguale a quella attuale. Questa parte dell’algoritmo ha una complessità di O(NM) in quanto si processa in tempo costante ogni cella della matrice solamente una volta.

  2. Ora bisogna calcolare la sicurezza del percorso con sicurezza massima, per farlo si possono utilizzare due approcci:

  • Utilizzare la ricerca binaria sul valore della sicurezza: per testare ogni valore della ricerca binaria possiamo controllare se è possibile o meno attraversare la matrice senza passare da celle che hanno una sicurezza minore di quella che stiamo testando, per farlo ci si può muovere banalmente, partendo dalla partenza, o in alto o a desta, evitando di passare da celle già visitate o con una sicurezza inferiore a quella in questione. Verranno testati log_2(N+M) valori, ognuno dei quali può essere verificato in O(NM), portando la complessità dell’algoritmo a O(NM*log_2(N+M)).

  • Sfruttare la programmazione dinamica, tramite un approccio bottom up si può calcolare la sicurezza minima maggiore con la quale arrivare da ogni cella a destinazione, partendo dalle celle più vicine alla destinazione stessa: si può notare come questo valore corrisponda al minimo tra la la pericolosità della cella in questione ed il massimo tra il valore della dp per la cella sopra e quella a destra della cella in questione. Calcolando questo valore per ogni casella, basandosi sui valori delle celle vicine si può trovare la sicurezza del percorso con sicurezza massima dalla partenza alla destinazione in O(NM), mantenendo dunque la complessità dell’algoritmo a O(NM).

  1. Infine bisogna contare i percorsi, ed anche qui è necessaria la programmazione dinamica, nello specifico: il numero di modi in cui posso arrivare dalla cella x,y alla destinazione sono uguali a 0 nel caso in cui la sicurezza di tale casella sia inferiore a quella trovata precedentemente nel passo 2, altrimenti corrisponde alla somma del numero di modi in cui posso concludere il percorso partendo da x+1,y e quelli in cui lo posso concludere da x,y+1. Anche in questo caso si processa ogni casella della matrice 1 volta.La complessità sara quindi O(NM*log_2(N+M)) nel caso in cui si utilizzi la ricerca binari, O(NM) se si utilizza la programmazione dinamica.

Spero di essere stato chiaro :smile:.

Fabio.


#4

La soluzione di @frakkiobello è senz’altro corretta, tuttavia per questo problema è sorprendentemente disponibile il booklet con la soluzione ufficiale!


spuntato #5

#6

Ottimo @frakkiobello!

In ogni caso qui trovate il nuovo problema della settimana!