International Olympiad in Informatics 2013, del 2

Etter en sol- og vindfylt ekskursjon til Stillehavskysten (og en ny, lang oversettelsesnatt for lederne) var det duket for den andre konkurransedagen, og alle var ivrige til å vise hva de kunne få til med et fungerende konkurransesystem. Oppgavene var som følger:

  • Den første oppgaven handlet om en hule som var beskyttet av en serie av dører som står innforbi hverandre. Utenfor finnes det en bryter for hver dør, men du vet ikke hvilken bryter som hører til hvilken dør, eller om hver enkelt bryter åpner døren sin ved å stå opp eller ned. Hver gang du stiller inn bryterne, kan du gå inn i hulen og finne den ytterste døren som er stengt. Ved hjelp av færrest mulig forsøk må du klare å åpne alle dørene og finne ut hvilken bryter som hører til hvilken dør.
  • En av oppgavene handlet om forskjellige typer roboter som kunne rydde bort leker fra gulvet. Ut fra hva slags leker som ligger på gulvet og hva slags roboter man har måtte man delegere arbeid til robotene slik at de klarer å rydde gulvet fortest mulig.
  • I den tredje oppgaven skulle man lage et program som kunne spille et spill som handlet om å gjentatte ganger regne ut fellesnevneren til attensifrede tall som var spredd utover et rutenett – med den ekstra utfordringen at rutenettet som tallene var spredd utover kunne inneholde inntil en trillion ruter…

Heldigvis fungerte konkurransesystemet fint denne gangen (selv om det ble litt kaos i forbindelse med noen feil i en av oppgavetekstene). Dessverre ble det ingen medalje på Norge i år, men Fredrik sanket likevel respektable 156 poeng og kom på en tredelt 190. plass. [Opprinnelig stod det 189. plass her, men stillingene endret seg litt etter at en deltager fikk poengene sine justert etter en klage.] (Grensen for å få bronsemedalje endte opp på 220 poeng.) Ellers ble Sondre første nordmann på ni år som har fått full poengsum på en oppgave, da han leverte en perfekt løsning på huleoppgaven. Vi gratulerer!

På torsdag dro alle på ekskursjon til Australia Zoo. Med unntak av en litt vel høy reklamefaktor basert på Steve Irwin var det en fin park, og høydepunktene var å kunne vandre rundt blandt frittgående (evt. fritthoppende og frittsovende) kenguruer og koalaer, og å få demonstrasjoner av krokodillenes angrepshastighet. Det eneste som gjenstår på programmet nå er avslutningsseremoni og to avsluttende kvelder med sosialisering (ihvertfall for deltagerne – lederne må gjennom en del møter…) før to av oss drar tilbake til Norge og de fire andre tar en velfortjent ferie i Australia. Nils og Arne begynner på datateknikk på NTNU til høsten, mens Sondre skal i førstegangstjeneste – men Fredrik kommer sterkt tilbake til høsten og sannsynligvis IOI 2014 i Taiwan.

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!