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?
treno: fase territoriale
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
@@@@@@@@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.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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 ha scritto:vero, tibor, quella credo che sia (col senno di poi) la soluzione ottimale!
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
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.