Datatähti 2009 -kilpailu on alkanut tänään:
http://www.cs.uta.fi/datatahti/
Kyseessä on peruskoulun ja lukion oppilaille tarkoitettu kilpailu, jonka ohjelmointitehtävät liittyvät algoritmeihin. Alkukilpailun tehtävät ratkaistaan kotona, ja ne täytyy palauttaa sähköpostilla 11.11.2008 mennessä. Näiden tehtävien perusteella parhaat osallistujat kutsutaan loppukilpailuun, joka pidetään Helsingin yliopistolla 23.1.2009.
Datatähteen kannattaa ehdottomasti osallistua, jos algoritmit kiinnostavat ja haluaa oppia niistä lisää. Jos tehtävät näyttävät aluksi vaikeilta, ei hätää: ne näyttävät aluksi kaikkien mielestä vaikeilta. Kilpailuissa ja myöhemmin pidettävillä leireillä pääsee tutustumaan nuoriin ohjelmoijiin ympäri Suomen, ja niissä oppii paljon kiinnostavia asioita, jotka tulisivat muuten vastaan vasta yliopiston syventävillä kursseilla. Lisäksi tiedossa on alan kirjallisuutta sekä matkoja ulkomaille kansainvälisten kilpailujen merkeissä.
Tervetuloa mukaan Datatähteen!
Itseäni kiinnostaisi kuulla hieman Antin kokemuksia kilpailusta. Olet ollut loppukilpailussa useita kertoja (olettaisin, en muista tarkalleen). Leirejä? Tämä on uutta minulle. Kuinka moni kilpailun osaanottajista pääsee leireille (loppukilpailuun päässeet)? Millainen itse loppukilpailutilanne on? Stooria! Ulkomaankilpailut?
itseä kiinnostais, mut noi haetut algoritmit kuulostaa siltä ettei oo meikäläisel mitään mahdollisuutta selvitä niistä.. ainakaan kun tuolla pyörii tuo 1 sekuntin suoritusaika sekä mitähä se oli 198(?) mb muistia.. -.-
edit: ainakin siis tälleen yhdellä lukemalla
Minusta taas tämän vuoden tehtävät vaikuttavat aikaisempia helpommilta. Kakkostehtävä on jo melkein valmiina. Haastavimmalta näytti kolmonen, mutta eiköhän tuokin alkukankeuden jälkeen jotenkin suju, tai näin ainakin toivon. Olisi kiva saada jotain aikaiseksi tämänkin kilpailun suhteen nyt, kun on viimeinen mahdollisuus osallistua. Kaksi aikaisempaa lukiovuotta on mennyt asenteella "kyllä mä ne tehtävät kerkeen tehdä, ei oo kiire" ja NAPS viimeinen palautuspäivä iski.
Itsekin kun katsoin niin ainakin eka algoritmitehtävä vaikutti sellaiselta viiden minuutin puserrukselta.. (Tosin lukioaikoina olisi voinut mennä hieman pidempään). Sanoisin että vaikka ei kilpailuun osallistuisikaan niin kannattaa silti kokeilla tehdä noita tehtäviä, ainakaan kaikki ei näytä kovin vaikeilta.
Vaikuttaapa helpolta. Noh, jos väkertäis noi vielä tässä illalla, kun ikäkin vielä riittänee.
Plääh, no ei se niin helppoo ollutkaan kun ensiks kuvittelin :D Eka nyt kuitenki tehty, kolmonen näyttää helpoimmalta ja tätä kakkosta olis hyvä miettiä yön yli.
Harmi kun en osaa sallittuja kieliä. :( Olisi muuten voinut jopa osallistuakkin.
Kokeilin kuitenkin huvin vuoksi Pythonilla, sillä ainakin kolmonen onnistui varsin helposti. Kolmonen vaikutti minun mielestä helpoimmalta, en tosin tiedä mitä kielikohtaisia ns. rajoituksia sallitut kielet aiheuttavat ja tekevät siitä siksi vaikeahkon.
trilog kirjoitti:
Harmi kun en osaa sallittuja kieliä.
C:n perusteiden opettelemiseen ei onneksi mene kauaa. Ehdit helposti oppia tarpeeksi ennen kilpailuajan päättymistä.
ByteMan kirjoitti:
tuolla pyörii tuo 1 sekuntin suoritusaika sekä mitähä se oli 198(?) mb muistia.. -.-
Rajat voisivat minusta olla paljon tiukemmatkin. Ainakaan ensimmäisessä ja kolmannessa tehtävässä (toista en ole vielä ehtinyt miettiä paljoa) kunnollinen algoritmi ja toteutus ei tarvitse läheskään noin paljoa aikaa eikä muistia patologisimmissakaan tapauksissa. Kohtalaisen huonollakin ratkaisulla voi siis saada pisteitä.
Vielä kun olisi kirjoilla jossain lukiossa niin voisi osallistua. >_>
TeeVee kirjoitti:
Itseäni kiinnostaisi kuulla hieman Antin kokemuksia kilpailusta.
Loppukilpailu muistuttaa paljon alkukilpailua, ainoastaan tehtävät pitää ratkaista muutaman tunnin kuluessa valvotuissa oloissa. Loppukilpailu alkaa aamulla kokoontumisella yliopiston aulassa. Päivään kuuluu tehtävien ratkomista yliopiston tietokoneluokassa, syömistä yliopiston ravintolassa ja vapaa-aikaa, jolloin voi vaikkapa tutustua muihin kilpailijoihin. Lopuksi illansuussa koittaa jännittävin hetki: tulokset paljastetaan ja palkinnot jaetaan.
Ohjelmointileirejä pidetään kaksi, yksi keväällä ja yksi kesällä. Ensimmäiselle leirille on viime aikoina valittu noin kahdeksan osallistujaa tärkeimpänä valintaperusteena ohjelmointitehtävien ratkaisut alku- ja loppukilpailussa. Leireillä opitaan algoritmien ohjelmointia luentoja seuraamalla ja tehtäviä ratkomalla. Leireillä myös pidetään harjoituskilpailuja. Leirit järjestetään yliopistolla ja niiden kesto on yleensä kolme tai neljä päivää.
Kansainväliset kilpailut ovat BOI (Baltic Olympiad in Informatics) ja IOI (International Olympiad in Informatics). BOI:n osallistujat tulevat Itämeren alueelta ja IOI:n osallistujat maailman joka kolkasta. Jokainen maa voi lähettää BOI:hin kuusihenkisen ja IOI:hin nelihenkisen joukkueen. Tänä vuonna BOI oli Puolassa ja IOI Egyptissä, ja Suomelle tuli menestystä molemmissa. BOI ja IOI kestävät kumpikin noin viikon, ja niihin mahtuu toki paljon muutakin ohjelmaa kuin pelkkää ohjelmointia.
Kattotaan jos jotaki saisin aikaseks. C++:lla kai lähetään liikenteeseen :D Mutta tuskinpa vaan saan.
Ainakin silti tuota kakkosta lukiessani mietin että sopisikohan siihen A*-algoritmin soveltaminen. Ja kolmonen vaikutti kaikista helpoimmalta. Ykkönen taas vaikein, ku en keksi miten saisi järkevästi käytyä läpi kaikki mahdolliset järjestykset. Sisäkkäisiä forlooppeja? Rekursiivisia funktiota? Mjoo :D
Niin ja saako siellä loppukilpailussa käyttää googlea? :D
temu92 kirjoitti:
Niin ja saako siellä loppukilpailussa käyttää googlea? :D
Esseeosiossa saa käyttää verkko vapaasti kunhan ei käytä mitään interaktiivisia keskustelusysteemejä.
Ohjelmointiosion aikana on kaikki Internetin selaaminen kiellettyä, mutta koneilta on ainakin tähän mennessä aina löytynyt C++:n standardikirjaston referenssi.
Nyt on kaksi ensimmäistä tehtävää valmiina. Kakkonen oli aika paha. En tosin käyttäny mitään valmiita algoritmeja ts. heitin koko homman omasta päästä. :-)
edit: Epäilen tosin ohjelmani suorituskykyä kun m ja n lähestyy sitä kolmeatuhatta.
Itselläni alkaa olla 1 ja 3 valmiina. Ykkönen oli ehdottomasti helpoin, kun sitä ei tarvitse pahemmin optimoidakkaan. Kolmonen oli taas aikas vaikea ja ratkaisun keksi suht helposti, mutta taas optimointi siinä on haastavaa. Tällä hetkellä 1 - 10^10 väliltä hakeminen kestää tuon vähän alle sekunnin ja optimointi ideat alkaa loppu.
Kakkonen tuntuu vähän vaikealta kun ei ole tultu pohdittua tälläisiä pathfinding-algoritmejä. Eiköhän sekin onnitu pienen ponnistelun jälkeen.
Ensimmäinen on triviaali tehtävä (muistakaa katsoa syötteiden kokorajat!), ja toinen on varsin tyypillinen tietyillä ehdoilla optimaalisen reitin etsintä. Kolmannen haaste taas on luultavasti tehokkaan algoritmin idean kaksiminen ja toteuttaminen oikein.
Hienoa, että kilpailun painopiste on tällä kertaa hieman enemmän ohjelmoinnin puolella.
Teinpä nuo aivojumpaksi, mutta lukiorajoitus ei ole reilu. Olipahan tekemistä. Kielenä tietenkin ensirakkaus, C. <3 Kannattaa tosiaan tehdä, vaikkei osallistua voisikaan, käyhän nuo hyvästä harjoituksesta :) Hyvää harjoitusta optimoinnista ja ongelmanratkonnasta.
Ja kielien pähkäilijiöille, niin esim. C-kielen perusteet ei ole vaikeita, kunhan ohjelmointi yleensä on halinnassa.
Lukiorajoitus johtunee lähinnä kansainvälisten jatkokilpailujen vaatimuksista, ja toki myös siitä, että eihän MAOLin muutkaan lukiokisat ole avoimia kaikille.
GoldenDragon kirjoitti:
Teinpä nuo aivojumpaksi, mutta lukiorajoitus ei ole reilu.
Onhan se reilu sikäli, ettei ole järkeä päästää lukion ohittaneita ihmisiä (esimerkiksi yliopistoista) osallistumaan. Siitä olen kuitenkin samaa mieltä, että on melko perusteetonta rajata ammattikoulut kilpailun ulkopuolelle. Peruskoululaiset saavat tiettävästi osallistua, erillinen sarja vain lakkautettiin osallistujapulan vuoksi. Antti osannee kertoa, onko yhä näin.
Toisen tehtävän ratkaisu toimii 1,2–1,6 sekunnissa, ensimmäisen ja kolmannen jopa mittausta nopeammin. (Hirveän suuri vaihtelu tuossa eri ajokerroilla, osaako joku selittää tämän? Ajat ovat aivan normaaleja user-prosessoriaikoja ja syöte on tietenkin aina sama.)
Tehtäviä tehdessä kannattaa muistaa, että usein arvostelussa (testisyötteissä) on jonkin verran pieniä testitapauksia, joista voi hyvin saada pisteitä hitaallakin algoritmilla. Siis esimerkiksi kolmannesta tehtävästä saa todennäköisesti kohtuullisesti pisteitä, jos selviää edes miljoonan luvun lukuväleistä.
Kolmannesta tehtävästä tuli muuten ensi lukemalla mieleen Lukujenvihaaja. :)
Tuo 3 tehtävä on kyllä mahdoton. Ehkä sen saisi toimimaan tarpeeksi nopeaa jollain supertietokoneella, mutta tuolla testi koneella ei onnistu. Ensimmäinen tehtävä oli kyllä selvästi helpoin. Vielä 2 pitäis tehdä heti kun on aikaa.
Metabolix kirjoitti:
Peruskoululaiset saavat tiettävästi osallistua, erillinen sarja vain lakkautettiin osallistujapulan vuoksi. Antti osannee kertoa, onko yhä näin.
Kyllä, peruskoululaiset saavat edelleen osallistua Datatähteen. Ja tämä myös kannattaa, sillä jos jo peruskouluiässä osallistuu kilpailuun, on monta vuotta aikaa kehittyä todella taitavaksi.
Tehtävään 3 sain mielestäni hyvän idean, mutta käytännön toteutus ontuu vielä pahasti.
Pitää katsoa, että minkälaisia tehtäviä on ensi vuonna, koska en keksi ratkaisua tehtävään 2 :(
Jalmari91: jos teet edes huononkin ratkaisun tehtävään 2, ja muut tehtävät on tehty oikein ja tehokkaasti, uskallan väittää että pääset alkukilpailusta jatkoon.
Kakkostehtävä näyttää kyllä vaikeimmalta. Jonkinlainen ajatus siitä olisi, mutta vielä kun tietäisi miten sen toteuttaisi. Ykköstehtävän vastauksen laskeminen kestää huimat 7 sekunnin sadasosaa. Kolmosessa en saa laskettu sekunissa kuin välin 1 - 60000000 ja tietenkin alla on paljon nopeampi kone kuin siellä.
Nyt vasta huomasin, että on neljäskin tehtävä. Ei sitä minun mielestäni pari päivää sitten ollut...
Ei kai siellä ohjelmointitehtäviä edelleenkään ole kuin ne kolme?
Sitä esseetehtävää tarkoitin. Voi olla, että en vain huomannut sitä ja hyppäsin suoraan ohjelmointitehtäviin.
Nyt on ohjelmointitehtävät tehty. Ykkönen ja kolmonen menee reippaasti alle sekunnin suurimmillakin syötteillä :) Kumpa tuloksetkin sattuis vielä olemaan oikeat (testailtu on, mutta jotain jää aina huomaamatta). Kakkostehtävän algoritmini on vähän tyhmä ja varmaan hidas, mutta eiköhän sillä silti pari pistettä irtoa.
Vielä pitäs se essee raapustella...
Voikos tähän kisaan osallistua ihan itsenäisesti vai pitääkö mennä jonkin tietotekniikan opettajan kautta?
petrinm kirjoitti:
Voikos tähän kisaan osallistua ihan itsenäisesti vai pitääkö mennä jonkin tietotekniikan opettajan kautta?
Itsenäisesti osallistutaan.
Osallistumiseen riittää, että toimitat ilmoittautumistiedot ja tehtävien vastaukset sivujen ohjeiden mukaan. Opettajalle tai kenellekään muullekaan ei tarvitse kertoa asiasta.
Silloin kun minä olin lukiossa meillä oli vain höyrykoneenrakennuskilpailuja, mutta silti osallistuisin tämän kilpailun nipotussarjaan.
ohje kirjoitti:
Ohjelmointikielissä C ja C++ pääohjelman main suorituksen pitää päättyä lauseeseen return 0; (Pascal-kääntäjä huolehtii tästä puolestasi).
Myös standardia noudattava C++-kääntäjä huolehtii tästä puolestasi. Jos he sakottavat joltakulta pisteitä pois tämän takia, väärin perustein menee.
Itse kyllä lisään sen returnin sinne. Ei tarvitse kuunnella valivalia ihmisiltä, jotka eivät ole RTFM.
end section nipotus :)
Hupimielellä kehitelty teoria: Siellä on joku Pascal-fanaatikko järjestäjänä ja pitää keksiä jotain hyvää sanottavaa Pascalista.
Selittäisi senkin, miksi siellä on nykyaikana vaihtoehtoina juuri C, C++ ja Pascal.
Onko asia nyt niin, että huomenna tehtäviä saa vielä palauttaa, vai onko palautus tehtävä _ennen_ huomista? Sivuilla nimittäin ilmoitetaan alkukilpailun ajaksi 28.10. - 11.11.2008, ja jos kerran 28. päivänä sai tehdä tehtäviä, niin miksei vielä huomennakin? :)
Grez kirjoitti:
Selittäisi senkin, miksi siellä on nykyaikana vaihtoehtoina juuri C, C++ ja Pascal.
Yksi syy kielten valintaan on, että samoja kieliä saa käyttää kansainvälisissä kilpailuissa.
tgunner kirjoitti:
Onko asia nyt niin, että huomenna tehtäviä saa vielä palauttaa, vai onko palautus tehtävä _ennen_ huomista?
Tehtävät täytyy palauttaa viimeistään 11.11. eli huomenna.
Grez: ei ole näin. Syynä vaan on se, että kansainvälisissä tietotekniikkaolympialaisissa sallitut kielet ovat juuri C, C++ ja Pascal. Pascal lienee jäänyt reliikiksi näihin kisoihin, koska monet opettajat osaavat juuri Pascalia eri maissa, joten ohjelmointiopetus tapahtuu usein juuri Pascaliksi.
Huh, nyt alkaa olla softat kasassa, tosin kakkosessa riittää vielä hiomista. Pari bugia korjattu vielä viime hetkillä kolmosesta.
Noniin, miltä tehtävät tuntui? Kiinnostaisi kuulla, että miten oikeasti tiukan standardisti suuria lukuja käsitellään? Siis suurempia kuin C++:n long int (long long kääntyy mutta ei liene tiukinta standardia?)?
Kyllä long longia saa käyttää. Koodia ei käännetä -pedantic-flagilla, kuten FAQ:ssakin sanotaan.
Laitinen kirjoitti:
Kyllä long longia saa käyttää. Koodia ei käännetä -pedantic-flagilla, kuten FAQ:ssakin sanotaan.
Taisin sanoa viestissäni että long long kääntyy? Nyt vaan kiinnostaisi että miten homma tapahtuu stringien avulla... Kyllähän itsekin käytin long longia, mutta uteliaisuuttani kysyin.
int64_t on ihan yhtä hyväksytty/ei-hyväksytty kuin long long -tyyppikin.
Kummatkin ovat osa C99:ä ja gcc ja g++ hyväksyvät ne, mutta ne eivät kuulu C++98-standardiin.
No eihän tuossa kisassa mitään standardia kysytä, vaan algoritmia joka annetussa ympäristössä annetuilla kielillä ratkaisee annetun ongelman. Tällöin tietenkin käytetään C++:n long long:ia. Jos haluat käsitellä "tiukan standardisti" suuria lukuja (jossa siis edelleenkään ei ole mitään järkeä), niin käytetään yleensä kyllä taulukoita, joihin laskutoimitukset toteutetaan sitten itse käsin, esim. allekainlaskuilla.
Enpä saa tuohon enää osallistua, mutta kirjoittelin ratkaisut huvikseni.
C:n vuosimalli C99 sisältää long long -tyypin, C++ ei vielä. Tätä tarvittiin vain 3. tehtävässä, jossa taas C++ ei tuonut nähdäkseni mitään etua, joten kirjoitin ratkaisuni puhtaalla C:llä. GCC kuitenkin varoitteli silti, ettei printf:n ja scanf:n formaatti %Lu kuulu standardiin, joten tein omat luku- ja tulostusfunktiot, jotka tietenkin toimivat yksinkertaisesti kerto- ja jakolaskun voimin. Jos omaa lukujärjestelmää kaipaa, niin käytännössähän silloin täytyy jonkinlainen allekkainlasku toteuttaa eli lähinnä ohjelmoida "kymmenylitys". Esimerkiksi kahden 16-bittisen luvun kertolaskun tulos mahtuu aina 32-bittiseen muuttujaan, joten neljästä tällaisesta saa helposti 64-bittisen luvun, jossa on neljä "numeroa" ja jolla voi turvallisesti laskea.
Ensimmäinen tehtävä on triviaali ja ratkeaa noissa rajoissa (20 ohjelmoijaa) helposti rekursiolla, jokainen joko menee tai ei mene hissillä ja tapoja löytyy yksi lisää aina, kun kaikki ovat menneet ja massa ei ylittynyt. Aikavaatimus on O(2n), missä n on ohjelmoijien määrä. On mahdollista toteuttaa myös algoritmi, joka toimii ajassa O(n*m), missä m on suurin sallittu massa. Tätäkin voi vielä pienillä syötteillä hieman optimoida, mutta merkitys on pahimmassa tapauksessa hyvin marginaalinen ja luultavasti mutkikkaampi toteutus lopulta aiheuttaa vain hidastumista.
int rek(int m_nyt, int i) {
if (m_nyt > m_max) return 0;
if (i == ohjelmoijia) return 1;
return rek(m_nyt, i + 1) + rek(m_nyt + m[i], i + 1);
}Toinen tehtävä onnistuu eräänlaisella leveyshaulla (BFS), jonka aikavaatimus on siis O(w*h) eli suoraan verrannollinen ruutujen määrään. Kun matka viereiseen vapaaseen ruutuun on nolla ja aidalliseen yksi, "lyhin" reitti on se, jolla on vähiten aitaa. Reitin saa tulostettua jälkikäteen vaikkapa kulkemalla sen lopusta alkuun eli siirtymällä aina ruutuun, johon mennessä oli (a) kaadettu vähemmän pensaita tai (b) kaadettu yhtä monta pensasta mutta kuljettu lyhyempi matka. Tätä varten leveyshaussa voi pitää kirjaa myös todellisesta ruutumäärästä.
Kolmas tehtävä ratkeaa logaritmisessa ajassa (O(log(n))), mutta ratkaisu on liian epätriviaali selitettäväksi selkeästi yhdeltä yöllä. ;) Joka tapauksessa tehtävä on selvästi Lukujenvihaajan ilkeä isoveli, ratkaisumalli on aivan sama mutta mutkia kaksi enemmän.
Erityyppisiä sokkelotehtäviä on ollut Datatähdessä aika usein. Miten vastaavia graafialgoritmeja voisi harjoitella ja mistä lähteä liikkeelle?
TeeVee kirjoitti:
Miten vastaavia graafialgoritmeja voisi harjoitella ja mistä lähteä liikkeelle?
Aivan ensiksi kannattaa tutustua syyvyyshakuun (DFS, depth-first search) ja leveyshakuun (BFS, breadth-first search) ja niiden hyviin ja huonoihin puoliin. Kumpikaan ei yleensä esiinny tehtävissä aivan sellaisenaan, mutta monet edistyneemmät hakualgoritmit (mm. Dijkstran algoritmi ja A*) pohjautuvat tavallaan BFS:ään. Järkeä joutuu joka tapauksessa käyttämään tehtäväkohtaisestikin.
DFS ja BFS ovat ruudukkojen perusalgoritmeja, ja kun mukaan tuodaan jotain erikoisempaa kuten tässä pensaat, täytyy soveltaa hieman Dijkstran algoritmin kaltaista periaatetta eli valita jäljellä olevista ruuduista aina se, johon on ollut lyhin matka (vähiten pensaita). A* on tietyssä mielessä vain lisäys tähän: arvioidaankin, mistä voisi tulla lyhin ratkaisu, ja jatketaan siitä. Näitä muutamaa perusalgoritmia soveltamalla ja muuntelemalla pääseekin jo aika pitkälle Datatähden tehtävissä, ja esimerkiksi Dijkstran algoritmin keksiminen itse ei ole vaikeaa, jos vain sattuu kohdalle sopiva tehtävä, joka hyvin johdattaa oivaltamaan idean.
Hyviä harjoituksia ovat ensiksi tavallisen sokkelon ratkaiseminen ja sitten erikoisominaisuuksien keksiminen sokkeloon. Mikä on paras reitti sokkelon läpi, kun ruudusta saa pisteitä sen lukuarvon verran (esim. -10–10)? Entä jos ruuduista saa kaksia eri pisteitä, joiden erotus pitää saada mahdollisimman lähelle nollaa? (Jaa, mitenhän tuo jälkimmäinen muuten onnistuisikaan... :D) Tehtäviä voi aina keksiä lisää, testisyötteitä voi generoida satunnaisesti, ja yleensä tehtäviin on myös jokin hidas mutta varma ratkaisu, jolloin tulosten tarkistaminenkin onnistuu omin käsin.
Jos tehtävät tuntuvat liian tylsiltä, voi aina kehittää niihin sopivan taustatarinan. ;) "Pirjolla on puutarha, jossa kasvaa omena- ja päärynäpuita. Lisäksi puutarhassa asuu suuria etanoita, joita Pirjo pelkää kovasti."
Aihe on jo aika vanha, joten et voi enää vastata siihen.