International Olympiad in Informatics 2013, del 1

Etter over tretti timer på reisefot ankom det norske laget Brisbane, klare for årets International Olympiad in Informatics. Årets deltagere, som er de fire beste fra Norsk informatikkolympiade 2013, er Nils Barlaug (Valler VGS), Fredrik Anfinsen (Foss VGS), Arne Lyngstad Sund (Ringerike VGS) og Sondre Sortland (Bergen Handelsgymnasium). Nils og Arne deltok i IOI i fjor også, og har dermed fordelen av å kjenne til opplegget fra før av. Laglederne, Åsmund Eldhuset og David Narum, har selv deltatt i IOI, og er nå med på å arrangere NIO.

De som hadde gledet seg til å slikke sol hadde nok glemt å tenke på at det er vinter i Australia nå – likevel er klimaet nå sammenlignbart med en gjennomsnittlig norsk maidag med godt vær, så vi lider ingen nød. Guiden vår, Lauren, studerer ingeniørvitenskap (med planer om å spesialisere seg i gruvedrift) på University of Queensland, hvor IOI foregår. Universitetsområdet er veldig flott, med mye interessant arkitektur og mange grøntarealer.

IOI2013-lagbilde
Fra venstre: Åsmund Eldhuset (lagleder), Arne Lyngstad Sund (deltager), Sondre Sortland (deltager), Lauren Dickie (guide), Fredrik Anfinsen (deltager), Nils Barlaug (deltager) og David Narum (assistentleder).

Den første dagen og natten gikk stort sett med til å venne seg til tidsforskjellen, og alle kom seg opp til treningsrunden på søndag. Åpningsseremonien var relativt kortfattet i forhold til hva de pleier å være (like greit), med noen få taler fra prominente personer og en danseoppvisning. Etter litt diskusjon om oppgavestrategi og gjennomgang av alle reglene for hva programmene man skriver ikke har lov til å gjøre, startet karantenen hvor lederne og deltagerne ikke får lov til å kommunisere. Dette skyldes at lederne får se oppgavene kvelden før hver konkurransedag, slik at de kan si ifra hvis deltagerne deres har sett en tilsvarende oppgave før, og slik at de landene som trenger det kan oversette oppgavene til deltagernes eget språk – IOI er i stor grad basert på tillit.

Oppgavene var kreative, og som vanlig var flere av dem inspirert av vertslandet – denne gangen av dyrelivet. Merk at dette er veldig forenklede fremstillinger av oppgavene; de nysgjerrige oppfordres til å lese de fullstendige oppgavetekstene når disse blir tilgjengelige.

  • Den “enkleste” oppgaven handlet om et samling med vannhull som har stier mellom seg, og hvordan man burde bygge flere stier på en slik måte at avstanden mellom vannhullene som er lengst fra hverandre blir kortest mulig [korreksjon: opprinnelig stod det “lengst mulig”]. Her trengte man noen etablerte algoritmer fra grafteori for å finne egenskaper ved det eksisterende stinettverket, samtidig som at man på egen hånd måtte utlede algoritmen for å velge hvor man skulle bygge de nye stiene basert på egenskapene til de eksisterende.
  • Den andre oppgaven var usedvanlig på den måten at den ikke krevde tradisjonell algoritmeteori for å løse. I stedet var det snakk om å klassifisere malerier fra forskjellige perioder, så her ble det snakk om kreative påfunn av algoritmer for bildeanalyse.
  • Den vanskeligste oppgaven handlet om at Brisbane er blitt invadert av muterte vombater. Folk må rømme fra byen gjennom et veinett på en slik måte at de støter på færrest mulig vombater. I utgangspunktet kan det løses ved hjelp av kjente grafalgoritmer eller dynamisk programmering, men det ble vesentlig mye vanskeligere av at antallet vombater rundt omkring i byen hele tiden endret seg. Her måtte man både bruke dynamisk programmering og såkalte segmenttrær for å løse oppgaven optimalt.

Dessverre slo konkurransesystemet seg vrang etter at en drøy time hadde gått, og dermed måtte man kode i blinde uten å få tilbakemelding på hvor mange poeng besvarelsene ens hadde fått. (“Akkurat som i gamle dager”, i følge Åsmund og David…) Dette gjorde at de fleste fikk færre poeng enn de kunne ha fått hvis de hadde fått se hvor besvarelsene deres feilet og fått sjansen til å justere ting – men i det minste slo dette relativt likt ut for alle de 299 deltagerne [korreksjon: opprinnelig stod det 315, men dette var et midlertidig tall som ikke tok hensyn til at enkelte lag ikke møtte opp]. Fredrik og Nils kom best ut med 55 poeng, og ligger foreløpig på en syvdelt 180. plass. Konkurranseproblemene ble diskutert i tre timer og ett kvarter på kveldens General Assembly-møte, som består av IOI-arrangørene og alle laglederne. Etter mye frem og tilbake og tre avstemningsrunder ble konklusjonen at poengene fra dag 1 blir stående som de er (i stedet for at man vekter de to dagene forskjellig eller forkaster dag 1 fullstendig).

I morgen vil deltakerne trenge litt hvile, så da skal alle på ekskursjon til Sunshine Coast og Underwater World. Etter det regner vi med at alle er klare til en ny konkurransedag på onsdag. Vi gleder oss!

Leave a Reply

Your email address will not be published. Required fields are marked *