Kommentarer och lösningar till uppgifterna i
Finalen i Programmeringsolympiaden 2002.

Lösningarna är skrivna i C/C++ och följer tävlingsstandarden på så sätt att de är helt okommenterade och obegripliga. I några fall används stdin istället för läsning från fil.

Uppgifterna (PDF)
Testdata (ZIP)

Uppgift 1 - Nattlig förflyttning

Ett enkelt sätt att lösa uppgiften är med rekursion (s.k. backtracking). I varje steg kommer alltid två personer att gå över, varefter en person går tillbaka med ficklampan om det finns några personer kvar att hämta. Om man kommer på att det alltid är den snabbaste personen som ska gå tillbaka så hinner man gå igenom alla möjliga sätt att göra förflyttningen, eftersom det då bara finns 21*15*10*6*3 = 56700 sätt (2 av 7 kan väljas på 21 sätt, 2 av 6 på 15 sätt o.s.v.)

Detta är naturligtvis en väldigt dålig metod om man har många personer, eftersom tidsåtgången för programmet när man har n personer ungefär blir proportionell mot (n!)^2. Exempelvis fungerar det inte för 10 personer. Vi fick in många bättre bidrag av typen dynamisk programmering, vilket fungerar bra eftersom antalet "tillstånd" bara är 2^8.

Lösningsförslag

Uppgift 2 - Ordlek

Detta är ett typexempel på backtracking. Man har en lista på vilka bokstäver som finns kvar att använda. Så testar man först vilken bokstav som kan sättas som första bokstav i ordet som ska bildas. När man hittat en giltig bokstav stryker man den från listan och anropar samma funktion igen (rekurserar) fast nu börjar man från andra bokstaven i ordet o.s.v. Varje gång man placerar en bokstav måste man kolla att stavningsreglerna uppfylls. När man sätter dit A eller G, de bokstäver som kan vara sista bokstav i ordet, kollar man om det ord som har bildats är längre än det tidigare längsta ordet. När man har testat alla möliga bokstäver på en position, går man tillbaka till föregående position, sätter tillbaka den bokstaven i listan och fortsätter med nästa testbokstav på den nivån. Allt detta kan skötas med en rekursiv funktion, eller som i lösningsförslaget några olika för folofjant, pedal respektive valfri bokstav.

Lösningsförslag

Uppgift 3 - Wildcards

Gå igenom alla städerna i tur och ordning och se om de matchar söksträngen. Att göra själva matchningen tillhör praktiskt sett de viktigaste algoritmiska problemen (används t.ex. inom bioinformatik) och har genererat mängder av intressanta metoder som kan vara värda att sätta sig in i. Eftersom stränglängden i denna uppgift var tämligen begränsad, räcker det dock med en rekursiv funktion av samma typ som i uppgift 2. Om en bokstav matchar exakt eller om söksträngstecknet är ? är det bara att gå vidare med nästa bokstav. Om söksträngstecknet är * så kan man t.ex. testa att hoppa fram alla möjliga steg i namnet (0, 1, 2 o.s.v. ), vilket mosvarar att asterisken får ersätta det antalet tecken. Om man efter ett antal steg finner att namnet och sökstränget slutar samtidigt så har man hittat en sökträff.

Lösningsförslag

Uppgift 4 - Alfametik

Lämpligen så börjar man med att lokalisera de unika bokstäverna (max 10 st) och därefter lagra dessa in en liten tabell. Sedan tittar på alla möjliga kombinationer att placera ut siffrorna 0-9 på de 10 bokstäverna. Antalet
möjliga sådana permutationer är 10! = 10*9*8*7*6*5*4*3*2*1 = 3628800 vilket med dagens
datorer inte tar lång tid. För att gå igenom alla permutationer kan man antingen
använda rekursion eller, om man programmerar i C++, STL funktionen next_permutation. För varje permutation kontrollerar man sedan om additionen stämmer samt att inga bokstäver som är först på en rad blev tilldelad en nolla. Exempellösningen är lite överkomplicerad eftersom den även tillåter siffror i termerna/summan.

Lösningsförslag

Uppgift 5 - Motorvägar

