Archive for August, 2014

Aug 07 2014

IOI 2014

Published by Targo under Haridus, Maad ja rahvad

Reportaaž Eesti võistkonna kogemustest 2014 Rahvusvahelisel Informaatikaolümpiaadil Taiwanis. Tekst – Targo, pildid – Simmo, Ahto, Targo

Olümpiaadidest

Hulk aastaid tagasi olin usin olümpiaadidel käija. Pingutus tasus end paljukordselt ära, nii konkreetsete probleemilahendusoskuste, sotsiaalsete sidemete kui lihtsalt laiema silmaringi osas.

Iseenesest need üritused siiski ei juhtu – kui Teaduskool täidab koordineerivat rolli, siis konkreetsete aineolümpiaadide õnnestumisele aitab kaasa veel terve hulk vabatahtlikke. Siinkohal edastan ka tänusõnad oma kunagistele juhendajatele, kes kogu seda vaeva viitsisid näha. Samuti tasun oma kogunenud karmavõlga ja löön ise kaasa olümpiaadide korralduses, eriti informaatikas.

Informaatikaolümpiaadi hooaeg kestab läbi terve õppeaasta. Eesti Informaatikaolümpiaadi toimkond korraldab mitmesuguses formaadis võistlusi, millest tähtsaim on riiklik lõppvoor. Lõppvooru parimad kutsutakse valikvõistlusele, kus selguvad koondise liikmed rahvusvahelistel võistlustel osalemiseks. Tavaliselt lööme kaasa Balti Informaatikaolümpiaadil (millest võtavad osa Läänemere äärsed riigid ja Norra) ning Rahvusvahelisel Informaatikaolümpiaadil (International Olympiad in Informatics, IOI), millel oli sel aastal üle 80 osalejariigi.

Ülesannetest

Informaatikaolümpiaadil tuleb ajapiirangu raames kirjutada programme, mis lahendavad algoritmilise iseloomuga ülesandeid. Lahendused peavad läbima hulga teste, mille eest saab punkte. Testid jagunevad laias laastus kaheks: esimene kategooria teste kontrollivad programmi korrektsust, katsetades mitmesuguseid erijuhtumeid, teine kategooria aga programmi jõudlust, andes sellele ette järkjärgult suuremaid andmehulki. Lahendustel on ajapiirang, mille jooksul nad peavad vastuse andma ning enamik lahendusi ületavad piisavalt suurte andmete juures selle limiidi.

Enamasti eksisteeribki olümpiaadiülesannetel “jõumeetodiga” lahendus, mis töötab suhteliselt väikeste andmehulkade puhul, kuid võtab suuremate puhul liiga kaua aega, ning järkjärgult “kavalamad” lahendused, mis kasutavad efektiivsemaid algoritme või andmestruktuure. Et kavalamat lahendust realiseerida, on esiteks vaja vastava algoritmiga tuttav olla ning teiseks osata ära tunda, et vaja läheb just nimelt seda algoritmi.

Toon näitena ühe keskmise raskusega ülesande käesoleva aasta IOI-lt (täielik tekst siin).

Kividest sein koosneb tulpadest. Igal sammul võime kive seina sisse kas lisada või sealt eemaldada, andes ette a) lõigu, mitmendast tulbast mitmendani me kive lisame või eemaldame, ning b) kõrguse, milleni kive lisatakse või eemaldatakse. Kui lisamisel on mõnes tulbas juba rohkem kive, siis see tulp ei muutu. Samuti, kui eemaldamisel on mõnes tulbas juba vähem kive, siis seda me samuti ei puutu.

Andes ette käikude jada

1. lisa 1-8 kõrguseni 4

2. eemalda 4-9 kõrguseni 1

3. eemalda 3-6 kõrguseni 5

4. lisa 0-5 kõrguseni 3

5. lisa 2 kõrguseni 5

6. eemalda 6-7 kõrguseni 0,

saame järgmisel joonisel kujutatud seisud:

Ülesandeks on leida kivide arv pärast viimast sammu. Jõumeetodil igas tulbas kivide arvu meeles pidamine ja kokkulugemine on muidugi triviaalne, kuid selle eest sai suhteliselt vähe punkte. Maksimaalse suurusega testis oli seina pikkus 500 000 ning sammude arv 2 000 000, mida jõumeetod mõistliku ajaga kokku ei suuda lugeda.

Parim lahendus on kasutada lõikude puu nimelist andmestruktuuri, mis võimaldaks kõrguste meelespidamist ajaga, mis sõltub seina pikkusest logaritmiliselt, mitte lineaarselt. Võimalikud on ka mõned vahepealsed lahendused, mis annaks vahepealse arvu punkte.

