International Olympiad in Informatics 2014, del 4

Etter et velfortjent besøk til en fornøyelsespark/badeland og en tur opp i Taipei 101, som med sine 101 etasjer og 509 meter var verdens høyeste bygg fra 2004 til 1010, gjenstod bare én ting på programmet: avslutningsseremonien, hvor medaljene deles ut. Det var en veldig god følelse å se en nordmann på scenen etter ti års medaljetørke!

Laget på toppen av Taipei 101:

Laget på toppen av Taipei 101

Taipei by night, sett fra Taipei 101:

Taipei by night, sett fra Taipei 101

Johan får utdelt medalje og diplom under avslutningsseremonien (diplomene ble dessverre stokket om, så han holder en annens diplom):

Johan får utdelt medalje og diplom under avslutningsseremonien

Johan med medaljen utenfor Taipei 101:

Johan med medaljen utenfor Taipei 101

Med unntak av Åsmund, som har blitt igjen i Taiwan for en ukes ferie (for lederne består IOI stort sett av møtevirksomhet, konferanser og oppgaveoversettelse), kom alle tilbake til Norge på mandag morgen. Fredrik Anfinsen og Fredrik Østrem begynner å studere på Universitetet i Oslo til høsten og kan dermed ikke delta mer i IOI (men vi forventer at de kommer til å gjøre det sterkt i NM i Programmering, som er en programmeringskonkurranse for studenter) – men Johan og Håvard er allerede i gang med å forberede seg til neste års Norsk informatikkolympiade og, hvis de nok en gang vinner NIO, International Olympiad in Informatics 2015 i Astana i Kazakhstan. Den norske delegasjonen fra IOI 2014 takker for seg!

International Olympiad in Informatics 2014, del 3 – endelig medalje!

Etter en solid innsats på den andre konkurransedagen kom Johan Sokrates Wind på 115. plass med 278 poeng, og fikk dermed bronsemedalje! Dette er ekstra stas siden det Norges første medalje siden 2004! Fredrik Østrem kom på en respektabel 175. plass med 189 poeng. Johan klarte dessuten å løse en av oppgavene (“Gondola”) perfekt, og det er også en sjeldenhet i Norge. Vi gratulerer!

Her er deltagerne i gang med ivrig diskusjon om hverandres løsninger i etterkant av konkurransen:

Etter andre konkurransedag

Oppgavene

  • “Gondola” handlet om en gondolbane med nummererte gondoler, hvor noen av gondolene har brutt sammen og blitt byttet ut med nye gondoler med stadig økende numre. Oppgaven var delt inn i tre underoppgaver som krevde hvert sitt delprogram: en hvor programmet skulle finne ut om en gitt tallsekvens kunne representere en slik sekvens med gondolnumre, en hvor programmet skulle finne en mulig forklaring på hvilke gondoler som har brutt sammen ut fra hvordan gondolsekvensen ser ut nå, og en hvor programmet skulle regne ut hvor mange mulige måter gondolene potensielt sett kunne ha brutt sammen ut fra den nåværende gondolsekvensen (her kunne svarene bli astronomiske, så man måtte redusere tallet med en bestemt matematisk operasjon før man svarte).
  • “Friend” handlet om sosiale nettverk, som jo er veldig tidsriktig. Det skal gjøres en undersøkelse blant brukerne av nettverket, men forskjellige personer har forskjellig troverdighet, og man ønsker ikke å spørre folk som er venner med hverandre. Her måtte man skrive et program som først finner ut hvordan nettverket ser ut ut ifra en beskrivelse av rekkefølgen folk har lagt hverandre til i (og om de har delt venneflokkene sine med de man blir venner med, noe Facebook heldigvis ikke lar deg gjøre), og deretter velge ut folk til spørreundersøkelsen på en slik måte at ingen av de utvalgte er venner med hverandre og den samlede troverdigheten er størst mulig.
  • I “Holiday” er man på ferie i Taiwan, og ønsker å besøke attraksjoner i de forskjellige byene. Hver dag kan man enten besøke alle attraksjonene i den byen man er i, eller reise til en av de to nabobyene (alle byene ligger tydeligvis etter hverandre langs en lang vei). Her skulle man skrive et program som, ut ifra hvilken by man starter i og en oversikt over antallet attraksjoner i hver by, finner ut hvordan man kan få med seg flest mulig attraksjoner før ferien er over.

Som nevnt på tirsdag er oppgavene mye vanskeligere enn de kanskje høres ut her; du kan bryne deg på oppgavene selv hvis du føler at det klør i programmeringsfingrene!

International Olympiad in Informatics 2014, del 2

Norge har levert en av de beste førsteomgangene sine på mange år – Johan Sokrates Wind ligger på 128. plass blant 311 deltagere med 104 av 300 poeng; Fredrik Østrem ligger på 150. plass med 103 poeng; begge ligger dermed an til bronsemedalje hvis de holder trykket oppe på torsdag! (For de som ikke kjenner til medaljesystemet til de internasjonale realfagsolympiadene, er det slik at den beste tolvtedelen av deltagerne får gullmedalje, de neste 2/12 får sølv, og de neste 3/12 får bronse.) Den fullstendige resultatlisten finnes på http://live.ioi2014.org/Ranking.html, og kommer til å oppdateres live også under konkurransen på torsdag.

Her diskuterer deltagerne oppgavene og løsningene umiddelbart etter konkurransen:

Deltagerne etter første konkurransedag

