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.

Hypyissä keksin kirjoittaa vastaukset bufferiin ja tulostaa sen sitten lopuksi. Tämä antoi täydet pisteet.

Seuraavassa tehtävässä (Kyselyt) tuo ei riittänyt ja Brutal Force antoi vain 10 pistettä.

Metabolix kirjoitti:

Kyselyyn (a,b) löytyy tästä puusta logaritmisesti mahdollisia hallitsevia lukuja, joiden tarkastus summataulusta vie logaritmisen ajan.

Segmenttipuun voi toteuttaa myös niin, että se palauttaa vain yhden mahdollisesti hallitsevan luvun: https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm. Ainakin minun ja Laakerin ratkaisut käyttävät tätä ideaa.

Muistin, että tällainen yksinkertainen jippo on olemassa, mutta minulta meni kuitenkin pari tuntia sen keksimiseen uudestaan. Ehkä ensi kerralla se palautuu mieleen nopeammin...

D:n ratkaisut ovat yllättävän lyhyitä. Kokeilin ratkaista paria tapausta käsin ja tuotokseni olivat selvästi huonompia.

jlaire kirjoitti:

Muistin, että tällainen yksinkertainen jippo on olemassa, mutta minulta meni kuitenkin pari tuntia sen keksimiseen uudestaan. Ehkä ensi kerralla se palautuu mieleen nopeammin...

Joo mäkin muistin että jippo on olemassa, mutta en jaksanut alkaa etsiä/miettiä sitä :D

Itse tein ensin Pythonilla nopean ajatuksen jolla saikin 30 pistetä. Sitten koitin toista lähestymistapaa, jolla olisi saanut enää 10 pistettä. Koska ongelmana oli aikaraja, niin koitin vielä tehdä sen ekan ajatuksen C++ -versiona, mutta tämä ei parantanut tulosta. Eli vanha totuus että kielellä ei ole merkitystä, jos algoritmi on huono piti pintansa. Tuloksista tosin näen että C++ toteutuksella vain 3 testiä feilasi, kun Pythonilla 7 testiä feilasi. Jänniittävästi C++ -testeistä opin myös että jos tulee eri voi tulla eri tyyppisiä virheitä (itsellä TIME LIMIT ja RUNTIME ERROR) mutta vain yksi näistä palautetaan kilpailua suorittaessa.

Itselläni meinasi jäädä koko C-osa kokonaan tekemättä, kun jo A-kohdassa en meinannut älytä miksi "WRONG ANSWER". Tietenkin vikana oli tuo erityistapaus 1, jossa oikea vastaus ei ollut 0 komentoa, mutta kun en ensin tajunnut sitä niin etsin pitkään että mikä numero muka on laskettu väärin. No, tämä kenties oli harjoitus aiheesta että lue tarkasti tehtävänanto ja vastauksen validiussäännöt.

D:n tein lopulta vaan heittämällä A-tehtävään laatimani "sopivien kahden potenssien summa" ratkaisun, joka ilmeisesti oli monella muullakin se ensimmäinen ajatus, kun siellä oli aika monella muullakin silloin 43 pistettä D-tehtävästä. Muutamalla luvulla koitin keksiä ihan numeerisesti mikä olisi lyhyempi tapa. Ajattelin, että kenties satuin valitsemaan huonot numerot syötelistalta (sellaiset, joilla ei ole nopeampaa muuta tapaa) kun en keksinyt. Päätin sitten "luovuttaa" tuossa kohti, varsinkin kun en ollut tänä viikonloppuna ajatellut käyttää paljoa aikaa tähän. Nyt kun katsoin tuota optimipituuksien listaa, niin näköjään mistä tahansa luvusta olisi pitänyt keksiä reilusti lyhyempi tapa.

Sinänsä olisi mielenkiintoista tietää paljonko kukakin lopulta on käyttänyt aikaa tähän kilpailuun. Voin kuvitella että algoritmiguru käyttää 2 tuntia ja saa sataset kaikkiin ja sitten joku toinen hyvät pisteet saava käyttää vaikka 20 tuntia.