Denna uppgift löser man genom att använda sig av ett minimalt uppspännande träd (se träningssidan ). Det som kan vara förvillande är att vissa vägar redan är motorvägar, vilket gör att den uppspännande grafen inte nödvändigtvis är ett träd. Likväl är det samma algoritm man använder, t ex Kruskal eller Prims algoritm.

Lösningsförslag

Uppgift 6 - Ett markant problem

Detta var tävlingens svåraste uppgift, vilket var planerat. Om storleken på området hade varit mindre hade uppgiften varit betydligt enklare. Då kan man lagra hela området i en stor matris och genomföra flera stycken floodfills. Dvs, man börjar i en ruta i matrisen som inte ännu är fylld, "fyller" området (med en DFS eller BFS sökning) tills man stöter på staket samt lagrar hur många rutor man fyllde. Detta upprepas tills hela området blivit fyllt, och man har då storleken
på alla områden.

Men nu kunde området vara väldigt stort, och att skapa en matris på hela området på en gång är inte möjligt. Men antalet staket i området är litet, max 50 st, vilket innebär att antalet unika x resp. y koordinater som används av staketen är max
100. Med andra ord kan området skalas ner till ett område med storleken 100x100. Därefter
används algoritmen ovan, och vid beräknandet av arean så skalar man upp storleken
på rutorna i matrisen.

Lösningsförslag

Uppgift 7 - Snöplogning

Här var det meningen att man skulle använda sig av dynamisk programmering (se träningssidan ). Detta är möjligt tack vare de enkelriktade huvudgatorna. Om man har räknat ut den "maximala vägen" för varje tidsåtgång när man kommit n steg i östlig riktning, så kan man direkt räkna ut de maximala vägarna till korsningarna n+1 steg i östlig riktning, eftersom man vet att man aldrig kommer att åka tillbaka åt väster.

Låt T(x, y, t) beteckna maximala nyttan för vägen med tiden t till koordinat (x, y) samt h(x, 0), h(x, 1) och m(x) nyttorna för den södra huvudgatan, norra huvudgatan respektive tvärgatorna. Från början ses att T(0,0,0) = 0, T(0,1,1) = m(0) och T(0,0,2) = m(0). För varje x-koordinat börjar man med att ta huvudgatorna dit, d.v.s. T(x, y, t) = T(x-1, y, t-1) + h(x, y). Sedan ska man åka på tvärgatorna och då finns det fyra sätt att åka: norrut, söderut, norrut + söderut och söderut + norrut (notera att det aldrig är någon idé att åka mer än två gånger på samma tvärgata). Det enklaste är att ta de fyra fallen i tur och ordning. Det tredje fallet leder till exempel till T(x, 0, t) = T(x, 0, t-2) + m(x) eftersom man bara tjänar nytta åt ena hållet. Det man sparar i T är naturligtvis maximum för alla fallen. Det gäller också att hålla tungan rätt i mun så att man inte råkar skriva över något värde som man sen har tänkt att använda. I exempellösningen används en kompaktare tabell med antalet "omvägar" istället för tiden som sista index till T, men det är naturligtvis valfritt.

Det finns andra sätt att lösa uppgiften. Exempelvis kan man gå rekursivt och bara kolla i varje "tillstånd" (x, y, t) om man har varit där innan och då haft bättre nytta, i så fall är det ju hopplöst och man ska backtracka istället. Man kan visa att det värsta teoretiska fallet då blir ca 200 miljoner rekursiva anrop, vilket fortfarande går att klara inom tiden. Tyvärr var det många som gjorde rekursiva lösningar utan denna optimering. Då blir det värsta fallet upp mot 2^200, vilket tar ett tag. ..

Lösningsförslag

Uppgift 8 - Flyken till vadstället

Denna uppgift är ett typexempel på ett kortaste-vägen problem (i det här fallet egentligen snabbaste-vägen, men det är samma sak). Effektivast löser man ett sådant problem genom att använda sig av Dijkstras algoritm (se träningssidan ) men eftersom grafen var väldigt speciell så gick den att lösa med rekursion och dynamisk programmering om man var lite klurig.

Lösningsförslag