Lösningar till uppgifterna i
Finalen i Programmeringsolympiaden 2006.

Lösningarna är skrivna i C och sparsamt kommenterade. Tillsammans med kommentarerna nedan hoppas jag ändå att de kan vara till hjälp.

Kom ihåg att alla sätt att lösa en uppgift är rätt utom de som är fel!
Skriv gärna om ni har frågor, kommentarer, tips om andra lösningar m.m. Kolla också gärna in träningssajten.
Pär Söderhjelm, par.soderhjelm@teokem.lu.se
Uppgifterna (PDF) 
Testdata (ZIP)

Uppgift 1 - Lameller

Den första uppgiften vållade en hel del problem, det gäller att ha tungan rätt i mun så att man får med alla möjligheter. Det enklaste är att lägga ut den första lamellen på en fix position, t.ex. med den vänstraste rutan vid koordinat 0. Sedan testar man alla möjliga placeringar av den andra lamellen. Den kan starta så långt till vänster som position -N2 men den kan också starta så långt till höger som +N1 utan att det blir något mellanrum. För varje placering av den andra lamellen går man sedan igenom alla koordinater där åtminstone någon av lamellerna finns och räknar hur många av dessa som har genomgående hål. Man håller förstås reda på det minsta antalet hål man åstadkommit med någon placering hittills.

Lösningsförslag

Uppgift 2 - Summan blir 1

Får väl räknas som en standarduppgift. Eftersom de givna siffrorna endast kan bilda 9! = 9*8*7*6*5*4*3*2*1 = 362880 olika uttryck (eller ännu färre om man tar hänsyn till att termernas ordning inte spelar någon roll) så är det bara att gå igenom alla och testa om värdet blir ett och i så fall skriva ut svaret. De 9! permutationerna kan genereras med en enkel rekursiv funktion eller med hjälp av en färdig funktion i Standard Template Library (STL) om man använder C++, se nedan för båda lösningarna. För att testa om uttrycket är lika med ett utan att behöva bekymra sig om flyttalsprecision kan man använda ett klassiskt trick från skolmatematiken, multiplicera båda sidor med en gemensam nämnare, inte nödvändigtvis den minsta utan för enkelhets skull produkten av de tre nämnarna.

Lösningsförslag (rekursivt)
Lösningsförslag (STL)

Uppgift 3 - Förvirrande SMS

Denna uppgift var det också många som klarade. Återigen räcker det med backtracking. Man håller reda på var man är i sifferföljden och var man är i det ordet man håller på att bilda. När man kommer till slutet av sifferföljden skrivs ordet ut och man hoppar tillbaka (backtrackar) för att se om det finns några alternativa tolkningar. När vi är vid en given siffra, kan vi alltid låta den stå för den första bokstaven på knappen, då hoppar vi helt enkelt ett steg framåt. Om vi ser att nästa siffra är densamma som den vi just nu tittar på, så har vi ytterligare ett alternativ, nämligen att låta de siffrorna ihop stå för den andra bokstaven på knappen och hoppa två steg framåt. Och skulle de två följande siffrorna vara desamma som den aktuella, så har vi ett tredje alternativ, nämligen att låta de tre siffrorna tillsammans stå för den tredje bokstaven på knappen. Men fler än tre alternativ kan aldrig finnas, så det behövs inte ens någon loop.

Lösningsförslag

Uppgift 4 - Ordflätan

Här började många tävlande få problem eftersom det krävdes en ganska effektiv algoritm för att klara de svåraste testfallen. Den naiva lösningen är att ha en rekursiv funktion som fyller i ett vågrätt ord i taget och sedan kollar man på slutet om det stämmer lodrätt också. Problemet är att det finns ca 17 miljarder sätt att välja ut fyra av 800 ord. Visserligen är datorer snabba, men det är ändå lite för mycket, särskilt om man för varje fall ska kolla om de lodräta orden är godkända och inte förekommer flera gånger. Så detta är ett typiskt exempel där man behöver använda s.k. pruning, "beskärning" av sökträdet, d.v.s. att försöka se så tidigt som möjligt när man inte kan nå en lösning med de val man har gjort och därför bör backtracka direkt (se även träningssajten). Det finns många olika sådana optimeringar att göra i denna uppgift, men man behöver inte alls göra alla för att klara tidsgränsen, huvudsaken är att man tänker på någonting. Det kan t.ex. vara att man fyller i orden växelvis vågrätt och lodrätt så att man för varje ordval får färre möjligheter eftersom det begränsas av de tidigare ifyllda orden. Lite knöligt att skriva tycker jag, så mitt lösningsförslag bygger istället på en optimering av den naiva algoritmen. När man sätter dit det andra vågrätta ordet så kan man ju passa på att kolla, för varje kolumn, om de påbörjade lodrätta orden kan bli riktiga ord, d.v.s. om de kombinationerna av två bokstäver förekommer i början av ord, för annars är det ju ingen idé att fortsätta. Och likadant när man fyller i det tredje vågrätta ordet. För att göra den "preliminära" kontrollen på ett effektivt sätt kan man använda tabeller där man från början har sparat om en bokstavskombination är början på ett ord eller inte. Detta kan göras även för fyrbokstavskombinationer, det blir ju bara 26^4=456976 möjligheter, och vips så är också den "slutgiltiga" kontrollen (när alla fyra vågrätta orden är ifyllda) blixtsnabb.

