BOI 2011

OBS! Texten innhåller vissa hintar om uppgifterna. Vill du försöka lösa dem själv så gå direkt till uppgiftssidan istället.

För tolfte gången deltog Sverige i Baltic Olympiad in Informatics (BOI), som avjordes på Danmarks Tekniska Universitet (DTU) i Lyngby, 29/4-3/5. Tävlingen, som samlar deltagare från Estland, Lettland, Litauen, Polen, Tyskland, Danmark, Sverige och Finland, är en miniatyrupplaga av den världsomspännande tävlingen International Olympiad in Informatics (IOI). För Sveriges del fungerar den också som ett välbehövligt träningsläger.

Årets svenska lag bestod av Simon Lindholm, Emil Lenngren, Jonas Olsson och Mårten Wiman (alla Stockholm), Anton Grensjö (Piteå) och Johan Sannemo (Linköping), samt lagledarna Pär Söderhjelm och Arash Rouhani. Som vanligt försökte vi resa "långsamt", den här gången med tåg. Resan började på fredagmorgonen på Stockholms central, utom för Anton som lämnat Piteå redan på torsdagen. Johan och Pär steg på tåget senare på dess väg mot Köpenhamn och anslöt till diskussionerna om bl.a. skolan, programmering, tävlingar och algoritmer. Efter en rejäl tågförsening stövlade vi in på invigningen en minut före utsatt tid och mötes av en - kemishow! Efter en timmes explosioner, uppsprutande maskar och färgmagi släpptes dock deltagarna iväg till sitt rätta element - datorsalarna - för att träna i den Linuxmiljö som skulle användas på tävlingen. För många deltagare kan det vara svårt att vara utan de integrerade utvecklingsmiljöerna man är van vid, men för svenskarna verkade detta inte vara ett problem. Däremot hade några av dem föredragit att skriva i Java, men de tillåtna språken var som vanligt C/C++ och Pascal.

Kalciumkarbid och vatten ger acetylenfyllda bubblor. Hjortar på golfbanan i Dyrehaven. Psykologen.

Medan de tävlande kopplade av på vandrarhemmet i den idylliska Dyrehaven förberedde ledarna den första tävlingsdagen, eller snarare avslutade förberedelserna - varje land hade skickat in varsin uppgift och dessa hade redan diskuterats livligt över internet samt bearbetats av det tyska domarteamet. Tanken var att göra den första tävlingsdagen något lättare än den andra, med en uppgift (Glass) som alla skulle kunna lösa, en ganska standard dynamisk programmeringsuppgift (Tänd lampan), en lite lurig uppgift (Skatter och vikingar) som luktade spelteori men som gick att omformulera till ett ganska rättframt grafproblem, och slutligen en uppgift (Trädodling) där prestandakraven verkade omöjliga men där det gällde att hitta ett annat sätt att representera indatan för att få programmet tillräckligt effektivt. Efter lördagens fem timmar långa tävlingssession stod det klart att problemsetet varit lite väl enkelt, inte mindre än 8 tävlande hade maximala 400 poäng, däribland Simon. Emil och Mårten hade bara tappat poäng på trädodlingen (eftersom de inte hittat den optimala lösningen) och låg med sina 350 och 340 poäng runt plats 10. Även Jonas låg på övre delen av resultatlistan med sina 210 poäng.

Stilstudier av Anton, Emil, Jonas, Mårten, Simon och Johan.

Andra tävlingsdagen var redan betydligt svårare än den första och för att garantera att topp-oktetten splittrades så ökade man indatagränsen på en av dem (Möten) från 10⁵ till 10¹⁵ så att en mer matematisk lösning krävdes. Endast två personer fick lösningen tillräckligt effektiv, men Simons lösning gjorde det nästan. Den allra svåraste uppgiften att ta poäng på var dock Sveriges eget bidrag (Trädspegling), som Jimmy Mårdell föreslagit men som sedan försvårats av Polens lagledare. Här gällde det att både inse vissa egenskaper hos den speciella typ av graf man eftersökte och att implementera grafsökningsalgoritmer i flera steg för att komma fram tll lösningen. Återigen var det endast två personer som löste uppgiften, men denna gång var Simon en av dessa. Med sin lösning inskickad fem minuter före tävlingstidens slut var han märkbart tagen efteråt. Alla svenskarna fick full poäng på den lättaste uppgiften (Plagiering), men förutom Simon och Jonas stannade framgången där. Särskilt dåligt gick det på Polygon, som ingen av svenskarna var i närheten av att lösa. På denna uppgift var man betydligt hjälpt av en enkel formel för arean av en polygon, som dock ingen av svenskarna kände till, något som lagledarna tog till sig som läxa inför framtida tävlingar.

Middag och prisutdelning

Efter genomförd tävling bar det av till det anrika nöjesfältet Bakken där det bjöds på fri åkning och god mat. Utflyktsprogrammet fortsatte sedan på måndagen med båttur runt Köpenhamn och fri rundvandring, varefter hela återsamlades på Experimentarium, där vi hade en helkväll med alla utställningar och två museiguider för oss själva och där vi särskilt fascinerades av Gunther van Hagens utställning av plastinerade människokroppar (Body worlds) på tillfälligt besök i Köpenhamn. En annan höjdpunkt för de tävlande var när de lyckades hacka datorn som konstant skulle köra ett program om energiförsörjning. Med ett meddelande på skärmen som enda effekt får nog BOI-deltagarna räknas som ganska snälla hackers. Prisutdelningen ägde rum inne på Experimentarium och i vanlig ordning var resultatet hemligt och medaljörerna ropades upp i omvänd ordning för spänningseffektens skull. Alla kände dock till resultatet, efter att det dagliga nyhetsbladet publicerat så detaljerad statistik att var och en kunde klura ut sin placering. För Sveriges del blev det medaljregn - Simon fick guld, Mårten och Emil silver och Jonas brons, vilket nog får räknas som Sveriges bästa resultat i BOI någonsin. Speciellt imponerande var Simon, som med sin tredjeplats var den ende i startfältet som kunde utmana de polska eleverna som i vanlig ordning dominerade tävlingen (med placeringar 1, 2, 4, 6 och 7). Den fullständiga resultatlistan finns här.

Svenska laget i BOI 2011. Fr.v. Martin Tange (guide), Arash Rouhani (ledare), Jonas Olsson, Emil Lenngren, Anton Grensjö, Johan Sannemo, Pär Söderhjelm (ledare), Mie Bach-Pedersen (guide), Simon Lindholm och Mårten Wiman. Ingen hjärnaktivitet kunde uppmätas efter prisutdelningen.

Jag tror att alla lämnade Danmark med en positiv känsla. Uppgifterna var svåra, vissa mycket svåra, men inte övermänskliga utan fullt begripliga när man väl insåg tricket. Det var också uppenbart att träning ger färdighet, inte minst för att känna igen problemtyperna och inse vilka som är lättast att ta poäng på. Vid årets IOI i Pattaya City, Thailand, deltar inte Simon (p.g.a. kollision med matematikolympiaden IMO), men genrepet i Lyngby visar att Sverige har ett starkt lag ändå.

Pär Söderhjelm

Fler lagbilder.