treno: fase territoriale

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
dovix91
Messaggi: 43
Iscritto il: 24 feb 2007, 21:09
Località: alessandria

treno: fase territoriale

Messaggio da dovix91 »

quali idee avete utilizzato (o usereste) per risolvere il problema treno della Fase Territoriale di quest'anno alle olimpiadi di informatica?
Lo si trova qui:
http://81.208.32.83:8080/oii/2009/selez ... /treno.pdf

la soluzione che avevo dato in gara era una pura ricerca esaustiva, ma ci mette millenni (e per di più calcola la migliore e non una qualsiasi serie di spostamenti, il che avrebbe fatto risparmiare un bel po' di tempo d'esecuzione, ma avevo letto male il testo)...

esiste una soluzione "matematica" figa? 8)
carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop »

Non mi è venuto in mente nulla di "figo"...

Come notavi tu, il problema non chiede un insieme di spostamenti minimale, solo uno qualsiasi con al più 3N spostamenti.

Hint: prova a risolvere il problema con il vincolo aggiuntivo di usare esattamente 3N spostamenti
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Ecco l'idea: induzione.

esempio per N=7:

@@@@@@@OOOOOOO__
@@@@@@__OOOOOO@O
@@@@@@OOOOOO__@O
.
.
. . . risolvo per N=6 . . .
.
.
@O@O@O@O@O@O__@O
@O@O@O@O@O@O@O__

In totale aggiungo 3 spostamenti ogni volta che incremento N. Inoltre, per N=3 so farlo con 4 mosse. Quindi le mosse totali sono 3N-5.
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

In verità si può risolvere anche in 2N-1 mosse, ecco come per N=8 (spero sia chiaro il pattern):

@@@@@@@@OOOOOOOO__
@@@@@@@__OOOOOOO@O
@@@@@@@OOOOOOO__@O
@@@@@@__OOOOOO@O@O
@@@@@@OOOOOO__@O@O
@@@@@__OOOOO@O@O@O
@@@@@OOOOO__@O@O@O
@@@@__OOOO@O@O@O@O
@@@@OOOO__@O@O@O@O
@@@__OOO@O@O@O@O@O
@@@OOO__@O@O@O@O@O
@__OOO@@@O@O@O@O@O
@O@OO__@@O@O@O@O@O
@O@__OO@@O@O@O@O@O
@O@O@O__@O@O@O@O@O
@O@O@O@O@O@O@O@O__

In pratica mi riduco sempre a N=3 come facevo prima, ma alla fine risolvo tutto in un passaggio solo anziché in N-3.
dovix91
Messaggi: 43
Iscritto il: 24 feb 2007, 21:09
Località: alessandria

Messaggio da dovix91 »

vero, tibor, quella credo che sia (col senno di poi) la soluzione ottimale!
ne approfitto per fare i complimenti ai 56 punti di giove e a tutti quelli che sono passati alla selezione per le IOI! :wink:
...e maledetti 2 punti... :evil:
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

dovix91 ha scritto:vero, tibor, quella credo che sia (col senno di poi) la soluzione ottimale!
Non ho trovato la soluzione ottimale, perché per N=4 si può fare con 5<7 mosse, e per N=5 si può fare con 6<9 mosse (sono le soluzioni fornite dal testo!). La congettura è che quella costante 2 si possa abbassare a 1, ma non so come (in tempo polinomiale, s'intende...).
dovix91
Messaggi: 43
Iscritto il: 24 feb 2007, 21:09
Località: alessandria

Messaggio da dovix91 »

si scusa mi sono espresso male, intendevo che è la soluzione computazionalmente ottimale (non credo che altre migliorie possano velocizzare di molto questo algoritmo, che dovrebbe avere complessità lineare) :wink:
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Mostrare che la complessità dev'essere almeno lineare è facile (anzi, fatelo!), il problema è ottimizzare la costante, che non sembra un compito banale.

Inoltre, distinguiamo tra dimensione minima dell'output e complessità computazionale del suo calcolo, che sono due cose a priori ben distinte. Per esempio, la soluzione qua sopra opera in tempo lineare e produce un output lungo ~2N. Ora, se anche fosse vera l'esistenza di una sequenza di output "ottimale" lunga ~N, non è detto che sia calcolabile in tempo polinomiale, e tantomeno lineare.
Rispondi