Lösningsförslag
Uppgift 5 - Skidåkning

Detta är ett typexempel på en uppgift som lämpligtvis löses med dynamisk programmering. Problemet har till och med ett eget namn, knapsack-problemet, och har varit föremål för mycket datavetenskaplig forskning. Normalt brukar det formuleras som hur man ska packa en ryggsäck (knapsack) med en viss storlek på ett sådant sätt att den totala nyttan maximeras. Man väljer bland ett antal objekt som vart och ett tar en viss plats och ger en viss nytta. I en version kan man ta flera exemplar av samma objekt, i en annan version högst ett. I den version som diskuteras på träningssajten är nyttan lika med storleken, alltså ett specialfall. I skidåkningsuppgiften är förstås objekten nedfarter, deras "storlek" är den sammanlagda lift- och åktiden och deras nytta är åktiden. Ryggsäckens storlek motsvaras av den maximala tiden M. Uppenbarligen kan man ta flera exemplar av samma objekt, d.v.s. åka samma nerfart flera gånger.

I det generella fallet är problemet NP-komplett, d.v.s. troligen olösbart på polynomisk tid. Om storlekarna är heltal i ett någorlunda litet intervall så finns dock effektiva lösningar med dynamisk programmering. Det gäller att inse att när man har förbrukat en viss tid och uppnått en viss åktid, så spelar det ingen roll för fortsättningen precis vilka backar man har tagit innan. Så om man i en rekursiv lösning hela tiden kollar om man redan har hittat en lösning med exakt samma förbrukad tid men med längre åktid, så kan man ge upp direkt, det kommer aldrig att "ta ifatt" det man ligger efter. Detta är alltså också en form av beskärning av sökträdet, men till skillnad från förra uppgiften är detta en mycket kraftig sådan, man inser lätt att det totala antalet ställningar man kommer till aldrig är fler än t^2 (där t är maxtiden) och i praktiken mycket färre. Ofta är det lättare att bygga upp de bästa dellösningarna svarande mot succesivt ökande förbrukad tid i en tabell så att man slipper rekursera överhuvudtaget, mer om det på träningssajten.

Lösningsförslag
Uppgift 6 - Rinnande vatten

Ingen lyckades lösa detta problem korrekt, men många var på rätt väg. Det är lätt att bli lurad att tro att man kan räkna ut "fyllningstiderna" i en snygg följd uppifrån och ner (likt Pascals triangel) eftersom ett glas fyllningstid vid första anblicken ser ut att bara bero på fyllningstider och fyllningshastigheter i raden ovanför. Men det finns ett problem: medan ett glas håller på att fyllas en bit ner i pyramiden så kan plötsligt ett glas flera rader upp bli fullt och ändra alla fyllnadshastigheter i mellanliggande lager. Men läget är inte alls hopplöst. Man kan nämligen helt enkelt simulera förloppet i tidsordning och hålla reda på hur mycket som för tillfället rinner från varje glas. Det är då lätt att räkna ut vilket glas som härnäst kommer att fyllas och vid vilken tidpunkt detta sker. Då hoppar man fram till denna tidpunkt och uppdaterar alla flöden. På detta sätt fortsätter man tills det intressanta glaset är fullt. Det som många gjorde och som endast gav delpoäng var att istället simulera med ett konstant tidssteg på typ 0.001 sekunder. Dels så förlorar man i exekveringstid, eftersom man behandlar en massa tidpunkter där det inte händer ett skvatt. Dels så förlorar man i noggrannhet eftersom glasen inte nödvändigtvis fylls just vid de simulerade tidpunkterna. Felen som uppstår samlar på sikt ihop sig och kan bli ganska stora.

Lösningsförslag

Uppgift 7 - Avståndstabell

Det här problemet är som Kortaste vägen fast tvärtom, alltså man ska här bestämma grafen när man vet kortaste vägen. Teknikerna man kan använda påminner också om lösningen av Kortaste vägen. Man bygger succesivt upp grafen genom att addera fler och fler bågar (vägar mellan städerna).  Man kollar i avståndstabellen efter det kortaste avståndet som ännu inte har fått sin förklaring i grafen. Detta måste bli en ny direktväg, för om det är en sammansatt väg så måste den involvera minst en ny väg (eftersom den inte gick att förklara). Denna nya väg måste vara kortare än den aktuella, vilket är en motsägelse eftersom man valde det kortaste avståndet.

Lösningsförslag