treno: fase territoriale

[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?

[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]

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]

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]

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!
...e maledetti 2 punti...

[Tibor Gallai]

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]

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)

[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.