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.]

Leave a Reply

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