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ännittävästi C++ -testeistä opin myös että 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 kolmoskierros 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. Ja toki se ilmeisen oikea ajatus kävi mielessä, että kertolaskua käyttämällä voisi saada merkittävää lyhentymistä.

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.

Statistiikoissa C++ dominoi, mutta Text oli tällä kertaa yllättävän vahva :D

Ensimmäinen kierros kun vain yksi sai täydet pisteet.

D:ssä tosiaan 2:n potenssien summa -algoritmi on yllättävän kaukana optimista, vaikka sitä intuitiivisesti pitäisi ihan hyvänä.

Koodasin bruteforcen aluksi ihan vain tukemaan parempien heuristiikkojen keksimistä, kun en keksinyt mitä parantaa heuristisessa ratkaisussa ja oletin ettei brute mitenkään voi olla riittävän nopea. Luku 9 on ensimmäinen jossa helppo ratkaisu on epäoptimaalinen koska se on parempi laskea 3*3, mutta neliöjuuri on toki helppo lisäys. Sen sijaan jo luvun 11 optimiratkaisu (esim. DD+SO+D*+) on sen verran monimutkainen, että en keksinyt siihen auttavaa heuristiikkaa.

C oli käytännössä identtinen erään puolalaisen ohjelmointikilpailun tehtävän (CSES:ssä) kanssa, joten osa varmaan tunsi tehtävän sitä kautta.

D yritin leveyshakua, mutta RAM loppui kesken. Käytin sen sijaan baselinena kakkosen potenssi -lähestymistapaa ja sitten haeskelin satunnaisalgoritmilla parempia: http://paste.dy.fi/sxr

Intuitiona oli se, että sadalla syötteellä satunnaisohjelmatkin saattavat kohtuullisen hyvällä todennäköisyydellä parantaa ainakin jotain instansseista.

C: yritin aluksi soveltaa persistenttiä segmenttipuuta, johon on merkitty jokaiselle taulukon prefixille [1..p] kuinka monta kertaa kukin luku x esiintyy. [a, b] väliltä voidaan sitten tarkistaa kuinka monta kertaa luku x esiintyy laskemalla persistent(x, b) - persistent(x, a-1) eli toisin sanoen "kuinka monta kertaa x oli merkattu kohtaan b mennessä" - "kuinka monta kertaa x oli merkattu kohtaan a-1 mennessä".

Ongelmaksi muodostuu: miten valita x? Tähän oli intuitio, että jos x dominoi, se esiintyy reilusti välillä [a, b] ja siten satunnainen poiminta löytää sitä vähintäänkin lähes eniten. Haen 25 kertaa jonkin indeksin ja sitä vastaavan luvun väliltä [a, b] satunnaisesti (en ota toistamiseen käytettyä indeksiä) ja pidän kirjaa mitkä luvut esiintyivät eniten. Kokeilen sitten ainoastaan eniten ja toiseksi eniten esiintynyttä lukua. Persistentti vaikutti olevan tähän hieman liian hidas riippumatta optimoinneistani, joten käytin C++ STL:n pbds 'inxeded set'- tietorakennetta, jonka avulla voin toteuttaa saman kyselyn ilman persistenttiä puuta. Tässä linkki aiheeseen: https://codeforces.com/blog/entry/11080 : "find_by_order() and order_of_key(). The first returns an iterator to the k-th largest element (counting from zero), the second — the number of items in a set that are strictly smaller than our item."

D: käytin leveyshakua loppua kohden, mutta taisin pitää liian suurta pinoa (7 lukua kerrallaan). Hyödynsin myös sitä lähestymistapaa, että luvuilla [2, 3] voi luoda minkä vain luvun, ja koska BFS oli laskenut lyhyet tapaukset auki (esim. 2000 asti), pystyin laskemaan testejä halkomalla ne tekijöihin.

Esim testi: 156798 koostuu alkulukutekijöistä [2, 3, 3, 31, 281], joka voidaan jakaa osiin (2*3*3*31=558) ja (281). Nyt ohjelma laskee

optimal23(558) = "jos lähdetään tilasta [2, 3], miten päädytään optimaalisesti tilaan [2, 3, 558]?"

optimal23_consumed(281) = "jos lähdetään tilasta [2, 3], miten päädytään optimaalisesti tilaan [281]?"

Nuo ratkaisut voivat nyt helposti yhdistää, koska ensimmäisen jälkeen ROT ROT vie tilaan [558, 2, 3] ja sitten kun toisen suorittaa niin pinossa on [558, 281] ja voidaan vain kertoa yhteen.

Jos testissä on iso alkuluku (niitä voi olla enintään 1), kuten luvussa

300372: [2, 2, 3, 25031]

voidaan katsoa mikä olisi pienin luku mikä miinustaa jotta siitä saadaan luku jolla on hallittavat tekijät.

25031 - 2 = 25029 => [3, 3, 3, 3, 3, 103]

-> hyvä! muodostetaan tuo siis samalla tekniikalla, ja lisätään 2 tuohon lukuun niin saadaan 25031 muodostettua.

D:ssä ainakaan komentoa DROP ei tunnu tarvitsevan koskaan, koska ei tunnu hyvältä laittaa pinoon lukua, jota ei käytetä tuloksen laskemiseen. Mutta tarvitaanko myöskään komentoa SWAP?

En ole löytänyt mitään tilannetta, jossa komennon SWAP avulla saisi lyhyemmän ratkaisun kuin toteuttamalla ohjelman ilman sitä. Lisähaaste tehtävään onkin etsiä tällainen tilanne tai todistaa, ettei tällaista tilannetta esiinny koskaan.

Grez kirjoitti:

Jännittävästi C++ -testeistä opin myös että voi tulla eri tyyppisiä virheitä (itsellä TIME LIMIT ja RUNTIME ERROR), mutta vain yksi näistä palautetaan kilpailua suorittaessa.

Jos tietyn osatehtävän testeissä tulee erityyppisiä virheitä, näistä tosiaan näytetään vain yksi kilpailun aikana. Näytettävä virhe on se, joka tulee ensimmäisenä testien järjestyksessä.

Kuha kirjoitti:

C oli käytännössä identtinen erään puolalaisen ohjelmointikilpailun tehtävän (CSES:ssä) kanssa, joten osa varmaan tunsi tehtävän sitä kautta.

Hyvä havainto, itse en muistanut että tällainenkin tehtävä on CSES:ssä.