PDA

Visualizza la versione completa : [Olimpiadi Informatica - Nazionali 2008]Troupe televisive


renatrino
08-10-2012, 22:13
Ciao a tutti,
da un po' di giorni sto sbattendo la testa su un problema delle fasi nazionali delle olimpiadi di informatica. Per chi non lo sapesse, in breve si tratta di una competizione aperta agli studenti delle superiori, in cui, nella fase nazionale, data la descrizione di un problema e di un certo numero di input relativi al problema, bisogna scrivere un algoritmo (il codice può essere in C, C++ o Pascal) che, nei limiti di tempo previsti per il problema, restituisca l'output corretto. Il problema in questione è stato proposto nel 2008 e si chiama "Troupe televisive" (il testo si può trovare qui http://81.208.32.83:8080/ioi/index.php?option=com_content&view=article&id=187%3Aprove-assegnate&catid=78%3Aolimpiadi-italiane&Itemid=229&lang=it ). L'unica soluzione che mi viene in mente è di complessità esponenziale (2^N), ma poichè N, nel problema specifico, può essere anche 1000, in tal modo su input anche non troppo grossi è impossibile rientrare nei 2 secondi di tempo massimo. Sostanzialmente, mi calcolo tutte le possibili combinazioni e le metto in un albero binario. Ho pensato a un'ottimizzazione basata sui gruppi di k eventi consecutivi (in tal caso i movimenti da fare per quegli eventi saranno o k 'R' o k 'C'), ma si tratta di un caso particolare, e comunque non sempre mi darebbe un grande vantaggio. Qualcuno può darmi un suggerimento su un approccio più efficiente?

Ringrazio in anticipo le anime pie che sono arrivate a leggere fino a qui ;)

Scara95
08-10-2012, 23:33
Mantieni la posizione corrente delle troupe, ad ogni evento controlli qual'è la più vicina e la sposti...

renatrino
09-10-2012, 16:14
Innanzitutto grazie per la risposta. La soluzione che mi proponi dovrebbe essere greedy, ma come si comporterebbe su un input di questo tipo?

3 3
1 3
2 3
3 3
Se ho ben capito dovrebbe restituire RRR, perchè dapprima la telecamera più vicina è R, che non si muove, poi di nuovo R (costo 1, contro il costo 2 di C), che si muove di 1 in giù e infine di nuovo R (che prima stava inquadrando la riga 2 e quindi ha costo 3-2=1, contro il costo 3-1=2 di C)... Ma la soluzione migliore dovrebbe essere CCC (costo 2+0+0=2, contro il costo 1+1+1=3 di RRR). Mi confermi che ho capito bene?

Grazie :)

Rising1
09-10-2012, 18:11
Originariamente inviato da renatrino
Innanzitutto grazie per la risposta. La soluzione che mi proponi dovrebbe essere greedy, ma come si comporterebbe su un input di questo tipo?

3 3
1 3
2 3
3 3
Se ho ben capito dovrebbe restituire RRR, perchè dapprima la telecamera più vicina è R, che non si muove, poi di nuovo R (costo 1, contro il costo 2 di C), che si muove di 1 in giù e infine di nuovo R (che prima stava inquadrando la riga 2 e quindi ha costo 3-2=1, contro il costo 3-1=2 di C)... Ma la soluzione migliore dovrebbe essere CCC (costo 2+0+0=2, contro il costo 1+1+1=3 di RRR). Mi confermi che ho capito bene?

Grazie :)

schematizziamo così la tabella (1=evento, 0=niente)

001
001
001

per inquadrare tutti gli eventi ci si può spostare di 2 a destra (costo: 2) o di due in basso (costo:2 dato che al primo istante, stando fermo, riesce già ad inquadrare un evento). Quindi le due soluzioni sono identiche (ma l'algoritmo così organizzato dirà di fare due passi in verticale ovviamente)

renatrino
09-10-2012, 18:47
Originariamente inviato da Rising1
schematizziamo così la tabella (1=evento, 0=niente)

001
001
001

per inquadrare tutti gli eventi ci si può spostare di 2 a destra (costo: 2) o di due in basso (costo:2 dato che al primo istante, stando fermo, riesce già ad inquadrare un evento). Quindi le due soluzioni sono identiche (ma l'algoritmo così organizzato dirà di fare due passi in verticale ovviamente)

Hai ragione, ho sbagliato esempio! Però proviamo ad aggiungere un altro evento subito più in basso:


4 4
1 3
2 3
3 3
3 4


La situazione dovrebbe essere questa:
001
001
001
001

Se ho capito bene l'algoritmo greedy funziona così:

Prima mossa:
- uso R perchè ha costo 0; usare C mi comporterebbe un costo di 2
Seconda mossa:
-uso R perchè ha costo 1; usare C mi comporterebbe un costo di 2
Terza mossa:
-uso R (che ora inquadra la riga 2) perchè ha costo 1 (3-2); usare C (che inquadra ancora la colonna 1) mi comporterebbe un costo di 2
Quarta mossa:
-uso R (che ora inquadra la riga 3) perchè ha costo 1 (4-3); usare C mi comporterebbe un costo di 2

Totale: RRRR ----> 0+1+1+1=3

Usando invece CCCC abbiamo 2+0+0+0=2, che è quindi una soluzione migliore...

Scara95
09-10-2012, 19:21
Uhm, hai ragione, ma l'unico algoritmo che mi viene in mente è esponenziale...

renatrino
09-10-2012, 19:42
Originariamente inviato da Scara95
Uhm, hai ragione, ma l'unico algoritmo che mi viene in mente è esponenziale...

Già, eppure ci deve essere una soluzione migliore, almeno di complessità polinomiale: compiere 2^1000 operazioni in 2 secondi è impensabile!
Avevo pensato qualcosa sui gruppi di eventi consecutivi, come nei casi che abbiamo visto: se gli n eventi consecutivi sono o in riga o in colonna, per tale gruppo la soluzione sarà sicuramente n volte R o n volte C. Ma nel caso peggiore questa ottimizzazione non ci apporta alcun vantaggio: prendiamo il caso di 1000 elementi sparsi in una matrice 1000x1000 senza che ve ne siano di consecutivi sulla stessa riga o sulla stessa colonna. Saremmo costretti a calcolarci tutti le possibili combinazioni...
E' da un bel po' che ci penso su, ma la soluzione mi sfugge. :dhò:
Eppure l'esercizio è di difficoltà 2... Nel 2008 capitò un altro problema di difficoltà 2 (per me molto più semplice) e addirittura un problema di difficoltà 3! :bhò:
Suggerimenti?

Loading