Sõidust

Pärast mitmesugustest rõngastest läbihüppamist ja sõeltest läbipugemist kvalifitseerusid käesoleva aasta IOI võistkonda Oliver-Matis, Andres, Siim ja Simmo. Juhendajatena kaasas Ahto ja Targo (ehk mina). Üritus ise toimus seekord üsna kaugel, Taiwanis.

Mõned päevad pärast meie väljumist tulistati vähem kui 10 km kaugusel meie lennutrajektoorist alla sama tüüpi Malaisia reisilennuk, aga sellist asja ei osanud lahkumise ajal veel keegi ette kujutada. Simmo osales ka Rahvusvahelisel Matemaatikaolümpiaadil ning lendas kohale Kaplinnast, ühinedes meiega Dubais. Lend ise oli paras tüütus, koos ooteaegadega üle 24 tunni, mida leevendas natuke Emiraatide lennuliini superkena teenindus ning see, et seal saab lennu ajal oma elektroonikat laadida.

Saabudes seisime peaaegu terve piirivalvejärjekorra ära, kuid siis krabati meid sealt välja ning suunati läbi spetsiaalse diplomaatide ja lennukimeeskondade värava. Piirivalvur kohtles meid aga autentse Hiina põhjalikkusega. Poisil oli nimekiri erinevate passide turvaelementidest ning ta kontrollis need kõik ükshaaval üle, uurides ka spetsiaalse luubiga, kas passipildile kantud mikrokiri ütleb ikka õiget asja.

Teisel pool võtsid meid vastu juba korraldajad, kes tegelesid terve päeva erinevate lendudega saabuvate võistkondade konveieril läbitöötlemisega: lennujaam-buss-registreerimine-kaelakaardid (RFID-ga, seda piiksutati erinevatel üritustel)-giid-hotellijaotus. Sadade eri maailma nurkadest saabuvate kooliõpilaste juhatamine pole kõige lihtsam ülesanne, respekt siinkohal korraldajatele. Paistis ka, et ürituse eelarve pealt polnud kokku hoitud, kasvõi meie majutus oli südalinna Hyattis, kus meie ja Taipei 101 kõrghoone vahele jäi vaid järgmine kubistlik veidrus:

Sellistel olümpiaadidel on igale võistkonnale tavapäraselt ette nähtud giid, enamasti kohalik õpilane või üliõpilane. Meie poiste giid ütles, et tema nimi on Lilian, aga Facebookis kirjutab ta hoopis 林家萱 ja ütleb oma kooliks olevat 臺北市立大安高級工業職業學校.

Juhendajad ja võistlejad majutatakse eraldi, et vältida liigseid kontakte võistluse perioodil, nii et poisse nägime taas järgmisel päeval, harjutusvoorul. Võistlus toimub korraldajate poolt ettevalmistatud riistvaral ning hoolimata sellest, et analoogses formaadis võistlusi on juba pikka aega korraldatud, tekib vahel tõrkeid – kas ei taha mõni printer araabiakeelset fonti trükkida või ei kannata kohalik võrk testfailide korraga sadadesse arvutitesse kopeerimist välja. Harjutusvoor ongi viimane võimalus selliste probleemide ennetamiseks.

Järgnenud avatseremoonia demonstreeris järjekordset tahku kohalikust kultuurist. Kõik sõnavõtjad alustasid pikkade pöördumistega erinevate kohalviibijate poole, hoolitsedes, et keegi vahele ei jääks ega vales järjekorras ei tuleks. Esmajärjekorras nimetati muidugi aukülalist, kelleks oli Taiwani asepresident Wu Den-yih. Kui asepresident ise lavale astus, mängis orkester spetsiaalset tunnusmeloodiat ning lava igasse nelja nurka vudis portfelliga turvamees. Aukülaline kõneles pikalt hiina keeles, mis hiljem umbes 10x lühemalt leninlikus “õppida-õppida-õppida” stiilis kokku võeti.

Hierarhilisus torkas ühiskondlikes suhetes üleüldse silma, isegi kiirtoidukohtade personalid teevad hommikuti rivistuse, kus ülemus neile väikese kõne peab.

Võistlusest

Võistluspäevi on IOI-l kaks, nende vahel puhkepäev. Kummalgi päeval on viis tundi aega, et lahendada kolm ülesannet. Lahenduseks on programmikood, mis saadetakse veebiliidese kaudu automaatsele testimissüsteemile, mis omakorda ütleb, kui palju punkte sa selle eest said. Kui mingi testi vastus oli vale, siis selle detaile sa teada ei saa, aga öeldakse, kui lahendus ületas ajalimiidi. Ülesannetega saab tutvuda IOI ametlikul saidil.

Et minimiseerida ajavahemikku, mil ülesanded laiemalt teada on, avalikustatakse nad juhendajatele eelmise päeva õhtul. Järgneb pikk diskussioon, mis meenutab tähenärimise maailmameistrivõistlusi ning mille käigus tehakse tavaliselt mitmesuguseid sõnastuse parandamise ettepanekuid. Kui ülesanded on stabiliseerunud, saavad juhendajad need tõlkida, trükkida ning vastastikku põhjalikult üle lugeda, et võistlejatel järgmisel päeval võimalikult vähe segadust tekiks.Võistluseelne ettevalmistus kestab juhendajate jaoks tavapäraselt pikalt üle südaöö, lisades sinna juurde ajavahe ning asjaolu, et mõnel päeval algas programm jälle hommikul vara, olin mina enamiku esimestest päevadest üsna kapsas.

IOI ülesannete lahendamise edukus on paljus kinni harjutamises, mistõttu domineerivad tulemustes riigid, millel on pikk ja põhjalik ettevalmistusprogramm, eelkõige Hiina ja USA, nemad said seekord ka neli kuldmedalit. Lisaks said kaks kulda Austraalia, Venemaa, Bulgaaria, Iraan, Korea, Tai ning Singapur. Nendel riikidel, kelle ettevalmistuse võimalused väiksemaks jäävad, pääsevad paremate kohtade löögile tavaliselt üksikud superandekad võistlejad, kelle hulgas on omakorda tähed nagu Gennady Korotkevich Valgevenest, mitmekordne absoluutvõitja. Eesti läbi aegade parim on olnud Martin Pettai, kes võistles aastail 1999-2002. Kultuuritausta rolli illustreerib ka asjaolu, et esimesel päeval said maksimaalsed 300 punkti 5 võistlejat, kellest kolme perekonnanimed olid Wu (USA-st), Xu ja Yu (Hiinast). Zu nimelist võistlejat siiski ei olnud.

Kuna informaatikas on võimalik kasutada automaattestimist, on juhendajate töö võistluse järel mõneti lihtsam kui teistel aladel, aga see ei tähenda, et üldse midagi teha ei oleks. Kui probleemid tekivad, on enamasti asi testide disainis või võistlejale antavas tagasisides. Kui juhtub, et kellelegi raporteeriti võistluse ajal tema lahenduse eest mittekorrektne punktide arv, on ka apellatsioon kindel. Ja nagu öeldud, on informaatikaolümpiaadi koondisejuhendajate seas hulgaliselt tähenärimistšempioneid :) Kokkuvõttes on ka võistlusjärgselt pikad koosolekud garanteeritud.

Tulemuste osas tekkis mul peas hierarhia: kasvõi Eestis on hulk kooliõpilasi, mingi koorekiht neist käib olümpiaadidel. Eesti koondis rahvusvahelisteks võistlusteks on omakorda koorekiht selle eelmise koorekihi sees, seal on umbes võrreldav tasemevahe. Siis aga saame mõelda neist, kes saavad rahvusvaheliselt olümpiaadilt kuldmedali (ülemine 1/12 kõigist võistlejatest, Eestist on informaatikas selle saavutanud Martin Pettai 3 korda, Erik Laansoo ja Oleg Mürk ühe korra) – nemad on jällegi klass omaette. Järgmine kvanthüpe on võistlejad, kes saavad maksimaalse skoori. Sel aastal oli 600 punktiga tulemusi 3, vahel pole neid ühtegi. Ja nende seas oli omakorda poiss, kes peajagu teistest üle – Scott Wu USA võistkonnast (järgmisel pildil parempoolne) saavutas esimesel päeval maksimumpunktid kõigest 2 tunni ja 13 minuti järel, teisel päeval veidi enam kui 3 tunni järel. Kokku siis natuke üle poole kasutada olnud kümnest tunnist. Katsun tal silma peal hoida, huvitav oleks näha, mis temast tulevikus saab.

Punktidest veel: aegade jooksul parim Eesti võistleja saavutatud skoor on 680/700 (Martin Pettai, 2000), käesoleval aastal oli meie parim skoor 323/600.

Alates võistlusele eelnevast õhtust kuni lõpusignaalini kestis karantiin, mille jooksul võistlejatel ei tohtinud olla kontakti välismaailmaga, eriti juhendajatega, seepärast pole võistlusest ka pilte. Küll tegime pilte pärast tulemuste selgumist ja autasustamist. Seekord sai võistkonna parima tulemuse Oliver-Matis, kes küündis hõbemedalini – meie jaoks täitsa korralik resultaat.

