IOI'94 - Giorno 2 - Problema 2: Gli autobus

Un uomo arriva ad una fermata d'autobus alle 12:00, e vi rimane per il periodo 12:00-12:39. La fermata viene usata da un certo numero di linee di autobus. L'uomo prende nota degli istanti di arrivo degli autobus, che sono dati come input del problema.

Gli autobus di una certa linea arrivano a intervalli regolari dalle 12:00 alle 12:59.
Gli istanti di arrivo sono numeri interi fra 0 e 59.
Ogni autobus si ferma almeno due volte durante l'ora.
Il numero di linee è <=17.
Autobus di linee diverse possono arrivare nello stesso momento.
Diverse linee di autobus possono avere lo stesso istante di prima fermata e/o la stessa frequenza. Se due linee di autobus hanno lo stesso istante di prima intervata e intervallo, gli istanti di fermata vengono comunque presentati come distinti.

Si trovi il minimo numero di linee di autobus che soddisfino l'input. Per ogni linea, si dia l'istante di prima fermata e la frequenza (cioè, il tempo che intercorre fra un arrivo e il successivo).

Dati di input

Il file di input, INPUT.TXT, contiene un numero n (n<=300) che indica quanti arrivi di autobus sono stati registrati, seguito dai tempi di arrivo in ordine crescente. Nel nostro esempio:

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

Dati di output

I risultati vanno scritti sul file OUTPUT.TXT con una riga per ciascuna linea di autobus. Ogni linea contiene l'istante del primo arrivo e la frequenza, in minuti. L'ordine in cui compaiono le linee non è importante; se ci sono più soluzioni, se ne deve comunque produrre una sola. Nel nostro esempio:

0 13
3 12
5 8

Terminologia

Useremo la seguente terminologia per discutere del problema:

chiamiamo passaggio la registrazione del passaggio di un autobus: l'input è quindi una sequenza (eventualmente con ripetizioni) di passaggi;
chiamiamo schedule la coppia (s,p) dove s è il minuto del primo passaggio di un autobus, e p è la frequenza (numero minuti che intercorrono fra un passaggio e il successivo); i passaggi di uno schedule sono gli istanti a cui si vede passare un autobus con quello schedule (s,s+p,s+2p,... fino a 60 escluso); il numero di passaggi di uno schedule è il numero di tali passaggi;
una soluzione parziale relativamente a una certa sequenza di passaggi è una sequenza di schedule tali che i passaggi del primo schedule siano compresi nella sequenza, i passaggi del secondo schedule siano compresi nella sequenza ottenuta eliminando quelli del primo schedule ecc. Chiamiamo (numero di) passaggi rimanenti i(l numero dei) passaggi della sequenza iniziale che rimangono ancora nella sequenza dopo i passaggi relativi a tutti gli schedules della soluzione parziale considerata. Se il numero di passaggi rimanenti è 0, la soluzione si dice completa.

Notate che s<p (la frequenza non può essere minore o uguale dell'istante del primo passaggio), e inoltre s+p<60 (ogni autobus passa almeno due volte). Da questo segue che 2s<60, cioè 0<=s<=29. Inoltre s+1<=p<=59-s (cioè 59-2s possibili valori di p). Ne segue che gli schedules possibili sono solo 59+57+55+...+1, che
significa SOMMA(i=0,...,29) (2i+1), cioè 30+2*SOMMA(i=0,...,29) i=30+2*29*30/2=30+870=900.

Algoritmo

L'algoritmo inizia con una fase in cui vengono precomputati (e posti in un array) i soli schedule ammissibili rispetto alla sequenza di passaggi di input.
A questo punto inizia la ricerca basata su un branch-and-bound. Si parte dalla soluzione parziale vuota e si tenta di estenderla aggiungendo ogni volta schedule ammissibili rispetto ai passaggi rimanenti dopo la soluzione parziale corrente: i passaggi rimanenti sono conservati nell'array rec che viene ogni volta aggiornato quando si aggiunge/toglie uno schedule alla soluzione. Per evitare di considerare due volte la stessa soluzione parziale, la sequenza degli schedule della soluzione parziale è non decrescente (rispetto all'ordine degli indici degli schedule nell'array degli schedule ammissibili).

Si possono verificare i seguenti casi:

si arriva a una soluzione completa: in questo caso, se la soluzione è migliore di quella corrente, si modifica l'ottimo corrente;
si arriva a una soluzione non estendibile: backtracking.

Notate inoltre che è inutile procedere se la lunghezza della soluzione parziale+1 non è minore dell'ottimo corrente.
Per ridurre ulteriormente i casi da considerare, supponete che l'array degli schedule ammissibili sia ordinato in ordine decrescente di numero di passaggi. Supponiamo ora di avere una certa soluzione parziale s1,...,sk e che il numero di passaggi di sk sia p. Supponiamo inoltre che i passaggi rimanenti siano r e che l'ottimo corrente sia costituito da n schedules. Perché la soluzione parziale possa diventare ottima occorre che la si possa estendere con meno di n-k schedules, ciascuno dei quali avrà non più di p passaggi: quindi dovrà essere t*p>=r per qualche r<n-k. E dunque (n-k)*p>r. Se non è così, è inutile provare ad estendere la soluzione...