IOI '95 - Giorno 2 - Problema 3: Fili e Interruttori

Questo problema è un problema olimpico (IOI 1995) che oggi sarebbe considerato di difficoltà medio-bassa, ed è uno degli esempi di problemi in cui la soluzione ottimale si trova con strategia divide-et-impera. Nel resto di questo documento, spiegherò tre diverse possibili soluzioni, ma solo la terza funziona su tutti gli input.

Soluzione 1: Strategia lineare

La prima strategia, la più banale, per risolvere il problema è la seguente. Si considerano tutte le coppie filo/interruttore; per ogni coppia, si prova a chiudere l'interruttore, si testa il filo, e quindi si riapre l'interruttore.

Il caso peggiore, in questa strategia, si ha quando, per ogni filo l'interruttore corretto viene provato per ultimo. In questo caso, dovremo per forza testare tutte le m² coppie, e per ognuna sono richieste 3 operazioni; inoltre, alla fine, ci sarà l'operazione D.

Quindi, nel caso peggiore, questa strategia richiede 3m²+1 operazioni; quindi funziona correttamente solo se 3m²+1 <= 900, cioè, m<=17.

Soluzione 2: Strategia lineare ottimizzata

La seconda strategia è la seguente. Si chiude l'interruttore 1, e si provano tutti i fili. Quelli che fanno accendere la lampadina sono collegati all'interruttore 1, e da questo momento in avanti non li considereremo più. Quindi si chiude l'interruttore 2, e si provano i fili rimanenti. Quelli che fanno accendere la lampadina sono collegati evidentemente all'interruttore 2, e d'ora in avanti non considereremo più nemmeno loro. Si procede così fino a quando non rimangono fili da classificare.

Il caso peggiore, per questa strategia, si ha quando tutti i fili sono collegati all'ultimo interruttore. In questo caso, tutti i fili rimarranno in gioco fino all'ultimo minuto. In pratica, le operazioni da fare in questo caso saranno:

1. m-1 operazioni per chiudere, uno per uno, i primi m-1 interruttori (notate che è inutile provare con l'ultimo interruttore, perché, se i fili non sono collegati a nessuno degli interruttori precedenti, devono per forza essere collegati con l'ultimo)
2. ogni volta che si chiude un interruttore, bisogna fare m test
3. alla fine bisogna dare il comando D.

In tutto sono quindi m-1+m(m-1)+1=m² operazioni. Quindi, questa strategia funziona correttamente solo per m²<=900, cioè per m<=30.

Soluzione 3: Strategia dicotomica

La strategia che alla fine risulterà vincente è una variante della classica ricerca dicotomica: quando volete cercare un elemento in un array ordinato iniziate a confrontarlo con l'elemento mediano per scoprire se l'elemento si trovi nella prima o nella seconda metà, e proseguite così dividendo ogni volta per due lo spazio di ricerca.

In questo caso, la tecnica è analoga: prima di tutto tentiamo capire in quale metà capita l'interruttore a cui è collegato ciascun filo e poi operiamo ricorsivamente sulle due metà.

Più precisamente, il cuore del programma è costituito da una funzione decidi che prende come parametri:

• un insieme di fili (contenuti in filo[0], filo[1], ... filo[nfili-1])
• due interi x e y, con x <= y e con la garanzia che i fili passati siano sicuramente collegati a qualche interruttore nell'intervallo x, x+1, ..., y.

Lo scopo della funzione è quello di stabilire a quale interruttore sia collegato ciascuno dei fili passati come argomento, mettendo per esempio in un array globale il numero dell'interruttore, una volta scopertolo.

Naturalmente, il programma principale chiamerà questa funzione passandole l'insieme di tutti i fili, x=1 e y=m.

La funzione opera come segue:

• se nfili=0, vuol dire che non le sono stati passati fili e quindi la funzione termina senza fare nulla;
• se x=y, tutti i fili passati come argomento sono necessariamente collegati all'interruttore x, e la funzione termina dopo aver riempito gli elementi opportuni dell'array globale;
• in caso contrario, considera il valore mezzo=(x+y)/2, e poi:
  1. fa in modo che solo gli interruttori della prima metà, cioè quelli di indici da x fino a m siano chiusi;
  2. prova uno per uno tutti gli interruttori dell'insieme, e li divide in due gruppi: quelli che provocano l'accensione della lampadina, e che quindi sono collegati a qualche interruttore della prima metà (x, x+1, ..., m), e quelli che invece non hanno fatto accendere la lampadina, e quindi sono collegati a qualche interruttore della seconda metà (m+1, m+2, ..., y).
  A questo punto, la funzione chiama ricorsivamente se stessa sulle due metà.

Ora, il modo in cui si implementa questa soluzione dipende in modo essenziale da come si implementa il punto 1. di cui sopra. Ci sono almeno due modi possibili per implementarlo:

• Sottostrategia A: si considerano uno a uno tutti gli interruttori e si premono quelli che devono cambiare stato; più precisamente, tutti gli interruttori eventualmente chiusi che non stiano nell'intervallo x, x+1, ..., m, e tutti gli interruttori eventualmente aperti nell'intervallo x, x+1, ..., m.
• Sottostrategia B: si può notare che la funzione sa già che i fili in esame sono collegati sicuramente a interruttori nell'intervallo x, ..., y; quindi, gli interruttori minori di x e quelli maggiori di y sono ininfluenti ai fini dei test. Notando questo, si può operare come nella sottostrategia A, ma non toccando gli interruttori di indici minori di x o maggiori di y.

Un'analisi del numero di operazioni richieste con la strategia dicotomica (qualunque delle sottostrategie si scelga) è piuttosto complessa, ma possiamo limitarci ad un'esame sperimentale. Occorre notare che il caso peggiore, nella strategia dicotomica, si presenta quando tutti i fili sono collegati a interruttori diversi, perché in questo caso nessuno dei rami di ricorsione si interrompe "prematuramente".

Provando a eseguire un programma che implementi la strategia dicotomica usando le sottostrategie A e B, nei casi peggiori otteniamo il seguente numero di comandi (per m=80, 81, ..., 90):

Dunque, mentre la sottostrategia A ce la fa sempre con meno di 900 operazioni, la sottostrategia B fallisce quando m>88. Per inciso, la sottostrategia B, con 91 fili, richiede 903 operazioni.

Riassumendo...

Ecco, quindi, i valori di m entro i quali funziona ciascuna strategia risolutiva: