Suomen taitavimmat lukioikäiset ohjelmoijat kokoontuivat 3.2.2011 TKTL:lle Datatähden loppukilpailuun. Kilpailun aloitti esseeosuus aiheena identiteettivarkaudet. Tämän jälkeen kilpailijat saivat ratkaistavakseen kaksi haastavaa ohjelmointitehtävää.

Kilpailun voitti Jasse Lahdenperä (Oulun Lyseon lukio), toiseksi tuli Samuli Löf (Valkeakosken Tietotien lukio) ja kolmannen sijan vei Toni Hyvönen (Paimion lukio). Kilpailu oli tänä vuonna varsin tasainen, ja kärkikaksikon välillä oli vain yhden pisteen ero. (Tuloslista MAOLin sivuilla)

Datatähden osallistujista valitaan Suomen edustajat lukiolaisten kansainvälisiin ohjelmoinnin olympialaisiin. Tänä vuonna Itämeren alueen kilpailu pidetään Tanskassa ja maailmanlaajuinen kilpailu pidetään Thaimaassa.

Seuraavassa on toinen loppukilpailun ohjelmointitehtävistä. Osaisitko ratkaista sen? Kilpailussa vaadittiin ratkaisuidean lisäksi toimiva toteutus C:llä tai C++:lla.

"Suorakulmion muotoiselle peltoalueelle halutaan rakentaa suorakulmion muotoinen luistinrata. Peltoalue ja luistinrata muodostuvat neliöruuduista. Joissakin peltoalueen ruuduissa on kuitenkin puita, eikä niiden kohdalle voi rakentaa. Tee ohjelma, joka selvittää suurimman mahdollisen luistinradan pinta-alan peltoalueen kartan perusteella.

Peltoalueen koko on korkeintaan 5000x5000 ruutua ja puiden määrä on korkeintaan 100000. Ohjelman saa käyttää yhden testisyötteen käsittelyyn korkeintaan yhden sekunnin aikaa. (Tämä tarkoittaa käytännössä, että ohjelman aikavaativuuden tulisi olla O(nm+p), missä, n on peltoalueen korkeus, m on peltoalueen leveys ja p on puiden määrä.)"

Teksti: Antti Laaksonen