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!

CFEngine to sponsor the Norwegian Informatics Olympiad

CFEngine_New_Logo-01

The Norwegian technology company CFEngine develops a tool that automates setup, configuration and monitoring of large numbers of computers. In turn, this makes life easier for developers and system administrators managing large server farms. The tool is available both as a community Open Source edition on github, and as an enterprise edition aimed at businesses.

An example of a task CFEngine can do is to make sure the Apache software is installed and properly configured on all web servers in a company. Whenever new machines are added, they are automatically configured as well.

CFEngine is mainly developed in the C programming language, which is the predecessor of C++ and famous for its speed. Many contestants in the Norwegian Informatics Olympiad (NIO) will feel at home in this language. Part of CFEngine’s success is due to its few platform dependencies and its high performance, which pays off when you’re running on thousands of machines.

We welcome CFEngine as a new sponsor of the Norwegian Informatics Olympiad!

Finaleresultater 2013/2014

Finalen i Norsk informatikkolympiade 2013 / 2014 ble arrangert 22. mars fra 10:40:00 til 15:40:00, og etter heftig koding og debugging trådte det frem noen klare vinnere. De fire beste går videre til International Olympiad in Informatics i Taiwan, og disse pluss de to neste går videre til Baltic Olympiad in Informatics i Litauen. Her er den øverste delen av resultatlisten:

1 Johan S. Wind Kongsbakken VGS 388,63
2 Fredrik Anfinsen Foss VGS 330,00
3 Fredrik Østrem Senja VGS 238,54
4 Håvard Terland Bergen Katedralskole 230,00
5 Håkon Flatval Kristelig Gymnasium 196,69
6 Mikael Klages Valler VGS 194,06
7 Terje Haga Stavnem Tryggheim skular 180,57
8 Michael Hemstad Gimle Rud VGS 178,60
9 Teodor Spæren Ski VGS 160,00
10 Asbjørn Apeland Tryggheim skular 150,00
10 Marcus Gulli Bergquist Nesodden VGS 150,00
10 Karl August Høivik Drammen VGS 150,00
10 Sverre Løyland Oslo Katedralskole 150,00
14 Emil Alexander Vihtari Sandstø Nesodden VGS 140,00
14 Grzegorz Swiderski Ringerike VGS 140,00

Vi gratulerer!

Oppgavene legges ut snart.

Trening til finalen i NIO

Nå ligger treningsoppgaver, inkludert oppgavene fra 2.runde på vår konkurranseserver. Brukernavn og passord er samme som i 2. runde. Treningsoppgavene er tilgjengelige frem til 20. mars.

Under finalen kommer vi til å bruke samme system som under 2. runde, og det vil være fire oppgaver som skal løses. Man får tilbakemelding på hvor mange poeng man har fortløpende under konkurransen. Internett vil ikke være tilgjengelig, og man kan ikke kommunisere med andre unntatt arrangørene. Maskinene man jobber på vil kjøre Linux. Editorer som gedit, vim, emacs, kate og pico er installert (gedit kan lastes ned for windows og mac også, så man kan prøve den ut hjemme). Alle skriftlige hjelpemidler er tillatt, men man kan ikke ta med f.eks minnepenner med kildekode.

Vi anbefaler å løse mange oppgaver i forkant for å bli mer komfortabel med programmering under tidspress!

Resultater fra 2. runde 2013 / 2014

Resultatene fra 2. runde i NIO 2013 / 2014 er nå klare. Nivået på besvarelsene var jevnt over svært høyt i år, og hele seks deltakere klarte å få perfekt poengsum! En ekstra applaus til Fredrik Anfinsen som oppnådde dette allerede klokken halv fem natt til mandag (vi håper det var en rolig dag på skolen).

1867 programmer ble sendt inn (1505 av disse kompilerte uten feil).

Oppgavene fra 2. runde er her:

  1. Brodering
  2. Flywheel
  3. Byggmester
  4. Julegaver
  5. Konsert

Vi har laget et løsningsforslag som forklarer hvordan man kan løse disse oppgavene. Vi kommer dessuten til å legge ut oppgavene på vår treningsserver ganske snart.

Disse 27 går videre til finalen på Universitetet i Bergen 22. mars. Vi gratulerer!