Oppgavene

  • I “Wall” skulle man bygge en mur på en litt spesiell måte: muren er delt inn i mange søyler med mursteiner som er lagt oppå hverandre. Byggingen foregår i faser; i hver fase tar man noen av søylene og enten bygger dem opp til en bestemt høyde (men søyler som allerede er høyere enn dette blir stående) eller river dem ned til en bestemt høyde (men søyler som allerede er lavere enn dette blir stående). Oppgaven var å finne ut hvordan muren ble seende ut til slutt. Det er jo i utgangspunktet enkelt å bare simulere denne byggeprosessen, men utfordringen ligger i at muren kunne være to millioner søyler bred og at det kunne være en halv million byggefaser, og programmet man skulle levere måtte finne svaret i løpet av tre sekunder.
  • “Game” handlet om en slags gjettelek der en person stiller spørsmål av typen “Finnes det en direkte flyrute mellom by A og by B?” til en annen person. Ut fra svarene prøver den første personen å finne ut, ved hjelp av færrest mulig spørsmål, hvorvidt det er mulig å komme seg rundt i hele landet ved hjelp av fly, eller om det finnes byer som ikke kan nåer fra andre byer. Oppgaven var å skrive et program som kan hjelpe den andre personen med å jukse: etterhvert som den første personen stiller spørsmål, finner programmet på svarene underveis på en slik måte at det blir så vanskelig som mulig å resonnere seg frem til hvorvidt flynettverket henger sammen.
  • “Rail” handlet om et spesielt jernbanenettverk som bare består av én østgående skinnegang og én vestgående, og noen tverrgående forbindelser mellom disse. Man skulle prøve å finne ut hvordan nettverket faktisk er utformet, ved hjelp av å stille færrest mulig spørsmål av typen “Hva er avstanden mellom stasjon A og stasjon B?” Her måtte man skrive et program som kan finne en intrikat rekkefølge å stille spørsmålene på slik at programmet får mest mulig informasjon ut av færrest mulig svar. Dette viste seg å være den vanskeligste oppgaven, og bare 17 av de 311 deltagerne fikk full score på denne.

De faktiske oppgavene er vesentlig mye vanskeligere enn de kanskje høres ut her; de som er interesserte oppfordres til å sjekke de originale oppgavetekstene når disse legges ut.

[Merk: Antallet deltagere, 311, er annerledes enn antallet rader i scoreboard’et, siden noen av de påmeldte deltagerne ikke dukket opp. Den originale artikkelen sa 310, da en av deltagerne mistet flyet sitt, men vedkommede dukket opp til andre konkurransedag.]

International Olympiad in Informatics 2014, del 1

Etter NIO-finalen i mars kom Johan Sokrates Wind (Kongsbakken VGS), Fredrik Anfinsen (Foss VGS), Fredrik Østrem (Senja VGS) og Håvard Terland (Bergen Katedralskole) seirende ut, og skal dermed forsvare Norges ære i International Olympiad in Informatics, som i år foregår i Taipei, hovedstaden i Taiwan. Sammen med dem reiser laglederne, Åsmund Eldhuset og David Narum, som selv har deltatt i IOI, og nå er med på å arrangere NIO. Alle unntatt Johan dro fra Gardermoen på fredag og ankom Taipei på lørdag etter 30 timers reisetid. I og med at de fleste andre delegasjonene ankom på søndag, fikk vi et ekstra døgn til å kvitte oss med jetlag, så vi satser på at dette gir oss et konkurransefortrinn. Johan fløy i stedet fra Sør-Afrika, hvor han har deltatt i International Mathematics Olympiad og tatt en meget imponerende sølvmedalje.

Fredrik Anfinsen deltok på IOI i fjor, så i likhet med Johan har han fordelen av å kjenne til realfagsolympiadeopplegget fra før av, og han har trent mye på egenhånd siden da. Tre av deltagerne deltok også på en treningsleir som ble arrangert av NIO i juni, så alle burde være godt forberedt.

Klimaet i Taipei er varmt (30-35 grader) og fuktig døgnet rundt, men regntiden har foreløpig bare gitt utslag i én regnskur. Kvaliteten på innlosjeringen varierer fra år til år ut ifra hvor mye sponsormidler IOI-arrangørene har fått tak i, men i år har de slått på stortrommen og skaffet to av de bedre hotellene i Taipei – og heldigvis er det airconditioning i alle rom.

Som vanlig får hver delegasjon tildelt en egen guide, som har ansvaret for å vise oss rundt og holde orden på at deltagerne kommer seg dit de skal i rett tid (siden laglederne ofte er opptatt i møter). Guidene er frivillige studenter eller elever fra universiteter eller skoler i nærheten, og Taiwan hadde visst gått ekstra grundig til verks: de som meldte seg måtte på audition for å vise frem engelskferdighetene og kunnskapen om landet de skulle jobbe med. Vår guide heter Coco, og er veldig trivelig og hjelpsom, og snakker strålende engelsk siden hun har bodd i Sør-Afrika i ti år.

I dag (mandag 14.) har det vært en treningsrunde hvor både deltagerne og lederne fikk tilbringe noen timer i konkurranselokalet, for å bli vant med PC’ene og konkurransesystemet, og å varme opp programmeringsfingrene med noen treningsoppgaver:

Treningsrunde

På åpningsseremonien ble vi hilst velkommen av ingen ringere enn Taiwans visepresident, og vi fikk noen imponerende opptredener fra dansegruppe som drev med tradisjonell dragedans, og en gruppe med sjonglører som gjorde ting vi trodde var fysisk umulig med “Diablo”-jojoer. Etterpå var det tid for et lagbilde:

Lagbilde

Første konkurransedag er i morgen, og da skal deltagerne få bryne seg på de første tre oppgavene i løpet av fem timer (09:00-14:00, eller 03:00-08:00 norsk tid). Vi venter i spenning på utfallet!