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