Plass Navn Skole Poeng
1 Fredrik Anfinsen Foss VGS 500
1 Michael Hemstad Gimle Rud VGS 500
1 Bernt Johan Damslora Kristelig Gymnasium 500
1 Ole Kristian Eidem Pedersen Kristiansand Katedralskole Gimle 500
1 Jakob Peder Pettersen Senja VGS 500
1 Johan S. Wind Kongsbakken VGS 500
7 Emil Alexander Vihtari Sandstø Nesodden VGS 470
8 Grzegorz Swiderski Ringerike VGS 450
8 Fredrik Østrem Senja VGS 450
10 Håkon Flatval Kristelig Gymnasium 440
10 Mikael Klages Valler VGS 440
10 Teodor Spæren Ski VGS 440
10 Håvard Terland Bergen Katedralskole 440
14 Thomas Lund Mathisen Kristelig Gymnasium 430
15 Øyvind T. Stubhaug Oslo Katedralskole 410
16 Asbjørn Apeland Tryggheim skular 400
17 Terje Haga Stavnem Tryggheim skular 390
18 Sivert Aasnæss Ringerike VGS 370
19 Marcus Gulli Bergquist Nesodden VGS 360
19 Åsgeir Livar Horpestad Tryggheim skular 360
21 Henning Halvorsen Foss VGS 340
22 Sigurd Alnes Lillehammer VGS 330
23 Martin Simensen Raufoss VGS 290
24 Kari Lovise Lodsby Hadeland VGS 280
24 Sverre Løyland Oslo Katedralskole 280
26 Karl August Høivik Drammen VGS 270
27 Sebastian S. Gundersen Ålesund VGS 260

Dersom du ikke gikk videre, men ønsker å vite din egen plassering kan du ta kontakt på nio@nio.no.

2. runde er i gang!

2. runde av NIO 2013 / 2014 er i gang! Oppgavene finner man på konkurranseserveren (se link øverst til høyre). Vi ønsker alle lykke til med løsningen av oppgavene!

Et lite tips rundt strategi: Det er ikke lurt å vente til siste sekund med å sende inn løsninger. Gjør heller dette så tidlig som mulig for å få tilbakemelding tidlig.

Om du står fast med programmeringen, lurer på hva feilmelding X betyr i C++ osv., så spør oss gjerne på vår Facebookside eller på nio@nio.no.

Resultater fra 1. runde 2013 / 2014

Resultatene fra 1. runde 2013 / 2014 er nå klare. Det kom inn i alt 210 besvarelser, og de 102 beste gikk videre til 2. runde. Oppgavene i år var jevnt over litt vanskeligere enn fjorårets, med unntak av siste oppgave, som var litt enklere.

Oppgavene og fasit kan lastes ned her: oppgaver (fasit).

I runde 2 vil deltakerne måtte skrive dataprogrammer i C++. Dette er ukjent for de fleste, så vi anbefaler å se på Pensum til 2. runde i NIO så fort som mulig (her vil det også snart komme en artikkel med introduksjon til programmering). De som har kvalifisert seg til 2. runde vil snart motta brukernavn og passord til NIOs konkurranseserver via sin faglærer. Der er oppgavene fra tidligere år, som man kan prøve seg på og få umiddelbar feedback fra konkurransesystemet om hvor mange poeng man ville fått. Andre interesserte kan ta kontakt med nio@nio.no for å få påloggingsinfo til serveren.

Her er listen over de som gikk videre. Vi gratulerer!

