Keskustelu: Ohjelmointiputka: Putka Open 2020 kierros 5

Putka Open 2020 kierros 5 alkaa pian:

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

Kierros 5 alkaa pe 27.11. klo 18:00 ja päättyy su 29.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.

Kierros on päättynyt. Tulokset löytyvät täältä: https://cses.fi/343/scores/

Antti tiedottaa myöhemmin, mitä seuraavaksi tapahtuu.

Tässä on jälleen eräitä ratkaisuja.

A, HQ9+

Esoteerisesta kielestä on tehty esoteerinen tehtävä. Ratkaisun kannalta olennaista on, että komennolla H voi tulostaa yhden rivin ja komennolla 9 voi tulostaa 494 riviä. Lyhin ohjelma tietyn rivimäärän tulostamiseen sisältää siis mahdollisimman monta 9-komentoa ja tarpeellisen määrän H-komentoja. Komentojen määrät saadaan suoraan jakolaskulla.

B, Järjestys

Tehtävä ratkeaa nopeasti induktiolla. Käsitellään luvut suuruusjärjestyksessä. Kun on N tapaa järjestää lukujoukko J ja tähän lisätään edellisiä pienempi luku L, luvun voi lisätä M eri kohtaan: ensimmäiseksi tai minkä tahansa sellaisen luvun perään, että lukujen ero on enintään x. Aluksi N = 1 ja J = vain suurin luku, ja joka kierroksen jälkeen N kerrotaan M:llä ja J:hin lisätään L. Tehtävän esimerkin ratkaisu tapahtuu siis näin: Luku 3 voidaan asettaa 1 tavalla, koska se on aluksi ainoa luku. Luku 2 voidaan asettaa 2 tavalla: alkuun tai 3:n jälkeen. Luku 1 voidaan asettaa 2 tavalla: alkuun tai 2:n jälkeen (mutta ei 3:n jälkeen). Tapoja on siis 2 * 2 = 4.

C, Pyramidi

Kaksi xor-operaatiota samalla luvulla kumoavat toisensa (A xor A = 0) eikä laskujärjestyksellä ole merkitystä, joten tehtävässä kysytään käytännössä, mitkä syötteen luvut tulevat mukaan lopulliseen xor-lausekkeeseen.

Pascalin kolmion kukin luku kertoo, montako reittiä huipulta on kyseiseen kohtaan. Pyramidi on käänteinen versio tästä: jokainen luku kulkee kohti huippua useaa eri reittiä pitkin. Koska xor-operaatio kumoaa itsensä, pitää siis laskea, onko reittejä parillinen vai pariton määrä eli onko Pascalin kolmiossa kyseisen syöteluvun kohdalla parillinen vai pariton luku. Tätä tarkoitusta varten kolmion rivistä N saadaan rivi N+2ⁱ bittisiirrolla ja xorilla: N xor (N << 2ⁱ). Esimerkiksi rivi 38 voidaan laskea seuraavasti:

rivi 1:   1

tavoite 38, puuttuu 37, hypätään on 2⁵ = 32, lasketaan N xor (N << 32)
rivi 33:  100000000000000000000000000000001

tavoite 38, puuttuu 5, hypätään on 2² = 4, lasketaan N xor (N << 4)
rivi 37:  1000100000000000000000000000000010001

tavoite 38, puuttuu 1, hypätään on 2⁰ = 1, lasketaan N xor (N << 1)
rivi 38:  11001100000000000000000000000000110011

tarkastus Pascalin kolmiosta: 1, 37, 666, 7770, 66045, 435897, ...

Koristeeksi kyseistä hauskaa kolmiota voi laskea Pythonilla vaikka näin:

r = 1
for i in range(40):
	print("{0:b}".format(r).replace("0", "."))
	r = r ^ (r << 1)

D, Alijonot

30 pistettä tuotti ahne algoritmi, jossa arvottiin tavoitteeksi vain jokin osajoukko syöterivejä ja valittiin aina seuraavaksi se merkki, joka mahdollisimman monessa syöterivissä olisi seuraavana vuorossa.

