Tänään alkaa peruskoulun ja lukion oppilaille tarkoitettu ohjelmointikilpailu Datatähti 2008:
http://www.cs.uta.fi/datatahti/
Alkukilpailussa tehtävät ratkaistaan kotona, ja kilpailuaika on 30.10. - 13.11. Loppukilpailu järjestetään Helsingin yliopistolla 31.1.2008. Kilpailun parhaat pääsevät edelleen valmennukseen Tampereen yliopistolle, ja valmennettavista valitaan joukkueet kansainvälisiin ohjelmoinnin olympialaisiin (BOI ja IOI).
Tässä vielä ensikertalaisille muutamia neuvoja ohjelmointitehtäviin:
1. Tehtävien ratkaisuja kannattaa ensin miettiä rauhassa kynällä ja paperilla. Usein on hyödyllistä hahmotella käsin tehtävän yksinkertaisia tapauksia ja etsiä niistä säännöllisyyksiä. Vasta sitten, kun ohjelman toiminta alkaa olla selvillä, on aika siirtyä tietokoneelle.
2. Tehtävissä ei tarvitse mitään ohjelmointikielten erityisominaisuuksia. Jos osaa käyttää muuttujia, taulukoita, ehtoja, silmukoita ja aliohjelmia, osaa oikeastaan kaiken tarvittavan.
3. Tärkeitä tietoja ovat, kuinka suuria syötteitä ohjelman täytyy käsitellä ja kuinka paljon aikaa ja muistia se saa kuluttaa. Nyrkkisääntö on "miljoona on vähän", eli jos ohjelma tekee jonkin yksinkertaisen asian miljoona kertaa, siihen ei kulu kovin paljon aikaa.
4. Ei kannata masentua, vaikka tehtävän ratkaisua ei keksisi viidessä minuutissa. Usein tehtävää täytyy miettiä tunteja, joskus jopa päiviä, ennen kuin siihen löytää kelvollisen ratkaisun.
Datatähteen osallistumalla voi oppia todella paljon ohjelmoinnista. Menestystä kilpailuun!
Hienoa, meikäläisen varmaan paras mahis päästä fiksuun yliopistoon :)
Ellei sitten tietojenkäsittelytiede ole harvinaisen epätungoksessa..
Olipa tällä kertaa yllättävän helpot koodaustehtävät. Molempiin sain yhdellä istumalla toimivan, vaikkakaan ei ehkä vielä täysin optimoidun, ohjelman rustattua. Verrattuna edellisten vuosien maze ym. tehtäviin melko helppoa. Eikun sitten vääntämään jotain projektinhallintasoftista ja tietomurroista.
Yllättävän helpolta tuntui verrattuna viime vuoden minigolf tekoälyyn...
Toisaalta tuo 32M merkin yläraja (@tehtävä 2) on iso...
Molempiin on jo toimivat ratkaisut :)
Helppoja? Mitenhän tuo ohjelma pitäisi puristaa sekunnin aikarajan sisään, kun ensimmäisessä tehtävässä jo kaikkien 32 miljoonan luvun lukeminen taulukkoon kestää vaatimattomat 8 sekuntia normaalilla fscanf:llä? Ei se testikone ihan niin paljon tehokkaampi voi olla.
Tällä kertaa on taidettu panostaa siihen, että tehtäviin on helppo tehdä hidas ratkaisu ja vaikeampi tehdä oikeasti kunnollinen.
Yhdyn Metabolixin väittämään. Itse olen vasta saanut todella hitaat versiot valmiiksi, mutta nopeuttamiseen en ole keksinyt vielä mitään. Onneksi on aikaa, ja voihan niihin teoriapuolenkin tehtäviin kokeilla luottaa...
Kuin myös... 1. tehtävän yläraja taitaa olla täysin utopistinen ja pisteitä jaetaan senperusteella miten lähelle sitä päästään. Käytännössä prosessoitava lisääntyy melkeen suoraan verrannollisesti N:nän ja M:män suhteen.
Jokainen voinee päätellä että 32000000*32000 on iso luku...
Ensimmäisen tehtävän sain sittenkin puristettua alle 1.4 sekuntiin (kummia konsteja käytössä). Täytyy vielä ihmetellä, jos jostain saisi pari millisekuntia pois, ja toivoa, että siitä tehokkaammasta prosessorista saa sitten vielä vähän etua irti. Toiseenkin tehtävään on algoritmin nimi tiedossa, kun vain osaisi vielä koodata sen ja optimoida noiden rajojen sisään.
Tietääkseni tiedoston lukemiseen kestävää aikaa ei oteta huomioon tehtävän suoritusaikaan. Siksi ensimmäinen kyllä lähtee 32M luvullakin alle sekunnin, mutta palindromitehtävä ei kyllä lähde millään jos pisin on jotain 7 tms.
Käsittääkseni kyllä lukemiseenkin mennyt aika lasketaan. En tiedä tarkempia detaileja, mutta ainakin itselläni tuo "ulimit -t 1"-komento aiheutti ohjelman kuoleman, kun time-komennon mukaan real timeä oli kulunut 1s ja user timeä vasta 0,7s.
Näin ollen ~0,25s katoaa väkisinkin ensimmäisessä tehtävässä käytettävissä olevasta ajasta.
Kyllä sen ekan tehtävän kaikesta huolimatta sai alle sekuntiin nysvättyä, vaikka ainakin omalla koodillani syötteen luku jätti itse algoritmille alle puoli sekuntia aikaa.
edit: Testailin ulimittia uudelleen, eikä se kyllä real-timeakaan laske. Olisiko user+sys? Sen ei pitäisi silti muuttaa sitä, että tiedostonlukuaika sisältyy utimen laskuihin.
SHSHSH kirjoitti:
Tietääkseni tiedoston lukemiseen kestävää aikaa ei oteta huomioon tehtävän suoritusaikaan.
Järjestelmäkutsuihin mennyttä aikaa ei lasketa, eli datan lukemisesta kovalevyltä muistiin ei oteta aikaa. Sen sijaan kaikki muu fscanf-funktiossa tapahtuva (itse kutsu, formaatin parsiminen, datan parsiminen tekstistä luvuksi jne.) kuuluu ohjelman suoritusaikaan. Kyseessä on siis Linuxin time-komennolla saatava user-aika.
Itse taidan olla liian vanha osallistuakseni kilpailuun (vai onko tuossa jokin avoinkin sarja?) mutta ihmettelen kyllä, että ohjeiden perusteella tuolta ei saa koodia lähetettäessä mitään palautetta että kääntyykö se edes. Siis onhan tuossa toki kerrottu jossain määrin ympäristö, missä se käännetään, mutta ei kaikilla välttämättä ole mahdollista testata ohjelmaa juuri täsmälleen samanlaisessa ympäristössä.
Grezin kommentteihin:
Ympäristö ei vaikuta koodin kääntymiseen, kun voidaan olettaa, että se tukee täysin standardia. Säännöissähän kehotetaan käyttämään "kielen peruspiirteitä" eli standardinmukaista koodia. Mitään sellaisia ihmeitä noissa ei tarvita, etteivät tavalliset muuttujat, rakenteet, funktiot, ehtolauseet ja silmukat riittäisi. Kuitenkin ainakin edellinen professori ilmoitti jopa koodin aiheuttamista varoituksista.
No siis lähinnä ajoin takaa sitä, että jos tekee jonkun typerän pikkumokan, niin että kääntyminen toimii omalla koneella mutta kosahtaa kilpailuympäristössä, niin se voisi olla melko kohtuutonta jos siitä saisi tietää vasta tulosten julkistuksessa. Toki jos virheistä ja jopa varoituksista tulee palautetta, niin sittenhän ongelmaa ei ole.
Vastaukset lähetetty eteenpäin, nyt sitten vaan odotellaan...
Lähetin vastaukset puoli tuntia ennen deadlineä :/. 32 megan satunnaissyötteellä palindromitehtävä runsaat 0.7s, mutta ykköstehtävään en ehtinyt tehdä tarpeeksi nopeaa algoritmiä. Ainakin 16000 rivin syöte meni alle sekuntiin, mutta ei pääse kyllä lähellekään maksimia. Esseistä tuli yhteensä noin 650 sanaa. Pitää toivoa parasta :)
Miten moni putkis osallistui? Päivölästä ("Valkeakosken lukio") osallistui tänä vuonna jopa kahdeksan tyyppiä, joista aika monella on suhteellisen hyvät mahkut loppukilpailuun.
Tekikö kukaan Javalla?
Niin, kuinka moni osallistui ja millaisia ratkaisuja saitte tehtäviin?
Tänä vuonna tehtävät olivat minusta mukavan selkeät ja kiinnostavat. Molempiin tehtäviin sai helposti yksinkertaisen toimivan ratkaisun, mutta riittävän nopean ohjelman laatimiseksi joutui todella pohtimaan asioita. 32 miljoonan merkin syötteet eivät ole nimittäin mikään leikin asia.
Kauppatehtävän perusratkaisu toimii O(n^2)-ajassa, mutta tehtävää tarkemmin miettimällä sopivan aputaulukon avulla ratkaisun saa O(n)-aikaan. Tässä tehtävässä syötteen lukeminen rivakasti on oma lukunsa, niin kuin Metabolix mainitsi. Tämä on kilpailuissa aika poikkeuksellista, koska yleensä tiedoston käsittelyn toteutukseen ei tarvitse uhrata lainkaan huomiota.
Palindromitehtävä on petollinen, sillä jos ohjelmaa kokeilee satunnaisella merkkijonolla, siinä tuskin on kovin pitkää palindromia ja moni ratkaisu toimii nopeasti. Mutta jos syötteenä onkin vaikka merkkijono, jossa lukee miljoona kertaa "saippuakauppias", ohjelmalle saattaa käydä todella huonosti.
Palindromeja voi etsiä tutkimalla merkkijonon kaikkia osamerkkijonoja, jolloin aikavaativuus on O(n^3), tai ovelammin ottamalla jokainen merkki vuorollaan palindromin keskikohdaksi ja tarkistamalla, kuinka pitkälle voidaan edetä kumpaankin suuntaan, jolloin aikavaativuus on O(n^2).
Yksi lähestymistapa on muodostaa tässäkin tehtävässä aputaulukko, jonka avulla mille tahansa osamerkkijonolle voidaan laskea hajautusarvo vakioajassa. Tämän ansiosta osamerkkijonoja tutkiva ratkaisu nopeutuu O(n^2)-aikaan, mutta vielä parempaan tulokseen pääsee etsimällä oikean pituista palindromia binäärihaulla. Tällöin aikavaativuus on O(nlogn), ja ohjelma alkaa jo olla melko nopea.
Huhujen mukaan palindromitehtävään on olemassa myös O(n)-ratkaisu, jossa avainsanana on tietorakenne suffiksipuu (suffix tree) ja sen muodostaminen nopeasti. Tämä reitti tuntuu kuitenkin aika hankalalta, erityisesti puun muodostaminen O(n)-ajassa, joten kenties O(n)-ratkaisuun voi päästä muutenkin. Tietääkö kukaan miten?
Vastatakseni vielä keskusteluun suoritinajan mittaamisesta: http://www.cs.uta.fi/datatahti/faq.html (kysymys 11).
edit: Jos ette oikeasti jaksa klikata: järjestelmäaika lasketaan suoritusaikaan mukaan.
En juuri kuluttanut aikaa näiden pohtimiseen.
Ensimmäiseen tehtävään O(n)-ratkaisun tekeminen oli helppoa, mutta en keksi siihen oikein mitään optimointia enää ja silti aikaa kuluu enimmillään 1,3 + 0,3, kun nyt ilmeisesti myös järjestelmäaika lasketaan. En käsitä, miten malliratkaisu voi toimia kymmenen kertaa nopeammin.
Palindromitehtävä jäi kovin heikoille, suffiksipuuta en saanut aikaan noissa tilavarauksissa, joten päädyin ratkaisuun, joka on pahimmillaan O(n^2) ja kertoimeltaan Antin tarjoamaan keskikohtien kokeilua raskaampi mutta usein kuitenkin paljon nopeampi, esimerkiksi palindromien pituuksilla 1 ja n toiminta-aika on O(n) ja satunnaissyötteelläkin yllättävän hyvä, kun pisin palindromi sattui olemaan yhdeksän merkin mittainen. Pahin tapaus on sellainen, että syötteessä on tasan yksi eriävä merkki jossain mahdollisimman kaukana päädyistä ja keskeltä (en osaa näin heti sanoa, onko 1/3 vai 1/4 pahempi). Ratkaisu olisi mahdollista optimoida toimimaan tässäkin tapauksessa nopeasti jonkinlaisella RLE-koodauksella, mutta tietenkin muotoa abaXababab-olevat merkkijonot eivät tästä parane, vaikka niistä tarvitseekin tarkistaa vain joka toinen vaihtoehto (a-a ja b-b).
Esseistä kirjoitin vain jälkimmäisen, kun olen näin laiska.
Antti Laaksonen kirjoitti:
Mutta vielä parempaan tulokseen pääsee etsimällä oikean pituista palindromia binäärihaulla.
Voisitko kertoa tästä vielä lisää?
Antti Laaksonen kirjoitti:
Huhujen mukaan palindromitehtävään on olemassa myös O(n)-ratkaisu, jossa avainsanana on tietorakenne suffiksipuu (suffix tree) ja sen muodostaminen nopeasti.
Tästä oli vaikea löytää selkeää selostusta, mutta lopulta jokeenkin ymmärsin ajatuksen, eikä se vaikuttanut lainkaan mahdottomalta. Vastaan tulee kuitenkin muistiraja: Tehtävässä on 6n tavua muistia, mutta suffiksipuu vaatii pahimmillaan 2n kaarta. Lisäksi tietystä kohti lähtevien kaarten määrää ei voi ennalta tietää, mikä vielä hieman hankaloittaa optimaalista toteutusta.
Metabolix kirjoitti:
Ratkaisu olisi mahdollista optimoida toimimaan tässäkin tapauksessa nopeasti jonkinlaisella RLE-koodauksella, - -
Merkkijonon pakkaus ennen palindromin etsimistä onkin kekseliäs idea, eipä olisi tullut minulle mieleen.
Metabolix kirjoitti:
Antti Laaksonen kirjoitti:
Mutta vielä parempaan tulokseen pääsee etsimällä oikean pituista palindromia binäärihaulla.
Voisitko kertoa tästä vielä lisää?
Mainitsemallani hajautustempulla pystyy tarkastamaan O(1)-ajassa, ovatko kaksi osamerkkijonoa samat. Nyt jos palindromin pituus on tiedossa, se löytyy merkkijonosta O(n)-ajassa. Binäärihaun avulla palindromin pituutta ei tarvitse arvata kovin monta kertaa - ainoastaan logn kertaa - koska pitkän palindromin keskellä on aina lyhyempiä palindromeja. Näin ohjelman lopullinen aikavaativuus on O(nlogn). Käytännössä keskikohtaratkaisu vie tästä voiton, jos pisin palindromi ei ole kovin pitkä (satunnainen merkkijono), mutta esim. miljoona saippuakauppiasta selviää hajautuksen ja binäärihaun yhdistelmällä noin sekunnissa, kun taas keskikohtia tutkimalla aikaa kuluu vaikka kuinka kauan.
Antti Laaksonen kirjoitti:
Palindromeja voi etsiä tutkimalla merkkijonon kaikkia osamerkkijonoja, jolloin aikavaativuus on O(n^3), tai ovelammin ottamalla jokainen merkki vuorollaan palindromin keskikohdaksi ja tarkistamalla, kuinka pitkälle voidaan edetä kumpaankin suuntaan, jolloin aikavaativuus on O(n^2).
Jokaisen merkin ottaminen vuorollaan palindromin keskikohdaksi ei välttämättä tuota oikeaa ratkaisua, koska pisimmän palindromin pituus voi olla myös kahdella jaollinen (mikäli luin tehtävänannon tarpeeksi tarkasti). Esim. "katti" -> "tt".
Olet oikeassa, jätin mainitsematta tuon yksityiskohdan. Mutta asia korjaantuu tutkimalla erikseen parittomia ja parillisia palindromeja, ja parillisissa "keskikohta" on tyhjä. Sama huomio koskee muuten myös binäärihakua: pitää tutkia erikseen parittomia ja parillisia pituuksia.
En tiedä mikä on suffiksipuu, mutta mielestäni löysin kyllä palindromitehtävään lineaariratkaisun, ja suhteellisen helpon sellaisen vieläpä.
Idea on siinä, että lähdetään normaalisti alusta lähtien etsimään palindromeja keskikohtamenetelmällä alusta lähtien, ja taulukoidaan tulokset niin, että kussakin taulukon indeksissä i on pisimmän palindromin pituus, jonka keskikohta on kohdassa i. Lisäksi pidetään kirjaa siitä, mikä on pisimmälle jatkuva palindromi (siis palindromi jonka loppukohta tulee mahdollisimman myöhään, ei välttämättä pisin palindromi) joka on tähän mennessä löydetty.
Olkoon löydetyn pisimmälle jatkuvan palindromin keskikohta k, ja loppukohta l. Jos tällä hetkellä tutkitaan merkkiä nro. a, niin toimitaan seuraavasti:
- Jos a >= l, niin lasketaan normaalisti(=merkki kerrallaan) palindromin pituus, ja sijoitetaan k:hon a ja l:ään löydetyn palindromin loppukohta.
- Muuten tiedetään, että kohdassa a oleva palindromi on identtinen kohdassa k-(a-k) (=a peilattuna k:n suhteen) olevan palindromin kanssa (koska palindromin molemmat puolet ovat tietty identtiset!). Tietenkin tästä voidaan olla varmoja vain k-keskeisen palindromin reunalle asti, siitä eteenpäin on taas testattava merkki kerrallaan.
Algoritmi on lineaarinen, sillä merkkejä joudutaan tutkimaan vain, kun merkkijonossa mennään eteenpäin alueelle, jolle vielä yksikään palindromi ei ole yltänyt. Samoin ylimääräistä muistia vaaditaan vain merkkijonon mittaisen int-taulukon verran.
Tehtävään 1 sain mielestäni kohtalaisen nopean ratkaisun, joskaan aivan pisimpiin syötteisiin se ei välttämättä ehdi.
Tehtävän 2 ratkaisuni onkin kanssa suhteellisen ovela, tosin ei yhtä nerokas kuin Sisuaskin. Palindromeja etsitään keskipistemenetelmällä, ja tarkastelu suoritetaan vain sellaisiin kohtiin, joissa voi sijaita pidempi palindromi. Se, voiko kohdassa x sijaita riittävän pitkä palindromi tarkastetaan siten, että tarkastetaan ovatko riittävän kaukana keskipisteestä sijaitsevat merkit symmetrisessä asemassa (parilliset palindromit huomioiden).
Kaikilla testisyötteilläni ratkaisu on ollut riittävän nopea, vaikka koneeni testikoneelle häviääkin. Aikakompleksisuus on O(n^2). Tälläinen toteutuu tosin jos ja vain jos syöte on pelkkää yhtä ja samaa kirjainta :(
Itse lähdin kakkostehtävässä siitä, että vertaillaan ensin merkkijonon päitä ja tullaan sieltä keskelle päin. Tällöin jos oli juuri vaikka saippuakauppias monta kertaa peräkkäin tuli melko nopea aika, sillä palindromin keskellä olevien merkkien yli voitiin vain hypätä. Mutta sitten taas jos pitkiä ei löytynyt tuli ongelmia eli periaatteessa vain vastakohta tuolla keskipiste tarkastelulle. No joka tapauksessa en vaan saanut aikaan niitä esseitä, joten osallistuminen jäi ja KADUTTAA.
Sisuaski kirjoitti:
En tiedä mikä on suffiksipuu, mutta mielestäni löysin kyllä palindromitehtävään lineaariratkaisun, ja suhteellisen helpon sellaisen vieläpä.
Ratkaisusi vaikuttaa todella hyvältä ja pesee mennen tullen ehdottamani binäärihakuvirityksen. En vain uskonut, että asian voisi hoitaa noin helposti O(n)-ajassa. Merkkijonoalgoritmit ovat kyllä sellainen aihe, joka yllättää minut kerta toisensa jälkeen.
Mainitsin muuten aikaisemmin:
Antti Laaksonen kirjoitti:
Kauppatehtävän perusratkaisu toimii O(n^2)-ajassa, mutta tehtävää tarkemmin miettimällä sopivan aputaulukon avulla ratkaisun saa O(n)-aikaan.
Kun tehtävää miettii vielä tarkemmin, huomaakin, että mitään aputaulukkoa ei tarvita. (Otto Ebeling valisti minua tässä asiassa sähköpostitse.) Nopea ratkaisu (sekä aputaulukon kanssa että ilman) perustuu joka tapauksessa siihen, että laskettaessa kylien ostoarvojen summia järjestyksessä seuraavan kylän arvon voi laskea aika vaivattomasti edellisen perusteella.
Tässä on esimerkkitilanne, jossa suurin kerroin on 3. Ensimmäisellä rivillä on kylille keksityt tunnukset, toisella kylien ostoarvot ja kolmannella ostoarvojen kertoimet, kun lasketaan ostoarvojen summaa kylän E kohdalla:
A B C D E F G H I
2 7 3 9 1 3 2 2 7
1 2 3 2 1Kylän E summa on siis 1 * 3 + 2 * 9 + 3 * 1 + 2 * 3 + 1 * 2 = 32. Seuraavaksi pitäisi laskea samanlainen summa kylän F kohdalla:
A B C D E F G H I
2 7 3 9 1 3 2 2 7
1 2 3 2 1Summan voi toki laskea samoin kuin edellä: 1 * 9 + 2 * 1 + 3 * 3 + 2 * 2 + 1 * 2 = 26. Mutta kun edellinen summa sattuu olemaan tiedossa, sitä voi käyttää apuna laskennassa. Kylän F summa on muuten kuin kylän E summa, mutta kylien C, D ja E kertoimet ovat yhtä pienemmät ja kylien F, G ja H kertoimet ovat yhtä suuremmat. Eli aiemmasta summasta pitää vähentää kylien C, D ja E kerrointen summa eli 3 + 9 + 1 = 13, jonka jälkeen siihen pitää vielä lisätä kylien F, G ja H kerrointen summa eli 3 + 2 + 2 = 7. Siis riittää laskea 32 - 13 + 7 = 26.
Tästä Datatähdessä ja muissa kilpailuissa on todella usein kysymys: miten käyttää hyväksi jo aiemmin laskettuja tietoja.
Merkinnässä |i - j| käytettyjen pystyerottimien tarkoitus ei oikein auennut?
|a| = a:n itseisarvo, eli |a| = a, jos a >= 0 ja |a| = -a, jos a < 0.
Mitäs tällä tiedolla sitten tehdään tässä tapauksessa?
Koska olet viimeksi mitannut etäisyyksiä negatiivisina lukuina? Esimerkiksi onko matka kotoasi kouluun 4,3 km ja matka koulusta takaisin kotiin vastaavasti -4,3 km? Vahvasti kuitenkin veikkaisin, että sanot molempien matkojen kuitenkin olevan 4,3 km.
Tehtävänannossa mainittiin siis, että kylä j sijaitsee |i - j| kilometrin päässä kylästä i. Tutkitaan nyt esimerkiksi tilannetta, jossa halutaan selvittää kylien 2 ja 5 etäisyys. Muuttujissa i ja j ovat kylien tunnusnumerot. Nyt jos i = 5 ja j = 2, etäisyys on |5 - 2| = |3| = 3, ja samalla tavalla jos i = 2 ja j = 5, etäisyys on |2 - 5| = |-3| = 3. Eihän etäisyys saa riippua siitä, kumpi muuttuja sattuu kuvaamaan kumpaa kylää, ja tämän vuoksi käytetään itseisarvoa, jotta etäisyys on aina positiivinen.
No miten sitten tuossa "|a| = -a, jos a < 0" |a| = -a?
Jos itseisarvomerkkien sisällä on jotain negatiivista, se muuttuukin positiiviseksi. Jos a on vaikkapa -2, |a| = |-2| = 2. Toisin sanoen |a| = -a = -(-2) = 2. Eli a on jo valmiiksi negatiivinen, joten kun sen eteen laittaa toisen miinusmerkin, lopputulos on positiivinen. Vastaavasti laskussa |2 - 5| voi ajatella a:n olevan 2 - 5 = -3, ja koska a on negatiivinen, lopputulos on -a = -(2 - 5) = -(-3) = 3. Minusta itseisarvo on helpointa miettiä niin, että se poistaa luvun mahdollisen miinusmerkin.
No, ketkä kaikki sai kirjeen maolilta?
Mulle tuli fysiikka + datatähti.
Matematiikassa jäin pisteen päähän.
Datatähteen en ole vielä kehdannut osallistua (varmaan sen vuoksi että nykyään on vain lukiolaisten sarja), mutta peruskoulun matikassa pääsin loppukilpailuun.
En ole nähnyt kirjettä (enkä ole tällä hetkellä kotona) mutta kuulemma pääsin loppukilpailuun. Yhteensä meidän koulusta pääsi 4.
Joo, kyllä sieltä maolilta se kirje postiluukusta tipahti.
Onpas paljon tuttua väkeä MAOLin listoilla. Tosin eipä se yllätys ollutkaan, että putkalaiset taitavat näitä asioita. Menestystä loppukilpailuihin!
Antti Laaksonen kirjoitti:
Onpas paljon tuttua väkeä MAOLin listoilla. Tosin eipä se yllätys ollutkaan, että putkalaiset taitavat näitä asioita. Menestystä loppukilpailuihin!
Tässä vaiheessa varmaan pitäisi kiittää niitä henkilöitä, jotka ovat Putkapostien avulla auttaneet meitä ymmärtämään algoritmejä ja optimointia... ;)
Matematiikasta, fysiikasta ja tietotekniikasta sain postia. Kemiakilpailussa jäin juuri loppukilpailusta, kun jouduin lähtemään etuajassa ja jäi siksi koe kesken, mutta eipä tuo haittaa, kun kemiasta ja fysiikasta voi kuitenkin osallistua vain toiseen. Kisoissa nähdään sitten. :)
Terveisiä Datatähti-loppukilpailusta Helsingin yliopistosta!
Tänä vuonna loppukilpailun ohjelmointitehtävä osoittautui haastavaksi mutta ei mahdottomaksi. Kilpailun voitti Mikko Sysikaski, joka muuten uusi viime vuoden voittonsa. Toiseksi sijoittui Otto Ebeling ja kolmanneksi tuli Lauri Kenttä. Kaikki kolme ovat tuttuja aiemmista kilpailuista, joten kokemuksella näyttää olevan selvä yhteys menestykseen.
Loppukilpailun tulokset:
sija nimi pisteet ----------------------------------------------- 1. Mikko Sysikaski 77 2. Otto Ebeling 71 3. Lauri Kenttä 66 4. Mika Laitinen 52 5. Pyry Haulos 38 6. Aleksi Hartikainen 35 7. Jussi Kokkala 33 8. Jaakko Kulhia 32 9. Lari Koponen 30 10. Toni Huttunen 29 11. Lari Haataja 19 12. Samuel Marisa 17
Onnittelut hyvistä tuloksista ja menestystä tuleviin koitoksiin!
Onnea Laurille aka Metabolixille kolmannesta sijasta! Pääsikö tuloksille muita putkalaisia, itse en listasta muita tunnistanut?
Muutaman tunnistan vielä, eivät tosin kaikki ole niin aktiivisia täällä:
1. Sisuaski
2. tietoturvatestaaja
4. Altair^
8. lakupuu
9. L2-K2
Oho, ohjelmointiputkahan vie titteleitä minkä kerkiää. Isot onnittelut menestyksestä kaikille kahdelletoista kilpailijalle, mutta jättäkääs sitten ensi vuonna meille muilleki tilaa. ;)
No onnittelut nyt vielä sitten kaikille putkalaisille tasapuolisesti :)
Edit: 5. Pyry
Onnittelut kaikille! Harmi, että saavuin vähän myöhään paikalle, kun olisi ollut oikein tilaisuus tulla seuraamaan. :)
Loppukilpailun ohjelmointiosuus meni ainakin minulta hukkaan. Liian pitkä tehtävä suhteessa aikaan. Kuusi kilpailijaa kahdestatoista sai nolla pistettä ohjelmointiosuudesta. Esseet ratkasivat.
Kilpailu oli mielenkiintoinen. Pitänee osallistua seuraavanakin vuonna.
Antoivat kaksi paksua kirjaa algoritmeista ja kilpailutehtävistä.
Onnea nyt kaikille menestyneille!
Itse olin ainakin aivan pihalla miten kolmen tunnin aikarajaan pitäisi suhtautua itse kilpailutilanteessa. Keltanokkuudestani ohjelmoinnin suhteen johtuen menin ihan paniikkiin jo 45 min algoritmipohdinnan jälkeen, jonka jälkeen aloitin ohjelman toteuttamisen - ei olisi kannattanut. Koodatessani useita vanhoja tehtäviä aiemmin huomasin, että kaksikin tuntia algoritmin pohdintaan ei todellakaan ole hukkaan heitettyä aikaa. Olisi voinut uskaltaa tälläkin kertaa pohtia rauhassa.
Algoritmini oli huono, ja vaikea toteuttaa useiden indeksikikkailuiden takia. Indeksini bugasivatkin aivan loppuun asti, ja juuri kun sain suurimmat bugini korjattua, niin järjestäjien testijärjestelmät hajosivat täysin, jolloin debuggaamisesta tuli aivan mahdotonta. En kuitenkaan ole katkera, sillä mitalistit olivat ohjelmoinnissa sekä algoritmillisesti että koodausnopeudellisesti tällä kertaa valovuoden edellä - onnittelut mitalimiehille!
Niinhän se on, että sopivan algoritmin keksiminen on itsessään haastavaa, mutta kokonaan toinen juttu on vielä toimivan ohjelman kirjoittaminen. Ja joskus täytyy tehdä vaikea päätös, tähtääkö täydelliseen ohjelmaan, jonka toteutus kenties epäonnistuu, vai tyytyykö helppoon perusratkaisuun, jolla kuitenkin saa takuuvarmasti osan pisteistä. Tässä suhteessa Datatähti poikkeaa muista MAOLin kilpailuista: jos matematiikan vastauksessa on pieni virhe, se ei tuhoa kokonaisuutta, mutta jos ohjelmassa on pieni virhe, pistemäärän kohdalle ilmestyy usein pyöreä numeromerkki.
Aihe on jo aika vanha, joten et voi enää vastata siihen.