För att lyckas hålla sig inom gränsen för antalet kommandon bör man använda en variant av tekniken Divide & Conquer som påminner om binärsökning. Denna utförs genom att man för varje tråd (wire) håller reda på mängden möjliga lösningar, d.v.s. minsta och största numret på den brytare (switch) som tråden är kopplad till.

Från början är denna mängd = {1..m} för alla trådar. Då kör man en rekursiv funktion som gör följande:

*Låt intervallet som funktionen kör på vara L..R och antag att alla brytare däremellan har boolean-värdet p.
(Första gången är alltså L=1, R = m)
*Välj talet h i mitten av intervallet L..R
*Ändra alla brytare med nummer L..h till NOT p
*Testa om glödlampan lyser för varje tråd vars möjliga lösningar är L..R. (*)
Beroende på om den lyser eller inte och på hur vi har ställt brytarna (d.v.s. om p = true eller false) kan vi minska den tänkbara lösningsmängden för varje tråd till antingen {L..h} eller {h+1..R}
*Kör den rekursiva funktionen på L..h
*Kör den rekursiva funktionen på h+1..R

Lägg märke till att när vi kör den rekursiva funktionen på L..h så vet vi att alla brytare däremellan står i samma läge, antingen på eller av. Eftersom vi enligt rad (*) bara kommer att bry oss om de trådar vars möjliga lösningar ligger i detta intervall, behöver vi inte bry oss om ett dugg i vilket läge alla övriga brytare står.

Problemmakarna har varit ovanligt elaka här och lagt gränsen mycket snävt, så för att få full poäng krävs att man gör en ytterligare optimering, nämligen att man kollar om det verkligen är nödvändigt att rekursera i båda intervallen. Det kanske ändå inte är någon tråd som har den tänkbara lösningsmängden i t.ex. det lägre intervallet. Då kommer visserligen inte rad (*) att utföras, men då har vi ju ändå förlorat kommandon på att ställa om brytarna i onödan.

Tillbaka