48 pistettä tuotti lyhyellä ajolla algoritmi, jossa Levenšteinin etäisyyden tyyppisesti (lisäys 1, poisto 0, korvaus mahdoton) kokeiltiin eri rivejä osaksi ratkaisua ja valittiin ahneesti (mutta hieman satunnaisuudella sotkettuna) lyhimmän ratkaisun tuottava seuraava rivi. Uuden ratkaisurivin saa koottua Levenšteinin etäisyyttä laskiessa. Itse asiassa jopa PHP:llä tehty prototyyppi pääsi lähes tähän tulokseen.

60 pistettä tuotti lyhyellä ajolla yllä kuvatun algoritmin optimointi niin, että joka lisäyksen jälkeen käytiin muodostettu ratkaisu läpi ja koetettiin, voisiko osan merkeistä poistaa huonontamatta tulosta.

100 pistettä jäi osaltani saavuttamatta. Aloin toteuttaa tämän artikkelin algoritmia, mutta ajanpuutteen takia se jäi kesken. Mietin myös erilaisia topologiseen lajitteluun liittyviä ideoita. Ehkä olisi pitänyt kokeilla myös silkkaa satunnaisuutta. Tehtävänannossa huolestutti kuitenkin syötteen tarkka satunnaisuus ja ongelman tunnettu NP-kova laatu, joiden takia arvioin, että eräät keksimäni viritelmät todennäköisesti eivät kuitenkaan toimisi, ja en sitten viitsinyt panostaa niiden kokeilemiseen. Toisaalta kierroksen voittaja on nähtävästi mahduttanut ratkaisuunsa tekstin OMISTANVOITONHATSUNEMIKULLE...LOL, joten ehkä huonompikin ratkaisu olisi yllättäen riittänyt.

Täysien pisteiden haltijat voivat mielellään kertoa ratkaisuistaan.

D:n ratkaisuprosessista:

55 pistettä irtosi pakkaamalla alijonoja suunnattuun syklittömään verkkoon (DAG), jossa solmuille on merkitty kirjaimet. Jokaiselle alijonolle on tarkoitus lisätä verkkoon jokin sitä vastaava polku. Alijonoa lisättäessä valitaan verkolle jokin sattumanvarainen topologinen järjestys (eli solmujen järjestys, jossa kaaret eivät mene taaksepäin), ja etsitään tämän ja lisättävän alijonon välillä lyhyin yhteinen merkkijono dynaamisella ohjelmoinnilla, kuten Metabolix kuvaili. Yhteisille merkeille ei sitten tarvitse luoda uusia solmuja.

Yritin jalostaa tätä ideaa eteenpäin siten, että verkosta etsittäisiin mahdollisimman suuria joukkoja solmuja yhdistettäväksi. Tähän löytyy suhteellisen tehokkaita algoritmeja, mutta idea tuntui silti liian ahneelta toimiakseen.

Lopulta turvauduin sitten simulated annealing -tekniikkaan. Ohjelma muokkaa 1000-merkkistä ratkaisua, ja katsoo kuinka paljon pidemmän alkuosan jokaisesta alijonosta se tällöin sisältää päättääkseen pidetäänkö muutos vai ei. Sattumanvaraisella merkin vaihdolla pääsi jo muistaakseni 60 pisteen paikkeille, kunhan ei yrittänyt sisällyttää kaikkia alijonoja. Tärkeämmäksi muutostyypiksi osoittautui vierekkäisten merkkien vaihto. Muutaman tunnin hienosäädön ja tuuletinpuhistelujen jälkeen löytyi 100p ratkaisu.

Oma ratkaisuni D:hen oli varmaan samantyylinen kuin tuo Metabolixin 60 pisteen ratkaisu.