Toidust

Esimese võistluspäeva õhtuks oli ette nähtud pidulik söögiüritus, kus kohaliku kombe kohaselt tuli inimesi toita, nii et seda nägu.

Söömaaeg oli korraldatud Taipei linnapea poolt, kes pidas alguses kõne sellest, kuidas Taipei on maailma parim ja me peaks kõik sinna elama tulema. Kõne toon kõlas, nagu iga lause lõpus oleks mitu hüüumärki. Taipeis saab tegeleda kõigi huvialadega!!! Ja meil pole praktiliselt üldse mingit kuritegevust!!! Ja meie elanikud on väga abivalmid ja juhatavad teid alati kohale!!! Viimane oli meie kogemuses täitsa tõsi, aga instruktsioon viis kommunikatsioonihäirete tõttu hoopis teise kohta.

Seejärel kanti aga kõik kümme söögikäiku üksteise järel ette. See “geoduck” pildil toodud menüüs pole muuseas mitte maapart, vaid hoopis üks mereloom. Üldse oli Taiwanis viibimine üks suur söömaorgia, sest kõik katsusid meid alatasa toita ja söök oli minu meelest ka päris hea. Krooni pani viimasel päeval meie giidi ema, kes kutsus meid terve kambaga ühte kohalikku fancysse restorani ning tellis meile nii kaua igasuguseid asju, kuni me lõpuks nutu äärel kinnitasime, et tõepoolest rohkem ei jaksa. Isegi suvalistes külakohtades, kus me pärast ametlikku osa omal käel käisime, kanti laud igasugust kraami täis.

Ahto katsus lisaks leida kohta, kus mingeid praetud ämblikke müüdaks, aga edutult, nii et ta pidi neid ise loodusest püüdma.

Taiwanist

Võistlusvälisel ajal korraldati meile mitmesuguseid ekskursioone, kuid siin põrkuvad korraldajad probleemi otsa, et atraktsioone, kuhu saaks korraga viissada inimest komandeerida, on üsna raske leida. Tavapärasteks sihtmärkideks sarnastel üritustel on vabaõhumuuseumid, loomaaiad ja lõbustuspargid, kuid olles neid elus juba üksjagu näinud, katsusime ka võimalikult palju omal käel ringi vaadata. Kuna iga päev sinnakanti ei satu, jäime pärast üritust ka paariks ekstra päevaks omal kulul kohalikke olusid uurima.

Taiwan, Portugali meresõitjate poolt nimetatud Ilha Formosa – ilus saar, on väga mägine, kuid samas roheline. Tüüpiliselt peaks seal alatasa troopilist vihma sadama, kuid meie kogemuses oli ilm enamasti selge, kuigi palav ja niiske.

Pindalalt 20% Eestist väiksem, aga 23 miljoni elanikuga saar on meie mõistes muidugi väga tihedalt asustatud.

Tänavapildis jääb silma eelkõige Jaapani mõju, valdav enamik autosid on Jaapanist, rongisüsteem on sealse eeskujuga ning üle on võetud muidki kultuuritehnilisi uuendusi.

Mõistagi ei puudunud ka mitmesugused “lost in translation” efektid:

Kaugeima ekskursiooni tegime Taroko rahvusparki, kuhu meie giidi ema ei lubanud meiega kaasa tulla, sest sõita tuli mingit mägiteed mööda.

Reaalselt oli tee täitsa korralik, mujal maailmas olen palju hullemal sõitnud, aga kohalikud paistsidki meiega võrreldes väga ettevaatlik rahvas olevat (välja arvatud rolleritega linnatänavail sõites). Näiteks oli seal tavaline, et veepargis kantakse päästevesti ning rahvuspargis mägede vahel kiivrit. Eriti pani aga kukalt kratsima silt hotellis, mis kohustas personali informeerima, kui sul peaks ükskõik milline haigus kallal olema.

Viimasel täielikult Taiwanis veedetud päeva lõpetuseks saime aga mälestuseks vaat sellised pildid. Ookeanilained olid jalustrabavad, nii visuaalses kui ka sõna otseses tähenduses.

Järgmise aasta olümpiaad toimub juba hoopis vastupidises kliimas, ookeanist peaaegu nii kaugel kui vähegi võimalik, Almatõ linnas Kasahstanis. Paras aeg harjutama hakkamiseks on just praegu :)

No responses yet