Keskustelu: Ohjelmointiputka: Putka Open 2025 kierros 4

Putka Open 2025 kierros 4 alkaa pian:

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

Kierros 4 alkaa pe 7.11. klo 18:00 ja päättyy su 9.11. 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!

Taistelu finaalipaikoista on erittäin tiukka: https://www.ohjelmointiputka.net/kilpailut/2025-putka-open/yhteistulokset.php

A, Lista. Luvut pitää järjestää sen mukaan, montako kertaa niitä kysytään.

B, Huippualkio. Yksi tapa on seuraava: Tutkitaan ensin keskimmäinen luku. Se on ensimmäinen ehdokas huippualkioksi. Lasketaan, kummalla puolella ehdokasta on leveämpi tuntematon alue. Tutkitaan sen alueen keskimmäinen luku. Jos luku on ehdokasta suurempi, siitä tulee uusi ehdokas huippualkioksi. Näin ehdokas on aina vähintään sama kuin lähimmät tunnetut luvut, ja algoritmi päättyy, kun viereiset luvut tunnetaan. Alue puolittuu 1-2 kyselyllä.

C, Muutokset. Kuten A, mutta tieto pitää pystyä laskemaan kaikille listan alku- ja loppuosille nopeasti. Kun luvut ovat oikeassa järjestyksessä aiemmille kyselyille, uuden kyselyn lisäys käy seuraavasti: siirretään kysytty luku ensimmäiseksi niistä, joilla on sama määrä kyselyitä ennen uutta kyselyä, jolloin se on myös viimeinen niistä, joilla on sama määrä kyselyitä uuden kyselyn jälkeen. Kun pidetään yllä taulukkoa indekseistä, mistä löytyy mikäkin luku ja mistä alkavat kunkin lukumäärän luvut, tilan päivitys onnistuu muutamalla siirrolla. Koko ratkaisun saa, kun käy kyselyt läpi etuperin ja takaperin ja summaa näin saadut listan alkupään ja loppupään kustannukset. (Olisi mahdollista myös toteuttaa em. siirto takaperin ja ylläpitää samaan aikaan alku- ja loppuosan tuloksia.)

D, Merkkijonot. 18 pisteen ratkaisu onnistuu rekursiolla. Joka merkin i kohdalla asetetaan tähän leiman merkki j ja valitaan sitten jatkotapa: Jos merkki on leiman viimeinen, seuraavaksi paljastuu jokin osa alempaa leimaa (i+1,x kaikille pituuksille 1..m). Jos ei ole viimeinen, vaihtoehtona on jatkaa tätä leimaa (i+1,j+1) tai aloittaa päälle uusi leima (i+1,0). Ennen uuden tai paljastuvan leiman aloitusta pitää tarkistaa, mahtuuko leima alueelle kokonaan. Jos päästään merkkijonon loppuun, tulos kelpaa. Saman merkkijonon voi tehdä eri tavoin, joten täytyy pitää kirjaa, mitkä on jo nähty. Nopeammat ideat kaatuivat siihen, että leimassa voivat toistua samanlaiset osat ja leiman osia pystyy muodostamaan lyhyempiä alku- tai loppupaloja yhdistelemällä. Tuloksista päätellen ehkä olisi ollut erottevampaa laittaa mukaan osatehtäviä, joissa jokainen merkki esiintyy leimassa enintään kerran.

D: Jos yrittää laskea n-pituisten merkkijonojen määrää päättämällä eksplisiittisesti leimasinten paikkoja, päätyy Metabolixin kertomaan ongelmaan että monet merkkijonot voi generoida usealla tavalla. Sen sijaan parempi on generoida taulukko merkki kerrallaan, ja joka kohdassa kokeilla kaikille kirjaimille a-z voisiko se olla osa validia ratkaisua.

