Keskustelu: Ohjelmointiputka: Putka Open 2025 kierros 3

Putka Open 2025 kierros 3 alkaa pian:

https://cses.fi/putka-open-2025/

Kierros 3 alkaa pe 17.10. klo 18:00 ja päättyy su 19.10. 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!

D-tehtävän esimerkissä on virhe, ohjelma ”DUP *” ei tuota tulokseksi 2.

Kiitos, korjasin nyt tämän virheen esimerkistä.

Nyt on jalskille sopivia tehtäviä. Olisi temaattista ratkaista D forthilla tai edes 8th:llä.

jlaire kirjoitti:

Nyt on jalskille sopivia tehtäviä. Olisi temaattista ratkaista D forthilla tai edes 8th:llä.

Perkule, aika ei nyt anna myöten... 8th ohjelmointikieltä hyödyntävän yksinkertaisen esimerkki Webbi-sovellusprojektin laitoin nyt kuitenkin kaikkien saataville. Jospa joku vaikka innostuu Forth sukuisiin ohjelmointikieliin tutustumaan.

Java jumittaa hyppytehtävässä. Olisi mukava tietää, miten paljon aikaraja ylittyy. Tuntuu, että Javalla tuota ei pysty ratkaisemaan annetun aikarajan puitteissa?

TapaniS kirjoitti:

Java jumittaa hyppytehtävässä. Olisi mukava tietää, miten paljon aikaraja ylittyy. Tuntuu, että Javalla tuota ei pysty ratkaisemaan annetun aikarajan puitteissa?

Koska ohjelmalle annettava syöte on hyvin yksinkertainen, voit helposti itse kokeilla, miten kauan kestää eri ruudukoilla, alkaen 3x3, 4x4, 5x5, 6x6, ja miten jyrkästi ajankäyttö lisääntyy, kun ruudukon koko kasvaa. Yleensä jos tehtävä tuntuu ajankäytön kannalta täysin mahdottomalta, vika ei ole kielessä vaan siinä, että tehtävään on olemassa jokin idealtaan tehokkaampi ratkaisu.

Jep, kyllä tuo onnistuikin, kun löysin tehokkaamman ratkaisun! Great! Tästä tarkemmin osakilpailun päättymisen jälkeen ..

Ratkaisuja:

A, Forth. O(n). Syötekoko on niin pieni, että kaikki luvut voi muodostaa kopioimalla ykköstä ja laskemalla yhteen (DUP DUP ... + +). Koska ykkönen on pinossa valmiiksi, ykköstehtävään vähintään yhden komennon mittainen ratkaisu pitää tehdä erikseen ja voi olla esimerkiksi DUP DROP. Forth-koodia voi lyhentää käyttämällä kakkosen potensseja eli laittamalla komentoja DUP ja + myös eri järjestykseen, mutta tämä vaatii jo enemmän ajattelua. Ehkä tehtävässä olisi voinut olla vaikka 10 pisteen osatehtävä, jossa olisi tarvinnut tehdä näin.

B, Hypyt. O(nm). Reitti löytyy hyppäämällä vuorotellen ruudukon alusta loppuun ja lopusta alkuun, aina ensimmäiseen vapaaseen ruutuun. Yhtä riviparia edetessä |dy| pysyy samana ja dx/dy pienenee, ja seuraavalle riville siirtyessä |dy| muuttuu, joten samaa hyppyä ei tule koskaan. Ruudukkoa ei edes tarvitse pitää muistissa, vaan riittää, kun osaa kuljettaa koordinaatteja (x1,y1) alusta loppuun päin ja (x2,y2) lopusta alkuun päin ja hyppää vuorotellen näiden välillä, kunnes koordinaatit "törmäävät" eli ruudukko on käyty läpi.

C, Kyselyt. O((n+q) log² n) tai jotain. Ensinnäkin tarvitaan jokaiselle luvulle summataulu, josta luvun määrä syötteen välillä (a,b) saadaan kohtien b+1 ja a erotuksena. Lukuja voi olla 10⁵ ja kohtia 10⁵, ei voida tehdä joka luvulle täyttä taulukkoa, vaan tämä täytyy esittää pareina (kohta, määrä), ja tällöin tietyn kohdan löytäminen vie logaritmisen ajan (esimerkiksi binäärihaulla). Toiseksi tarvitaan segmenttipuu eli binääripuu, jossa alimmalla tasolla jokainen luku hallitsee omaa yksittäistä kohtaansa ja ylemmillä tasoilla hallitseva luku on jompikumpi alempien solmujen luvuista, koska lukua voi olla yli puolet vain, jos sitä on yli puolet edes toisessa alemmista puolikkaista. Kyselyyn (a,b) löytyy tästä puusta logaritmisesti mahdollisia hallitsevia lukuja, joiden tarkastus summataulusta vie logaritmisen ajan. Viimeisten kahden osatehtävän ero on hämmentävän pieni, ja osoittautui, että riittävä optimointi koodiin on se, että kyselyt käsitellään järjestyksessä loppukohdan mukaan ja summatauluun lisätään lukuja vasta kyselyiden edetessä, jolloin summataulun loppukohtaa ei tarvitse hakea binäärihaulla vaan viimeinen lisätty luku on aina oikea loppukohta. Eli tällä kertaa ei tarvinnut keksiä erikoisempaa segmenttipuun käyttötapaa.

D, Ohjelmat. Noin 50 pistettä saavutin rekursiolla kokeilemalla vaihtoehtoja (i-1), (i/2), (sqrt(i)) ja (i/j)*(j). Noin 80 pistettä saavutin leveyshakuun perustuvalla ratkaisulla, jossa pino oli rajattu 4 lukuun ja oli lisäksi optio yhdistää kaksi löydettyä ratkaisua DUP-SWAP-tekniikalla (yhden kerran). Lopullisen tulokseni puristin syvyyshaulla, jossa oli rajattu syvyys ja tilan tiivisteen perusteella samojen tilojen välttelyyn. Ajoin tästä muutamaa erilaista versiota (eri syvyys, erilainen saman tilan avain, eri järjestys kokeiluille jne.), ja eri versiot onnistuivat parantamaan eri testitapausten ratkaisuja antamani ajan puitteissa. Valitettavasti en tehnyt tätä ajoissa ja tarpeeksi suunnitelmallisesti, joten viimeinen piste jäi saamatta.

Hauska D-tehtävä. Käytin leveyshakua kaikkien ohjelmien kokeiluun Metabolixin aiemman ratkaisun tapaan. Viimeisetkin syötetapaukset ratkesivat 26 askeleen kohdalla, eli riitti optimoida koodia siihen asti.

Helppo rajaus on, että jos etsitään korkeintaan N pituisia ratkaisuja niin askeleella I voidaan hylätä yli N-I kokoiset pinot. Muistinkäytön optimoimiseksi säilytin vain 64-bittisen hajautusarvon käydyistä tiloista ja välttelin tilaa vieviä rakenteita kuten hajautustauluja.

Tiloja tulee n. puoli miljardia, jotka koneeni sai laskettua n. 25 minuutissa.

Siistimätön koodini koko rumuudessaan siltä varalta että jotakuta kiinnostaa: http://paste.dy.fi/sqy

Olisi kiva jos muutkin jakaisivat ratkaisujaan tehtävään, koska tykkään lukea erilaisia koodeja ja tämän tehtävän formaatilla on vaikeampi vakoilla muuten.