Visualizzazione dei risultati da 1 a 7 su 7
  1. #1

    [Olimpiadi Informatica - Nazionali 2008]Troupe televisive

    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.p...id=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

  2. #2
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Mantieni la posizione corrente delle troupe, ad ogni evento controlli qual'è la più vicina e la sposti...
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  3. #3
    Innanzitutto grazie per la risposta. La soluzione che mi proponi dovrebbe essere greedy, ma come si comporterebbe su un input di questo tipo?
    codice:
    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

  4. #4
    Utente di HTML.it
    Registrato dal
    Feb 2011
    Messaggi
    156
    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?
    codice:
    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)

  5. #5
    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:

    codice:
    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...

  6. #6
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Uhm, hai ragione, ma l'unico algoritmo che mi viene in mente è esponenziale...
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  7. #7
    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.
    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!
    Suggerimenti?

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.