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!

Første runde i NIO 2013

Norsk informatikkolympiade er en programmeringskonkurranse for elever i videregående. Første runde foregår i uke 45 (5.-9. november), så den nærmer seg med stormskritt! Har du lyst til å delta? Ta kontakt med IT- eller mattelæreren din og få ham/henne til å melde på skolen din! Dersom du befinner deg i Oslo, Trondheim eller Bergen vil det også være mulig å delta på universitetene i disse byene.

I Oslo kan man, dersom skolen ikke arrangerer NIO, delta i 1. runde av NIO onsdag 7. november på Institutt for Informatikk ved UiO. Se kart. Oppmøte kl 18:30 for registrering. Konkurransen foregår i seminarrom “C” (oppkalt etter programmeringsspråket) i tredje etasje.

I Bergen kan man delta på UiB onsdag 7. november kl 18:00 dersom skolen ikke arrangerer NIO (nøyaktig sted og instruksjoner kommer snart).

I Trondheim kan man delta onsdag 7. november kl 18:30 dersom skolen ikke arrangerer NIO. Dette foregår på Realfagbygget på NTNU; ring 95 93 98 26 når du kommer dit for å bli sluppet inn.

Deltar du på et av disse tre stedene bør du melde deg på for å være garantert en plass.

Er du nysgjerrig på programmering, men har ikke drevet med det før? Ingen grunn til panikk; første runde vil inneholde en del matte- og logikkoppgaver i tillegg til programmeringsoppgaver, og etterhvert som andre runde nærmer seg vil vi poste en del ressurser for å lære seg programmering.

IOI 2012, del 2: Første omgang

De norske deltakerne får se resultatet fra 1. konkurransedag

De norske deltakerne får se resultatet fra 1. konkurransedag

Første konkurransedag er over, og adrenalinet pumpet fortsatt i de fire deltagerne da de kom ut fra konkurranselokalet. Som vanlig etter en konkurranseomgang var det fornøyelse over det man hadde fått til, frustrasjon over ting som hadde gått galt, og såre underarmsmuskler etter fem timers intensiv koding.

Den mest interessante oppgaven handlet om en maskin som kunne flytte småsteiner rundt på et rutenett, og som kunne programmeres med et ekstremt primitivt programmeringsspråk. Utfordringen var å skrive programmer i dette språket for å utføre forskjellige oppgaver med småsteinene – dette var en ganske uvanlig oppgavetype, i og med at oppgavene vanligvis skal besvares med ordentlige programmeringsspråk som f.eks. C++.

Den mest utfordrende oppgaven handlet om å analysere en samling med metallringer som var lenket i hverandre på forskjellige måter, og finne ut hvilke ringer som var “kritiske”, dvs. som vil føre til at ringsamlingen brytes i to hvis de fjernes. I likhet med mange andre nedprioriterte våre deltagere denne oppgaven til fordel for de to andre.

Den siste oppgaven handlet om en slags skrivemaskin med angrefunksjonalitet, hvor angrekommandoene i seg selv kunne angres i etterkant, og man skulle finne ut hva som var sluttresultatet av en lang sekvens med kommandoer.

Nils Barlaug imponerte med 93 poeng og 150. plass, som var nok til en plassering blant medaljekandidatene (halvparten av deltagerne får medalje).

— Åsmund og Markus

Baltic Olympiad in Informatics 2012

Det norske laget

De norske deltakerne i BOI 2012: Fra venstre Håkon Strujik Holmen, Arne Lyngstad Sund, Tobias Hallingstad, Nils Barlaug, Henrik Hodne, Edgar Vedvik

Norge deltok for første gang på fire år i den baltiske informatikkolympiaden i Ventspils, Latvia 3. – 7. mai. Selv om oppgavene var ekstremt vanskelige i år, klarte alle seks å ta poeng, men det rakk ikke til medalje denne gangen. Se resultatlista her.

Mellom øktene med oppgaveløsning ble det også tid til mange ekskursjoner, spill og å bli kjent med deltakere fra noen av de åtte andre landene som deltok. Det ble også en lærerik tur, med introduksjon til mange nye, spennende problemer og algoritmer. Den vanskeligste oppgaven i konkurransen (Tiny), ble i etterkant løst av en av de norske deltakerne. Se oppgavene her.

Vi er optimistiske med tanke på IOI i Italia i høst og neste år for de av årets deltakere som fortsatt kan delta i 2013!