50 pistettä:
Aloitetaan tyhjällä merkkijonolla A ja lasketaan jokaiselle käyttämättömälle syötemerkkijonolle, mikä on sen ja A:n lyhin yhteinen ylijono (shortest common supersequence). Tämä voidaan laskea O(nm) ajassa dynaamisella ohjelmoinnilla. Lyhin tulos valitaan ja muutetaan A joksikin tällaiseksi lyhimmäksi yhteiseksi ylijonoksi valitun syötemerkkijonon kanssa (Tasatilanteissa käytetään satunnaisuutta). Tätä toistetaan niin kauan kunnes A:n pituus ylittää tuhannen.

65 pistettä:
Kuten edellä, mutta joka vaiheessa poistetaan A:sta kaikki sellaiset merkit, jotka eivät vähennä sen alijonojen määrää.

100 pistettä:
Kuten edellä, mutta ei lopeteta tuhannen kohdalla, vaan mennään loppuun asti, kunnes kaikki syötteen merkkijonot ovat A:n alijonoja. Sitten A:sta aletaan poistamaan merkkejä ahneesti siten, että mahdollisimman moni alijono säilyy alijonona. Tätä toistetaan kunnes A:n pituus alittaa pituuden x (= 900, 950, 980 tms, säätelin tätä arvoa aina välillä). Tämän jälkeen aloitetaan alusta eli taas lisäillään puuttuvia alijonoja ahneesti. Tätä sykliä toistetaan kunnes merkkijonon pituus on max 1000 ja kaikki syötemerkkijonot ovat sen alijonoja. Minulla se kesti useampia tunteja.

Noin 50p tuli edellä mainitun editointietäisyyden laskemisen avulla.

Naiivina parannuksena tähän oli turhien merkkien poistaminen, sekä merkkijonon lajitteleminen bubblesort muistuttavalla tekniikalla. Merkkijonoa lajitellaan vuorotellen kasvavaan ja laskevaan leksikografiseen järjestykseen sellaisilla swapeilla ettei alijonojen määrä kuitenkaan laske, ja aina välillä poistetaan turhia merkkejä, joiden poisto ei vähennä sisällettyjen alijonojen määrää. Kun merkkijonosta tulee tarpeeksi lyhyt, lisätään uusia merkkejä editointietäisyyden avulla. Tätä toistamalla parametreja muuttelemalla pääsi noin 85p asti, pieniä parannuksia tuli kuitenkin koko ajan, joten tälläkin olisi ehkä saanut 100p jos olisi antanut koodin pyöriä tarpeeksi pitkän ajan.

100p ratkaisussa bubblesorttiin lisätään satunnaisuutta niin, että noin 90% swapeista skipataan kokonaan, jolloin "lajittelu" ei jää liikaa jumiin kahden tietyn järjestyksen välille. Myöhemmin osoittautui että antamalla pelkästään merkkijonon joka sisältää merkit A..Z 100 kertaa peräkkäin, lyhentää ohjelma merkkijonon alle 1000 merkin reilusti alle minuutin, ja sitäkin lyhyemmäksi jos jättää ohjelman pyörimään.

Hienoja tehtäviä oli taas! Mukava, että on aina joku helpompi lämmittelytehtävä alussa, että pistetilin saa avattua ... :) Itselleni mielenkiintoisin oli Pyramidi, joka pitkän pohtimisen jälkeen avautui, kun huomasin, että 3, 5 ja 9 korkean pyramidin huippu määräytyy alimman rivin nurkkien XOR -kaavalla! Tuosta oikea, riittävän nopea (jopa javalla), ratkaisu syntyikin nopeasti ...

12 kovaa kärjessä! kluopaja valitettavasti missasi yhden kierroksen. Muutoin hänkin olisi voinut olla aivan kärkijoukon tuntumassa.

Epävirallisten laskujeni mukaan kaikille kierroksille olisi osallistunut 17 henkilöä.

ArktinenKarpalo kirjoitti:

100p ratkaisussa bubblesort ... merkit A..Z 100 kertaa peräkkäin ...

Pahus, meinasin tehdä suunnilleen saman, mutta ajattelin sitten, ettei noin yksinkertainen ratkaisu voi olla oikea, joten käytin rajallisen ajan muihin ideoihin.