Putka Open 2020 kierros 1 alkaa pian:
https://cses.fi/putka-open-2020/
Kierros 1 alkaa pe 4.9. klo 18:00 ja päättyy su 6.9. klo 23:00. Voit lähettää ratkaisuja milloin tahansa tällä aikavälillä.
Kierroksella on neljä tehtävää, jotka on jaettu osatehtäviin. Voit lähettää tehtäviin useita ratkaisuja ja paras ratkaisu jää voimaan.
Tuloslistalla järjestyksen määrittää tehtävien yhteispistemäärä. Jos kahdella osallistujalla on sama pistemäärä, ensin pistemäärän saavuttanut on parempi.
Tervetuloa kilpailuun!
Kiitos kisasta, Antti! Mukava nähdä, että osallistujia riittää. Tehtävät ovat mielestäni onnistuneen eritasoisia. Erityisesti viimeinen osoittautui yllättävän vaikeaksi, ja olisin toivonut vielä väliporrasta 36 ja 100 pisteen väliin, koska ainakin oma versioni oikeasta algorimista oli ensin marginaalisesti liian hidas.
Koska (ilmeisesti) noista testien tuloksista ei ole mahdollista saada mitään tarkempaa tietoa, kuin että ovatko oikein vain väärin, niin olisi kiva jos olisi useampi (isompi) esimerkki syötteestä ja oikeasta tuloksesta.
Esim. itselläni on "Ruudukko"-tehtävässä ohjelma joka antaa oikean tuloksen esimerkkiaineistosta ja kesti aika kauan ennen kuin sain tehtyä sille aineiston, joka tuotti väärän tuloksen.
Loistava kilpailu! Harmi tosin että huomasin kilpailun vasta tänään päivällä, joten ensimmäisestä kierroksesta en ehdi ainakaan saamaan täysiä pisteitä.
Tästä sainkin idean. Itse en ihan hirveän säännöllisesti käy putkassa ja useampi kilpailu ja haaste onkin mennyt tämän vuoksi sivusuun. Olisiko mahdollista lähettää jonkinlainen sähköpostiviesti uusista kilpailuista sen haluaville? Näin minun kaltaisiltani laiskoilta putkan käyttäjiltä ei menisi kilpailut ohi.
Grez kirjoitti:
olisi kiva jos olisi useampi (isompi) esimerkki syötteestä ja oikeasta tuloksesta
Enpä tiedä. Tuo syötteiden ja testien keksiminen on tavallaan kyllä osa haastetta myös. Itse esimerkiksi generoin isoja testitiedostoja tuohon ruudukko tehtävään. Hyvin löytyi virheet kun teki ensin hitaan version ratkaisimesta ja vertasi tuloksia sitten myöhemmin optimoidun version antamaan tulokseen.
osku91 kirjoitti:
Itse esimerkiksi generoin isoja testitiedostoja tuohon ruudukko tehtävään.
Itsekin generoin läjän testitiedostoja, mutta kävi sikäli huono tuuri että niissä ongelmaa ei virheellisen koodin tapauksessani esiintynyt. Sinänsähän sama huono tuuri olisi voinut tulla isommallakin esimerkkisyötteellä.
Eli joo ehkä tuo toiveeni on toisaalta turha. Nyt vaan jäin vähän epäilemään että ohjelmani tuloste palvelimella oli jotain muuta kuin omalla koneella tms.
Kierros 1 on nyt päättynyt ja tulokset ovat täällä:
Nyt CSES:n kautta näkee myös kaikki lähetykset ja testit.
Putka Open 2020 lähti mukavasti käyntiin, ja tästä on hyvä jatkaa seuraavalle kierrokselle, joka järjestetään 25.–27.9.
Hienot statistiikat, mutta total points over time graafissa ei näy putkakäyttäjien nimiä (vaikka ne näkyy esim. scoreboardilla)
Ja miksi muuten code running time distribution graafilla näkyy C-tehtävän viiva 10ms kohdalla olevan jossain 43 paikkeilla, vaikka hiiren kohdalle siirtämällä näyttää että oikea arvo olisi vain 1.
Grez kirjoitti:
total points over time graafissa ei näy putkakäyttäjien nimiä (vaikka ne näkyy esim. scoreboardilla)
Huomasin tämän myös, mutta en ehtinyt tälle viikolle korjaamaan. Toivottavasti ensi viikon kisaan mennessä toimii. Olen siis nuo statistiikkasivut aikoinaan toteuttanut.
Grez kirjoitti:
Ja miksi muuten code running time distribution graafilla näkyy C-tehtävän viiva 10ms kohdalla olevan jossain 43 paikkeilla, vaikka hiiren kohdalle siirtämällä näyttää että oikea arvo olisi vain 1.
Tässä ideana on että tehtävien kuvaajat laitetaan päällekkäin, jotta kokonaisjakauma näkyy suoraan, tietysti hankaloittaen yksittäisten tehtävien arvojen lukemista. Ne saa kuitenkin näkyviin jos piilottaa muut tehtävät.
Niinpä niin, olisihan sen voinut itsekin huomata että se on pinottu graafi.
osku91 kirjoitti:
Olisiko mahdollista lähettää jonkinlainen sähköpostiviesti uusista kilpailuista sen haluaville?
Tällainen mahdollisuus itse asiassa on jo, ja voit profiilisivulta tilata viestin. Tosin tällä kertaa myös viestin lähetys unohtui valitettavasti.
Grez kirjoitti:
Esim. itselläni on "Ruudukko"-tehtävässä ohjelma joka antaa oikean tuloksen esimerkkiaineistosta ja kesti aika kauan ennen kuin sain tehtyä sille aineiston, joka tuotti väärän tuloksen.
Tuo on aika yleinen ongelma. Toisaalta usein virhe esiintyy myös jollain melko pienellä syötteellä, ja joskus olen tehnyt niin, että generoin kaikki mahdolliset syötteet tiettyyn kokoon asti ja laitan varmasti oikean mutta hitaan koodin ratkaisemaan ne ja vertaan tuloksia. Esimerkiksi Ruudukko-tehtävässä voisi hyvinkin generoida kaikki 4x4-ruudukot (65536 kpl) ja ratkaista ne "brute forcella" eli vaikka syvyyshaulla (20 reittiä). Luonnollisesti tätä ratkaisua varten kannattaa muuttaa ohjelmaa niin, että kaikki syötteet voi testata yhdellä käynnistyksellä.
Mukava kisa ja aika haastavan tuntuisia tehtäviä! Itse sain vain ensimmäisen ratkaistua. Toiseen tehtävään oli jo hyvä idea, mutta aika ei riittänyt toteutuksen viimeistelyyn. Mutta hyvä, että oli yksi vähän helpompi tehtävä mukana. Oma tavoitteeni on päästä mukaan T-paitojen arvontaan! 😁
Metabolix kirjoitti:
osku91 kirjoitti:
Olisiko mahdollista lähettää jonkinlainen sähköpostiviesti uusista kilpailuista sen haluaville?
Tällainen mahdollisuus itse asiassa on jo, ja voit profiilisivulta tilata viestin. Tosin tällä kertaa myös viestin lähetys unohtui valitettavasti.
Hyvä tietää! Laitoinpa tilaukseen.
Kerron tässä eräät oikeat ratkaisut opiksi. Tosin B ja D voivat ratketa vielä paremmin. Näillä vinkeillä voi vielä yrittää ratkaista tehtäviä ja opetella temppuja seuraavia kierroksia varten. Kisakoodarin käsikirjaa kannattaa lukea myös.
A, Pinot
Hidas ratkaisu on, että silmukassa tehdään ohjeen mukaan: vähennetään kolikoita pienemmän pinon mukaisesti.
Nopea ratkaisu tästä tulee, kun käytetään jakolaskua: iso pino jaettuna pienellä pinolla kertoo vähennysten määrän, ja sen jälkeen isommasta pinosta on tullut pienempi. Esimerkiksi jos pinot ovat 16 ja 5, jakolaskusta kokonaisluvuilla saadaan 3 ja ison pinon uusi koko on 16 - 5*3 = 1, eli pinot ovat 5 ja 1. Jakolaskusta saadaan 5, minkä jälkeen isompaan pinoon jää 5 - 5*1 = 0 ja tehtävä päättyy. Vastaukseksi tulee jakolaskujen summa eli 3+5 = 8.
B, Lista
Ensin pitää tehdä taulukko alkuluvuista 2000:een asti, tämän voi laskea tai kopioida netistä. Ratkaisun lista aloitetaan isoimmasta luvusta, ja sitten tarvitaan rekursio (tai vastaava): funktio rekursio(i) sisältää silmukan, jossa kokeillaan ratkaisun kohtaan i jokaista lukua, jota ei ole vielä käytetty ja jolla tämän ja edellisen summa on alkuluku, ja silmukassa rekursiivisesti kutsutaan rekursio(i+1). Jos saadaan kaikki luvut laitettua, ratkaisu on löytynyt. (Jos rekursio on liian hidas, sen voi muuttaa silmukaksi.)
C, Ruudukko
Hidas ratkaisu käy läpi (vaikka rekursiolla) kaikki eri reitit, merkkaa taulukkoon löydetyt kolikoiden lukumäärät ja lopuksi laskee eri tulokset.
Nopea ratkaisu on dynaamista ohjelmointia: kohdasta (x,y) voidaan saavuttaa ne määrät, jotka voidaan saavuttaa kohdasta (x+1,y) tai (x,y+1), plus ruudun mahdollinen oma kolikko. Viimeisellä rivillä ja sarakkeella pitää huomioida, että ei mennä ruudukon yli. Ratkaisu voidaan hakea rekursiolla, jossa rekursio(x,y) laskee ratkaisun siitä eteenpäin eli rekursio(0,0) laskee alusta asti. Dynaamisen ohjelmoinnin olennainen asia on, että rekursion tulos tallennetaan eikä lasketa samaa asiaa monta kertaa. Rekursion sijaan voidaan täyttää ratkaisut taulukkoon lopusta alkuun päin järjestyksessä sisäkkäisissä silmukoissa.
D, Vaihdot
Hidas ratkaisu sisältää neljä sisäkkäistä silmukkaa: joka kohdalle a, joka kohdalle b, vaihda kohdat a ja b, laske tarvittavien kierrosten määrä (kun haettava on alle viimeisen, lisää yksi kierros laskuriin, kierrä jokainen luku, ja jos luku on haettava, nosta haettavaa yhdellä).
Nopeassa ratkaisussa pitää ensinnäkin tunnistaa kannattavat vaihdot: jos lukuja järjestyksessä kiertäessä 1:n jälkeen tulee ensin 3 ja sitten 2, kannattaisi vaihtaa 2 tuonne 1:n ja 3:n väliin. Sitten täytyy tehdä jokin rakenne, jolla saa nopeasti selville, että kun luku A haluaisi listan kohtaan I-J, montako lukua tuolta väliltä haluaisi tulla luvun A tilalle (parannus vaihdosta 2), ja vastaavat kirjanpidot myös, monelleko vaihdolla ei ole merkitystä (parannus 1) tai on haittaa (parannus 0). Tämä tietorakenne ja sen oikea käyttö tehtävässä on tähän asti kisan vaikein asia. Sopiva tietorakenne on summakyselyn mahdollistava segmenttipuu tai vastaava.
Omassa ratkaisussani on kaksi vaihetta. Käsittelin erikseen vaihtoehdon, jossa x ja x+1 vaihdetaan keskenään; tämä onnistuu ajassa O(n) syötteen koon mukaan, ja parannuksen määrä selviää nopeasti laskemalla vain kierrosten määrä muuttuvien lukujen osalta ennen ja jälkeen muutoksen. Vaikeampi osuus on muiden vaihtojen tutkiminen. Silmukassani käydään läpi listan luvut järjestyksessä ja pidetään kirjaa toivotuista ja ei-toivotuista. Olkoon x nykyinen luku. Poistetaan kirjanpidosta luvut x-1 ja x+1, koska niiden asia on jo käsitelty erikseen. Haetaan tällä hetkellä kertyneiden toivottujen ja ei-toivottujen lukumäärät niillä listan alueilla, joissa x itse olisi toivottu tai ei-toivottu. (Oikeat alueet saadaan siitä, missä luvut x-1 ja x+1 sijaitsevat.) Näistä lukumääristä saadaan laskettua, paljonko parannusta ja monellako tavalla x:n siirroilla voi saavuttaa. Lopuksi merkitään luku x+1 toivotuksi ja x-1 ei-toivotuksi ja siirrytään seuraavaan kohtaan. (Tarkemmin ottaen listoja on kolme: (1) toivotut ja nyt väärässä paikassa olevat, parannus 1; (2) toivotut ja oikeassa paikassa olevat, tai ei-toivotut mutta muutenkin väärässä paikassa olevat, parannus 0; (3) ei-toivotut ja nyt oikeassa paikassa olevat, parannus -1.)
Mietin myös, onnistuisiko ratkaisu tehokkaasti intervallipuulla, ja jos joku on tehnyt sillä tavalla, saa mielellään kertoa ratkaisusta.
Kiitos hyvistä ratkaisuista! Saihan sitä sitten heti tehtyä toimivan koodin ruudukko tehtävään kun sai ratkaisun kirjoituksen muodossa :D.
Jos sitä vielä taidot riittäisi siihen, että saisi toteutettua toimivan koodin "Vaihdot" tehtävään.
AtskaFin kirjoitti:
Jos sitä vielä taidot riittäisi siihen, että saisi toteutettua toimivan koodin "Vaihdot" tehtävään.
Mutta sinullahan on toimiva koodi. ;) Näissä kisoissa saa tarkoituksella pisteitä myös hitaasta ratkaisusta, ja se on paljon parempi kuin puuttuva ratkaisu.
Voit optimoida Vaihdot-tehtävän ratkaisuasi vaihe kerrallaan.
Lajittelu vie O(N log N) aikaa, joten tuloksia ei kannata lajitella, vaan parhaat voi hakea suoraan järjestyksessä ajassa O(N). Tästäkin voi parantaa: koko tulosten tallennus taulukkoon on ajanhukkaa, kun voi alunperinkin pitää kirjaa parhaasta ja sen lukumäärästä:
if (uusi_tulos < paras_tulos) {
paras_tulos = uusi_tulos;
paras_maara = 1;
} else if (uusi_tulos == paras_tulos) {
paras_maara += 1;
}Seuraava optimointi on se, että kierrosten lasku (sinulla getRounds) toimisi tehokkaammin. Ensin tehdään uusi käänteinen taulukko: kun alkuperäisessä datassa luku[i]=x, uudessa taulukossa indeksi[x]=i. Tällä tavalla ei tarvitse etsiä seuraavaa lukua silmukalla, vaan sen paikka tiedetään valmiiksi. Kierros kasvaa, jos seuraavan luvun paikka on nykyistä lukua aikaisemmin.
Toinen parannus kierrosten laskentaan on, että ei lasketa aina koko taulukkoa alusta loppuun vaan pelkkä muutos: kun vaihdetaan kohdat i ja j, tarvitsee laskea kierrokset ennen ja jälkeen vaihtamisen vain vaihdettavien lukujen kohdalta (luku[i]-1, luku[i], luku[i]+1, ja vastaavasti luku[j]-1, luku[j], luku[j]+1, tai peräkkäisten lukujen tapauksessa vain luku[i]-1, luku[i], luku[j], luku[j]+1).
Näillä parannuksilla saa tehtävästä keskimmäiset pisteet. Parhaisiin pisteisiin vaaditaan tuo mainitsemani nopeat välikyselyt mahdollistava tietorakenne kuten segmenttipuu. Kannattaa lukea Antin kirjoittamaa Kisakoodarin käsikirjaa.
Aihe on jo aika vanha, joten et voi enää vastata siihen.