Plass Navn Skole Poengsum
1 Fredrik Østrem Senja vgs 64
1 Johan S. Wind Kongsbakken VGS 64
3 Lodsby, Kari Lovise Hadeland vgs 61
3 Håkon Flatval Kristelig Gymnasium 61
3 Mikael Klages Valler vgs 61
3 Grzegorz Swiderski Ringerike vgs 61
7 Fredrik Anfinsen Foss VGS 60
7 Håkon Harrington Valler vgs 60
7 Eivind Baltzersen St olav vgs Satvanger 60
7 Arne Tobias Ødegaard St olav vgs Stavanger 60
11 Eivind Vold Aunebakk Fana Gymnas 58
11 Jakob Peder Pettersen Senja vgs 58
11 Karl August Høivik Drammen vgs 58
11 Øyvind T. Stubhaug Oslo katedralskole 58
11 Christian Marinelli Johansen Oslo katedralskole 58
16 Mogens Hestholm Nordahl Grieg vgs 57
16 Ole Kristian Eidem Pedersen KKG 57
16 Mathias Bynke Oslo katedralskole 57
16 Johannes LaCasse Oslo katedralskole 57
16 Eivind Rosón Eide Oslo katedralskole 57
16 Sivert Aasnæss Ringerike vgs 57
22 Jonas Boye Hansen Oslo Handelsgymnasium 56
22 Bernt Johan Damslora Kristelig Gymnasium 56
24 Eivind Grimstad Lillehammer vgs 54
24 Magnus Longva Molde vgs 54
24 Odd Kristian Kvarmestøl Ski vgs 54
24 Tonje Midjås Ski vgs 54
24 Ingrid Dæhlen Valler vgs 54
24 Magnus Muri Drammen VGS 54
30 Terje Haga Stavnem Tryggheim skular 53
30 Thomas Lund Mathisen Kristelig Gymnasium 53
32 Bendik Harto Seim Oslo Handelsgymnasium 52
32 Martin Simensen Raufoss VGS 52
32 Trond Lohne Vågsbygd VGS 52
32 Morten Knappskog Bergen Handelsgymnasium 52
32 Michael Hemstad Gimle Rud vgs. (Gjennomført ved Rosenvilde vgs.) 52
37 Tommy Odeh Tryggheim skular 51
37 Magne Svarverud Skaro Nesodden videregående skole 51
37 Peter Nordrum Riseng Kristelig Gymnasium 51
37 Luca Gazdag Oslo katedralskole 51
37 Jonas S. Lunde Valler vgs 51
42 Sindre Skåland Brun Oslo Handelsgymnasium 50
42 Torstein Rundhovde Bergen Handelsgymnasium (Katten) 50
42 Sebastian S. Gundersen Ålesund vgs, Volsdalsberga 50
42 Sverre Løyland Oslo katedralskole 50
42 Guro Sollien Tyse Oslo katedralskole 50
42 Anna Lina Sjur Oslo katedralskole 50
42 Eric L. Risbakk Valler vgs 50
42 Mathias Hedberg Valler vgs 50
42 Andreas Østhus St Olav vgs Stavanger 50
51 Even Bergersen Vågsbygd VGS 49
51 Eirik Kvalvåg Sandnes vgs 49
51 Bendik Sandøy Molde vgs 49
51 Marcus Gulli Bergquist Nesodden videregående skole 49
55 Vincent Wahl Stabekk vgs 48
55 Sigurd Alnes Lillehammer vgs 48
55 Åsgeir Livar Horpestad Tryggheim skular 48
55 Marcus Hveem Gjøvik videregående skole 48
55 Brede Paulsen Kongsbakken VGS 48
55 Eirik Haugen Kongsbakken VGS 48
61 Kristoffer Seljestad Bergen Handelsgymnasium (Katten) 47
61 Eirik Smithsen KKG 47
61 Geir Olav Furulund Lillehammer vgs 47
61 Aslak Tegle Sande Tryggheim skular 47
61 Jonathan Linnestad Foss VGS 47
61 Randulf Martin Myklebust Aasen Nesodden videregående skole 47
61 Jodans Pedersen Kongsbakken VGS 47
61 David H. Wu Valler vgs 47
61 Simen Keiland Fondevik Valler vgs 47
70 Jørgen Tufteskog Spanne Tryggheim skular 46
70 Nina Lisa Nordskag St. Hallvard vgs. 46
70 Teodor Spæren Ski vgs 46
70 Nikolai Overaae Ski vgs 46
74 Erlend N. Nese Vågsbygd VGS 45
74 Eirik Storrud Røsvik Nesodden videregående skole 45
74 Emil Alexander Vihtari Sandstø Nesodden videregående skole 45
77 Fredrik Fauskanger Sandsli vgs 44
77 Petter Minne Fana Gymnas 44
77 Kjetil Sekse Bergen Handelsgymnasium 44
77 Rasmus Reistad Lillehammer vgs 44
77 Ole Kristian Rønning Valler vgs 44
77 Håvard Ulsbøl Drammen VGS 44
83 Per Magne Røsvik Bømlo vgs 43
83 Gaute Svanes Lunde Bergen Handelsgymnasium 43
83 Peter Salvesen Bergen Handelsgymnasium 43
83 Eivind Bjørsvik Bergen Handelsgymnasium (Katten) 43
83 Marius Aarsnes Molde vgs 43
88 Sander Høyvik Nordahl Grieg vgs 42
88 Ole Marius Volle Haanæs Bergen Handelsgymnasium 42
88 Eivind Meyer Bergen Handelsgymnasium 42
88 Henning Halvorsen Foss VGS 42
88 Erlend Lønhaug Ottesen Gjøvik videregående skole 42
88 Bendik Schrøder Oslo katedralskole 42
88 Johan Ø. Birketvedt Valler vgs 42
88 Christopher W. Gjøvåg St Olav vgs Stavanger 42
96 Ørjan Kobbeltvedt Nordahl Grieg vgs 41
96 Ole Natlandsmyr Fana Gymnas 41
96 Marius Vollen Sortland videregående skole 41
96 Asbjørn Apeland Tryggheim skular 41
96 Herman Farbrot Foss VGS 41
96 Irina Zhevagin Kongsbakken VGS 41
96 Jens Lillethun Ringerike vgs 41