Dynaamisen ohjelmoinnin ratkaisu on kirjoittaa ratkaisu muotoon dp[n,k]=sum(dp[n-1,...]), missä n on generoitavan merkkijonon pituus ja tila k kertoo osittaisen ratkaisun viimeiset merkit. Käytin tiloina leimasimen prefiksejä ja suffiksipuun solmuja, jotka kertovat pisimmän mahdollisen leimasimen osan jota nyt saatetaan olla rakentamassa. Mahdolliset siirtymät tilojen välillä voi esilaskea, jolloin ratkaisusta tulee melko tehokas.

DP-ratkaisu on helposti muutettavissa matriisipotenssiksi, mutta suffiksipuussa on s=O(m^2) solmua joten potenssilasku O(s^3 log n) saattaa käydä liian hitaaksi. Tilojen määrää voi vähentää yhdistämällä tilat joista on identtiset siirtymät muihin tiloihin. (Vaihtoehtoisesti voi ajaa dp-algoritmia vähän matkaa ja sitten käyttää Berlekamp–Massey-algoritmia, mutta se mahdollisuus unohtui minulta kunnes näin jlairen ja Laakerin ratkaisut.)

D

Koodissani rakenteen dp[n][mask] toinen indeksi kuvaa joukon {0...m} osajoukkoa ja kertoo, kuinka monta merkkiä keskeneräisestä leimauksesta voi olla jäljellä.

Esimerkiksi leimasimella "ababc" merkkien "abab" jälkeen voimme olla joko kohdassa "abab|c" tai "ab|abc", joten maski on (1<<1) | (1<<3).

Erikoistapauksessa mask&(1<<0) "keskeneräisestä" leimauksesta voi olla jäljellä 0 merkkiä. Tämä tarkoittaa, että leimasin on tähän asti generoidun merkkijonon suffiksi. Nyt on mahdollista, että seuraavan merkin kohdalla alta paljastuu osittain peitossa ollut leimaus, joten tästä tilasta voidaan siirtyä mihin tahansa tilaan {0...m-1}.

Kaikki alkutilanteesta saavutettavat maskit ja niiden väliset siirtymät olisi voinut generoida eksplisiittisesti matriisiin, mutta tavoitteenani oli ratkaista vain riittävästi arvoja Berlekamp–Masseylle ja tähän riitti naiivi purkkatoteutus DP:stä.

(Leimasimen generoimat merkkijonot muodostavat säännöllisen kielen, ja tämän DP:n mask-parametrin voisi tulkita klassisena NFA->DFA -reduktiona. Tehtävän miettiminen muistutti minua hieman Käänteislausekkeesta, mutta tämä kertoo ehkä enemmän minusta kuin ko. tehtävistä...)

Nopeimpien C-ratkaisujen ajoaika on alle 10 ms, mutta tämä ei näy statistiikoissa https://cses.fi/597/stats/.

jlaire kirjoitti:

Nopeimpien C-ratkaisujen ajoaika on alle 10 ms, mutta tämä ei näy statistiikoissa https://cses.fi/597/stats/.

Missä ratkaisuissa näin? Huomaa, että tuossa otetaan huomioon vain viimeisimmät 100p lähetykset kisan aikana.

Ohoh nvm, katsoinkin vääriä tuloksia.

jlaire kirjoitti:

(Leimasimen generoimat merkkijonot muodostavat säännöllisen kielen, ja tämän DP:n mask-parametrin voisi tulkita klassisena NFA->DFA -reduktiona. Tehtävän miettiminen muistutti minua hieman Käänteislausekkeesta, mutta tämä kertoo ehkä enemmän minusta kuin ko. tehtävistä...)

Tämä on kyllä hyvä huomio. Mietin tehtävää aivan turhan vaikean kautta, kun olisi riittänyt todeta että kyseessä on säännöllinen kieli ja loppu onkin varsin mekaanista työtä.

Sisuaski kirjoitti:

Sen sijaan parempi on generoida taulukko merkki kerrallaan, ja joka kohdassa kokeilla kaikille kirjaimille a-z voisiko se olla osa validia ratkaisua.

Kiitos, tällä jälkiviisaasti katsoen ilmeisellä idealla ratkaisu olikin yksinkertainen: https://cses.fi/597/result/15289549/

Eikä tarvinnut tuntea edes Berlekamp–Masseyta.