Putka Open 2015 kierros 1 alkaa hetken kuluttua:
http://cses.fi/putka-open-2015/
Kierroksen kesto on 3 tuntia, ja voit aloittaa milloin tahansa välillä 17.7. klo 16:00 ja 19.7. klo 22:00.
Onnea kilpailuun!
Huom: Jos koodaat Javalla, älä käytä package-komentoa koodissa. Tämä aiheuttaa virheen RUNTIME ERROR järjestelmässä.
Miksiköhän muuten kääntäjäoptioina on -std=c++0x eikä c++11? Kai tuolla on merkitystä gcc:n kannalta, jos nyt oikein käsitin.
Liput -std=c++0x ja -std=c++11 tarkoittavat samaa. Lähinnä -std=c++0x on vanhasta tottumuksesta, koska ennen g++ hyväksyi vain sen.
Kierroksen 1 tehtävässä C ei näy kuva.
Kiitos tiedosta, tämä on nyt korjattu.
Ensimmäinen kierros keräsi mukavasti osallistujia, ja nyt odotamme, että viimeiset osallistujat saavat suorituksensa valmiiksi.
Kierroksen tulokset ja tehtävien ratkaisut ilmestyvät kolmen tunnin kuluttua.
Kierroksen 1 tulokset ovat tässä:
Tuloslista sisältää kaikki osallistujat, joilla on positiivinen pistemäärä. Järjestys on ensisijaisesti pistemäärän mukaan ja toissijaisesti sen ajanhetken mukaan, jolloin osallistuja saavutti pistemäärän.
Viisi osallistujaa sai täydet 300 pistettä. Onnittelut, Laakeri, Sisuaski, Gomhog, Hansuzu ja Futureman!
Tehtävien ratkaisut ovat tässä:
Seuraava kierros on vajaan kuukauden kuluttua 14.–16.8. Nähdään silloin!
Tuo ratkaisu sivu viljelee "Math processing error":ria.
Onko virheitä vielä? Yleensä ne ovat väliaikaisia ja johtuvat käytetystä matemaattisten kaavojen näyttäjästä.
Antti Laaksonen kirjoitti:
Kierroksen 1 tulokset ovat tässä:
Jos sopii, liitän tähän pari lisätietokoostetta.
Kielet ja kieliyhdistelmät sekä niitä käyttäneiden osallistujien määrät:
C++: 26 kpl Java: 9 kpl Python2: 3 kpl Python3: 2 kpl C++ + Python2: 1 kpl C++ + Java: 1 kpl
Pistetaulukko vähintään 200 pistettä saaneiden osalta maksimipisteiden saavutusaikoineen ja kielineen:
300 0:39:16 Laakeri - C++ 300 1:27:52 Sisuaski - C++ 300 1:33:57 Gomhog - C++ 300 2:10:58 Hansuzu - C++ 300 2:57:36 Futureman - Java 245 2:30:54 eXeP - C++ 235 2:54:51 ydna - C++ 212 1:01:37 Chiman - Python3 212 2:00:34 tta - C++ 212 2:26:42 Kuha - C++ 212 2:31:15 tsiki - Python2 212 2:33:07 Hennkka - C++ 212 2:41:56 jnalanko - C++ 200 0:22:45 jlaire - C++ 200 0:22:54 kllp - C++ 200 0:53:07 MusserO - C++ 200 1:02:02 PT - C++ 200 1:15:17 Nameci2718 - Java 200 1:48:28 copyrite - Python2 200 2:16:30 baobab - Java 200 2:25:48 Spyro - C++ 200 2:32:27 juhoh - C++
Muokattu 21.7. klo 11:15: lisäsin jälkimmäisen koosteen.
Kiitos, nuo ovat kiinnostavia tietoja.
Vielä yksi kooste. Eräitä prosenttiosuuksia koko kilpailun yhteenlasketuista pisteistä ja niiden saavuttamisajankohdat:
0:00:35 1.09 % 0:03:18 3.21 % 0:04:13 4.67 % 0:05:21 6.12 % 0:05:50 7.57 % 0:07:40 9.03 % 0:07:44 10.48 % 0:10:14 21.32 % 0:18:04 31.38 % 0:22:35 40.65 % 0:32:13 51.13 % 0:42:05 60.10 % 1:00:22 70.17 % 1:27:52 80.01 % 2:13:38 90.87 % 2:26:42 95.20 % 2:30:24 96.66 % 2:31:15 97.08 % 2:33:07 98.04 % 2:54:51 99.06 % 2:57:36 100.00 %
Eli puolen tunnin tienoilla oli jo puolet kokonaispisteistä kasassa.
Nyt kierroksen jo päätyttyä palasin vielä kokeilemaan, miten Lähetti-tehtävän läpäisy onnistuu Python3:n suoritusnopeudella. Se vaati muutaman yrityksen, mutta onnistuin rimaa hipoen:
http://cses.fi/26/result/16199/
Jätin tarkoituksella kokeilematta netistä löytyvien valmiiden laskentakaavojen nopeudet.
Muokattu klo 12.30: nyt linkki vie lyhytrivisempään koodiin
Chiman kirjoitti:
0:00:35 1.09 %
Aika nopeasti toteutettu: http://cses.fi/26/result/15384/
Nämä koodit eivät muuten näy ainakaan täällä monospace-fontilla. CSS näyttää kaipaavan pientä korjausta.
jlaire kirjoitti:
Nämä koodit eivät muuten näy ainakaan täällä monospace-fontilla. CSS näyttää kaipaavan pientä korjausta.
Jos kyse on lähdekoodin liian pitkistä riveistä, linkkasin ylle tiiviimmän version omastani. Saatoit tietty tarkoittaa Putkaakin, mutta sama se, pitkät koodirivit voivat olla hankalia.
Koodissa parittomuus/parillisuus tarkoittaa tietysti ruutumäärää rivillä, mutta jääköön oikaisematta.
Chiman: Koodisi ei ole tehokas. Tehtävän voi ratkaista järjestyksessä ilman rekursiota, ks. http://cses.fi/26/result/16200/. (Koodia voisi vielä parantaa pitämällä muistissa vain edellisen ja nykyisen rivin, koska aiempia ei tarvita.)
Metabolix kirjoitti:
Chiman: Koodisi ei ole tehokas. Tehtävän voi ratkaista järjestyksessä ilman rekursiota, ks. http://cses.fi/26/result/16200/. (Koodia voisi vielä parantaa pitämällä muistissa vain edellisen ja nykyisen rivin, koska aiempia ei tarvita.)
Ilman kommentteja tai kuvaavia muuttujanimiä kärsivällisyys tuon ratkaisun logiikan selvittämiseen loppuu kesken. Pisteet tietysti tulevat vain toimivasta koodista, joten siltä kannalta vain lopputuloksella on merkitystä.
En odottanutkaan, että ratkaisuni olisi huipputehokas vaan että sellaiseen olisin voinut päätyä kilpailuajan puitteissa, koska pyrin koodaamaan selkeästi helpottaakseni myös debuggaamista. Tällä kertaa osaamiseni ei riittänyt täysiin pisteisiin.
Chiman kirjoitti:
En odottanutkaan, että ratkaisuni olisi huipputehokas
Viestistäsi (varsinkin yhdistettynä aiempiin) jäi kuva, että jotenkin epäilit, onko Pythonilla edes mahdollista päästä reilusti aikarajan alle. Tähän oli tarkoitukseni vastata: on mahdollista, eikä vaadi sen kummempaa ratkaisua kuin muillakaan kielillä.
Chiman kirjoitti:
Ilman kommentteja tai kuvaavia muuttujanimiä kärsivällisyys tuon ratkaisun logiikan selvittämiseen loppuu kesken.
Varmasti. Sellaista on kisakoodaus. Pari kommenttia on C++-versiossa.
Ratkaisun ideana on laskea erikseen mustille ja valkeille, monellako tavalla voidaan asettaa i riville j lähettiä. On selvää, että ensimmäiselle riville saadaan 0 lähettiä 1 tavalla, 1 lähetti leveyden mukaan ja useampaa ei mitenkään. Myöhemmillä riveillä lasketaan yhteen vaihtoehdot, että lähettejä on haluttu määrä jo edellisellä rivillä (eli ei aseteta uutta) ja että lähettejä on edellisellä tasan yksi vähemmän ja nykyiselle laitetaan uusi jollakin mahdollisista tavoista (rivin leveyden ja aiemmin asetettujen määrän mukaan). Kuten Antin ratkaisukuvauksessa kerrotaan, voidaan laskea mustat ja valkeat ruudut erikseen ja yhdistää ratkaisut summakaavalla ∑m(x)v(k−x).
Nämä elementit ovat jo omassakin ratkaisussasi, mutta silmukkaratkaisussa lähdetään liikkeelle niistä kohdista, jotka sinulla ovat alussa return-lauseina, ja täytetään tulosmuistia tästä järjestyksessä, kunnes saadaan riittävän monen rivin ratkaisu.
Metabolix kirjoitti:
Viestistäsi (varsinkin yhdistettynä aiempiin) jäi kuva, että jotenkin epäilit, onko Pythonilla edes mahdollista päästä reilusti aikarajan alle.
Ymmärrän, mutta tuon sijaan tarkoitukseni oli selvittää, miten tehottomamman kielen valinta voi rajoittaa pistesaalista käytännön tilanteessa. 2 sekunnin suoritusaika Pythonilla vastaa ehkä 0,1 sekunnin suoritusaikaa C++:lla.
Huonolla algoritmilla ei ole mitään toivoa C++:llakaan saada täysiä pisteitä, mutta melko hyvällä algoritmilla valitun kielen vaikutus voi näkyä.
Olisin kierroksen aikana vaihtanut C++:aan, jos se olisi auttanut sopivasti aikarajan alle. Sitä tilannetta ei kuitenkaan tullut vastaan, joten pysyin Pythonissa, koska käytän sitä sujuvammin.
Jos tällainen sovellus tulisi jatkuvaan tuotantokäyttöön, Pythonin käyttö olisi typerää. Kuitenkin tässä kisassa ratkaisee vain koodauksen ja yhden suorituskerran viemä yhteisaika.
Kiitos ratkaisukoodin selvennyksestä.
Chiman, olet oikeassa, C++:n käyttäjällä oli etua Pythoniin verrattuna viimeisessä tehtävässä. Jälkeenpäin ajatellen parempi yläraja viimeiseen alitehtävään olisi ollut ehkä n=50.
Chiman kirjoitti:
jlaire kirjoitti:
Aika nopeasti toteutettu: http://cses.fi/26/result/15384/
Nämä koodit eivät muuten näy ainakaan täällä monospace-fontilla. CSS näyttää kaipaavan pientä korjausta.
Jos kyse on lähdekoodin liian pitkistä riveistä,
Tarkoitin noita result-linkkejä, siellä fonttina on verdana eikä courier, koska koodi on <pre><span>täällä</span></pre> ja CSS näyttää seuraavalta:
* {
font-family: verdana;
}
pre {
font-family: courier;
font-size: 14px;
}Ensimmänen sääntö ylittää toisen.
Nyt CSS-tiedosto lienee järkevämpi, ja koodin pitäisi näkyä tasalevyisenä.
Metabolix kirjoitti:
Tehtävän voi ratkaista järjestyksessä ilman rekursiota, ks. http://cses.fi/26/result/16200/. (Koodia voisi vielä parantaa pitämällä muistissa vain edellisen ja nykyisen rivin, koska aiempia ei tarvita.)
Itse asiassa riittää vain yksi rivi, kunhan rivin päivitys tehdään suurimmasta indeksistä lähtien. Tällainen koodista tuli tuolla ja parilla muulla muutoksella:
http://cses.fi/26/result/16203/
Nopeuseroa jälkimmäisen eduksi alkaa tulla vasta kilpailutestejä suuremmilla syötteillä.
Koodisi antaa muuten väärän lopputuloksen syötteellä 1 1. Oikea vastaus on 1, ei 0.
Chiman kirjoitti:
Koodisi antaa muuten väärän lopputuloksen syötteellä 1 1.
Niin, en näköjään ole huomioinut tuota rajatapausta, jossa ei ole yhtään parillisen mittaista riviä. Tällöin lopun summassa indeksi n-2 on negatiivinen. Hauskasti Pythonissa tästä tulee väärä vastaus, kun taas C++-versio voisi teoriassa kaatua tai ainakin tuottaisi mielivaltaisen tulosteen. Helpoin korjaus (kisatyyliin) on käsitellä alussa erikseen tapaus n=1.
jlaire kirjoitti:
Aika nopeasti toteutettu: http://cses.fi/26/result/15384/
Kun tuossa nyt keskusteltiin vaan noista muotoiluista, niin jäin kyllä itse ihmettelemään miten on edes mahdollista lukea tehtävänanto, kirjoittaa tuollainen koodi ja laittaa se kilpailuun 35 sekunnissa. Vai onko tämä joku tekoäly joka on osallistunut kilpailuun?
Grez kirjoitti:
Kun tuossa nyt keskusteltiin vaan noista muotoiluista, niin jäin kyllä itse ihmettelemään miten on edes mahdollista lukea tehtävänanto, kirjoittaa tuollainen koodi ja laittaa se kilpailuun 35 sekunnissa. Vai onko tämä joku tekoäly joka on osallistunut kilpailuun?
En sitä ihan suoraan viitsinyt sanoa, mutta en siis usko että on mahdollista.
Tekoälyn toteuttamista helpompaa on pyytää tehtävänanto joltain joka osallistui itseä aiemmin. Tai käyttää itse kahta eri tunnusta.
Onneksi kyseessä ei kuitenkaan ole mikään hirveän vakava kisa, joten tällainen säätö tuskin on yleistä.
No itsekin läpällä heitin tuon tekoälyjutun. Mutta olisihan se komeaa jos joku olisi kehittänyt koodaavan tekoälyn ja koemielessä laittaisi sen osallistumaan tällaiseen kilpailuun. :p
Aihe on jo aika vanha, joten et voi enää vastata siihen.