Tässä tulee uusi putkaposti:
https://www.ohjelmointiputka.net/postit/tehtava.
Kuinka nopeita ratkaisuja (sekunneissa ja O-merkinnöin) keksitte tehtävään?
Lisätehtävä: Uolevi päätti säveltää teokseen vielä 11. osan, jossa ei saisi olla yhtään mahdollista kertausjaksoa. Kuinka monta säveltä tässä osassa voi olla korkeintaan? Vai rajoittaako kertausjaksojen kieltäminen mitenkään osan pituutta?
En oikein älynny miten vastaus lähetetään.
Tehtävässä ilmeisesti pyydetään vain yhtä (pisintä) kertausjaksoa, vai kuinka? Olisihan mielenkiintoista selvittää, kuinka pieneen tilaan koko sävellyksen saa, jos kaikki mahdolliset kertausjaksot (ei tietenkään päällekkäisiä) hyödynnettäisiin.
Triviaali ratkaisu on tietenkin O(n^3), sen luulisi olevan lähes kaikille aivan selvä.
Edit. Siis O(n^3) on se täysin triviaali, O(n^2) voidaan johtaa tästä varsin helposti.
Kyllä, tehtävänä on etsiä jokaisesta sävellyksen osasta yksi mahdollisimman pitkä kertausjakso. Tehtävä siis muistuttaa viime syksyn Datatähti-alkukilpailun palindromitehtävää, mutta peilauskohdan sijasta etsitään toistokohtaa.
Ehdottamasi tehtävä (useampia kertausjaksoja) on kyllä kiinnostava, ja se sopii tämän tehtävän toiseksi lisätehtäväksi.
Koitin avata geditillä tuota tiedostoa 10.txt ja se näytti pelkkää roskaa. Taisin löytää bugin geditistä.
Joo, yritin työntää tuonne vastausta, jossa oli kaikkien kappaleiden kaikki kertausjaksot ja ihmettelin kun ei kelvannut. No, rupesin sitten tulosjoukosta kaivamaan käsipelillä että mikä voisi olla vikana ja kokeilin lähettää vain parista ekasta pisimmät, niin johan hulahti läpi. Sitten tulinkin jo tänne kysymään selvennystä, mutta eipä tarvinnut kysyä, kun Metabolix oli jo ehtinyt. :D
Tein nyt aluksi tuollaisen melko triviaaliratkaisun. Tehtävä ratkesi noin puolessa tunnissa. 5 oli aika patologinen tapaus, mutta muut oli huomattavasti helpompia. On mulla pari ideaa nopeammankin ratkaisun tekoo, mutta niiden toteutukseen menee taas enemmän aikaa kuin tuon triviaaliratkaisun suorittamiseen.
Kahdeksan helpointa vievät yhteensä reilut kymmenen sekuntia triviaalilla O(n^3)-algoritmilla ja saman verran O(n^2):lla. (Vai optimoiko kääntäjä ne samaksi? ;)
Viides oli aika murheenkryyni kyllä, en sitä koskaan täydellisesti ruksuttanut läpi. Mutta vastaukseksi kelpaa mikä tahansa on se sitten saatu keinolla millä hyvänsä :P
User137: Heh, taidettiin tehdä se samalla tavalla.
Käyttämäni algoritmi on minusta luokkaa O(n^3). Taisin missata jotain itsestäänselvää tai sitten en vaan osaa laskea noita oikein.
Minulla menee enemmän aikaa tuossa 10. kuin 5:ssä. 5:ssä meni 390 sekuntia VB6:lla. Samalla logiikalla uskoisin pääsevän alle minuutin esim VB.net 2005:llä kun siinä voi käyttää helposti 64-bittisiä kokonaislukuja. Tosin 32-bittisilläkin onnistuisi komeasti jos huomioisi, että noissa hankalimmissa taitaa olla pelkkää kahta "nuottia".
Noi ajat riippuu hyvin paljon käytetystä algoritmista, sillä tämän ongelman eri tehtävät on generoitu aika monipuoliksi ja erilaisiksi. Tein toisen algorimin joka on nopea, jos tehtävässä on vähän toistoa ja lyhyt kertausjakso. tällä algoritmilla 5 vei aikaa vain 0,8 s. Tosin 9 ja 10 veivät enemmän aikaa kuin triviaaliratkaisulla :)
Oma ratkaisu 1-10 vie yhteensä aikaa 39,641s kun jätetään 5 laskematta, sen ratkaisu kestäisi tuntemattoman kauan.
Onko datatähti 2008 kilpailua olemassa.
Pollapoju kirjoitti:
Onko datatähti 2008 kilpailua olemassa.
Ja tämä liittyy Putkaposti 25:een miten?
Eiköhän pullapoju viitannut tähän:
Antti Laaksonen kirjoitti:
Tehtävä siis muistuttaa viime syksyn Datatähti-alkukilpailun palindromitehtävää
Ja jos nuo aina syksyisin on, niin tuskin ainakaan julkisuudessa on vielä vuoden 2008 tehtäviä.
Datatähden alkukilpailu pidetään tosiaan aina syksyllä, mutta loppukilpailu ja sitä seuraavat valmennukset ja olympialaiset ovat vasta seuraavana vuonna. Tänä syksynä alkaa siis Datatähti 2009, joka päättyy kyseisenä vuonna.
Onko peruskoulusarjaa enään kun Voittajia listassa 2008 ja 2007 vuosia ei näy.
Kahtena viime vuonna peruskoulusarjaa ei ole ollut, ensi vuoden tilanne sen sijaan on vielä arvoitus.
:( nyt pitää lohduttaautua 8D
Nyt alkaa mun ratkaisu lähestyä datatähtitasoa :). 1.6s yhteensä kaikkien tehtävien suorittamiseen. Algoritmi taitaa olla luonteeltaan O(n*n/m) vai olisiko jopa O(n*log(n/m)), (m on pisimmän ratkaisun pituus). Tuo toimii suht nätisti myös tehtävillä, joissa on lyhyt pisin ratkaisu.
Itse en kyllä saa keksittyä edes miten tuollaiseen voisi päästä. Taitaa jäädä jotain itsestään selvää tajuamatta...
Kehtaatko heittää koodia ihmeteltäväksi? (sähköposti on profiilisivulla)
Keksin vähän paremman algoritmin ja toteutin sen C:llä.
$ gcc -O2 -Wall mpera.c $ time ./a.out [snip] real 0m0.264s user 0m0.244s sys 0m0.012s
Prosessorin taajuus on vajaa 1,5GHz. Rivejä on kaikkiaan 35, joista itse algoritmiä 15.
siis ei oo mitään muita oletuksia kuin tehtävässä annetut ja kaikki 10 tehtävää 1/4 s? Tuotakin koodia katsoisin mielelläni. Jos vaikka sais aivot pois jumista.
Ei mitään oletuksia. Kompleksisuudesta en osaa sanoa, koska tuo on oikestaan vain optimoitu versio triviaalista algoritmistä. Käytännössä se välttää paljon turhaa laskemista, mutta voi olla, että todella patologinen tapaus kestäisi pitkään.
Suunnilleen 0,20s menee viidenteen osaan ja 0,05s kaikkiin muihin.
Joo, käänsin tuon kielelle jolla itse noita tein ja silläkin menee vain noin 7 sekuntia koko roskaan. Selkeästi hitaampi siis kuin C:llä, mutta ei mitään verrattuna omaan algoritmiini.
Jep, itse näköjään vaan olin tehnyt turhaa työtä ja toteutukseni oli n^3 vaikka selvästikin n^2 oli riittävä. Ei vaan ollut tajunnut tuota yhtä itsestäänselvyyttä.. Yritin sitten erilaisilla monimutkaisilla keinoilla saada sitä nopeammaksi, vaikka oikea ratkaisu olisi ollut yksinkertaisempi.
funktion vastauksen perusteella olen tainnut itse tehdä vähän ylimääräistä hommaa. Mutta tulipahan keksittyä taas kaikenlaisia uusia jippoja :)
Kirjoitetaanpa nyt saman tien näistä ratkaisuista vähän juttua.
O(n^3)-aikainen ratkaisu xäl lxfvaxregnvfrfgv yäcv wbxn nybvghfxbuqnfgn wbxnvfra xregnhfwnxfba cvghhfinvugbruqba zhxnvfrfgv wbxnvfra wnxfbba xhhyhina zrexva. Gevivnnyrwn bcgvzbvagrwn bing gvrgraxva unxhwra enwbvggnzvara cnenfgn ghaargghn infgnhfgn cvgrzcvva xregnhfwnxfbvuva wn gnexvfghxfra ybcrggnzvara rafvzzävfrra iveurryyvfrra zrexxvva.
O(n^2)-ratkaisuun päästään, kun xälqääa wbxnvfgn xregnhfwnxfba cvghhggn xbugv yäcv xbxb xnccnyr frhenninyyn gninyyn: Wbf fäiryrg a wn a+x bing fnzng, xnfingrgnna zhhgghwnn, wbxn xregbb, zbagnxb creäxxävfgä fäirygä ba fbcvahg xregnhfwnxfbba, wn gnexvfgrgnna, baxb zääeä wb fnzn xhva xregnhfwnxfba cvghhf ryv ibvxb unxh wb cäägglä. Zhhffn gncnhxfrffn gnnf abyyngnna xlfrvara zhhgghwn, xbfxn iveurra wäyxrra lxfvxääa ivvzrvfvzzvfgä zrexrvfgä rv xhhyh xregnhfwnxfbba. (Tulipa huono selitys.)
Ohjelmaa voidaan edelleen optimoida niin, että nybvgrgnnaxva lyyä xhingha nytbevgzva gnexvfghf nvan xhaxva nyhrra ybchfgn. Wbf invxxncn ivvqraxlzzrara zvggnvfryyn xregnhfwnxfbyyn uninvgnna, rggä wnxfba xbyznaarxfv ivvzrvara fäiry rv gäfzää, ibvqnna fvveglä fhbenna gäzäa gäfzääzäggözäa fäiryra buv. Cvgxvra xregnhfwnxfbwra gncnhxfrffn zrargryzäa ulögl ba inygnin, xha rfvzrexvxfv xbuqnfgn lxfv nyxnina wnxfba wäyxrra ibvqnnaxva cääfgä wb cneva iregnvyha wäyxrra fhbenna ghunafvn fäiryvä cvgrzzäyyr, rvxä iäyvva wääarvgä gneivgfr gäyyä xvreebxfryyn xäfvgryyä ynvaxnna. Nytbevgzva cnenf gncnhf ba yvarnnevara, wbf flöggrra wbxnvara zrexxv ba revynvara. (Gbxv ba zhvgnxva gncnhxfvn.) Pahinta tapausta algoritmille en edes jaksa arvailla, joku muu voisi valaista tästä. On kuitenkin selvää, ettei tilanne voi olla pahempi kuin O(n^2).
Luulisin että suurimmat nopeuserot ei varmaankaan jälleen johdu käytetystä algoritmista vaan toteutuksesta ja teknisistä kikoista. Niistä haluisi tietää vähän enemmän ite, käytin vertailuun itse vaan tavun kokoisia numeroja per nuotti ja perinteistä yhtäläisyys vertailua. Kenties jotain jota voisi hyödyntää Delphillä?
Kokeilin itse uudenlaista algoritmia jolla korvasin 3 sisäkkäistä for-silmukkaa vain 2:lla mutta suoritusaika olikin 2x pidempi :/
User137 kirjoitti:
Luulisin että suurimmat nopeuserot ei varmaankaan jälleen johdu käytetystä algoritmista vaan toteutuksesta ja teknisistä kikoista.
Minä taas uskon sen olevan juuri päinvastoin. C-koodissani ei ainakaan ollut mitään kikkoja, vaan toteutin idean mahdollisimman yksinkertaisesti.
Tein saman huvin vuoksi Haskellilla (25 riviä, ajoaika 0,6s) ja Perlillä (10 riviä, ajoaika 32s). Selvästi huonompaa algoritmiä tuskin saisin optimoitua läheskään yhtä nopeaksi.
Itsekin yhdyn funktion näkemykseen. Funktion koodissa ei todellakaan ole mitään kikkoja ja ainoa ero omaan alkuperäiseen triviaaliratkaisuuni oli, että minä tyhmänä tarkistin n kertaa kunkin sävelen.
User137 kirjoitti:
Kokeilin itse uudenlaista algoritmia jolla korvasin 3 sisäkkäistä for-silmukkaa vain 2:lla mutta suoritusaika olikin 2x pidempi :/
Mainitsemani O(n^3)- ja O(n^2)-algoritmit toimivat yhteensä suunnilleen yhtä nopeasti, ero on vain noin 30% tuon teoriassa nopeamman hyväksi. Hyvin luultavaa on, ettei noiden lopullisessa suorituksessa oikeasti tuon enempää eroa tulekaan, kun kaikki silmukat päättyvät järkevästi silloin, kun on ilmeistä, ettei niistä ole enää hyötyä. Sen sijaan viimeinen kuvaamani algoritmi on selkeästi nopeampi, omalla koneellani (1,73 GHz) aikaa kului kaikkiin syötteisiin yhteensä 0,15 sekuntia. Koodi on tasoltaan ja kikattomuudeltaan aivan samanlaista kuin muissakin ratkaisuissa, eli ero tulee aivan varmasti algoritmista. Luitko rot13-selostukseni? Kokeilepa samaa Delphillä, tuloksen pitäisi olla aivan yhtä hyvä. Algoritmin toteutuksessa on jonkin verran sijaa virheillekin, joten jos tulos ei vakuuta, jokin on luultavasti pielessä.
Voin laittaa oman toteutukseni jossakin vaiheessa esille vaikkapa base64-enkoodattuna. Kiinnostaisi minuakin tietää, onko funktio ratkaissut tehtävän samalla tavalla vai onko tähän muutakin oivallettavaa.
funktion algoritmi (Grez forwardoi) toimii yleisesti O(nlogn)-ajassa . Tosin siinä käytetään pitkälti tuota sinun mainitsemaa kikkaa. Tai ehkä ymmärin selostuksesi väärin ja tuo on sama algoritmi, sillä en ymmärrä miten tuolla kikalla voit parhaassa tapauksessa löytää pisimmän ratkaisun lineearisesti. Funktion algoritmillakin saattaa olla yksittäisiä worst case tapauksia, jotka vievät O(n*n) verrattavan ajan (samoin kuin perus quicksort on n*n algoritmi valmiiksi järjestetylle listalle).
Luin Metabolixin selityksen uudestaan ajatuksen kanssa ja tuo optimoitu algoritmi taitaa olla aika tarkalleen sama, mitä itsekin käytin. Ajattelin tosin vähän eri tavalla, enkä keksinyt tuota O(n^2)-algoritmiä välissä.
yrg a = bfna cvghhf; x = rgfvggäiäa xregnhfwnxfba cvghhf
Bgrgnna rfvzrexvxfv a = 21; x = 5. Zvxäyv x:a zvggnvara xregnhfwnxfb ba byrznffn, fra infra chbyv ba wbaxha k:a cääyyä.
....k....k....k......
Xälqääa xnvxxv k:g yäcv wn xngfbgnna, yölgllxö fvvgä xbuqnfgn xregnhfwnxfbn.
yrg s(v) = (fäiry xbuqnffn v) == (fäiry xbuqnffn v + x)
Wbf s(k) ba rcägbfv, gäffä xbuqnffn rv fryiäfgvxääa ibv byyn xregnhfwnxfbn. Wbf fr ba gbfv, rgfvgääa rafvzzävfrg xbuqng k:fgä infrzznyyr wn bvxrnyyr, wbvffn s ba rcägbfv, wn avzrgääa ar y:xfv wn e:xfv. Wbf (e - 1) - (y + 1) >= x - 1, ba x:a cvghvara xregnhfwnxfb yölglalg, wn fr nyxnn xbuqnfgn y + 1.
En tiedä saako tuosta mitään selvää, ajatus ei oikein kulje kun ei ole nukkunut.
Pollapoju kirjoitti:
:( nyt pitää lohduttaautua 8D
Kerrotaan, että profeetat ovat jälkustäneet, että menneisyydessä Suuri Kananmuna Phug'Zwargurum-gurum-gurum-gurum jo ennen kuin sitä oli munittukaan vaikutti protoneutrofotonikvanttien maailmankaikkeutiseen liikesiirtymään niin että sarjat olisi yhdistetty. Nyt siis Lukion Pyhä Sarja ja Pyhä PerusSarja olisivat yksi sarja nimeltä Pyhä LukioSarja, johon kuuluvat kumpaisenkin sarjan jäsenet. Näin siis kahdesta on tullut yksi, molempia osallistujia hyvin tyydyttävä.
FooBat kirjoitti:
En ymmärrä miten tuolla kikalla voit parhaassa tapauksessa löytää pisimmän ratkaisun lineearisesti.
Esimerkiksi silloin, kun kappaleessa on vain yhtä säveltä. Tapaus lienee lineaarinen useimmille algoritmeille, jos ne vain aloittavat ratkaisun etsimisen suurimmasta vaihtoehdosta eli puolen kappaleen mittaisesta kertausjaksosta. Kahden tekstin vertailu vie luonnollisesti lineaarisen ajan, ja koska ratkaisu toimii ja on pidempi kuin mikään muu mahdollisuus, algoritmi on saman tien jo tehnyt tehtävänsä.
Metabolix kirjoitti:
Ohjelmaa voidaan edelleen optimoida niin, että ...
Jeps :D "Aikaa kului: 172ms (0,172s)" yhteensä laskettuna kaikki 10 tapausta putkeen. Meni hetki(ä) tajuta tuo idea.
Edit: 156ms kokonaisuus kun optimoin tiedostonkäsittelyn.
Metabolix kirjoitti:
FooBat kirjoitti:
En ymmärrä miten tuolla kikalla voit parhaassa tapauksessa löytää pisimmän ratkaisun lineearisesti.
Esimerkiksi silloin, kun kappaleessa on vain yhtä säveltä. Tapaus lienee lineaarinen useimmille algoritmeille, jos ne vain aloittavat ratkaisun etsimisen suurimmasta vaihtoehdosta eli puolen kappaleen mittaisesta kertausjaksosta. Kahden tekstin vertailu vie luonnollisesti lineaarisen ajan, ja koska ratkaisu toimii ja on pidempi kuin mikään muu mahdollisuus, algoritmi on saman tien jo tehnyt tehtävänsä.
No njoo, yksittäisissä tapauksissa moni algoritmi on O(1). Tämän algoritmin tuo ominaisuus voidaan paremminkin kuvata sanomalla, että se on luokkaa O(nlog(n/m)), jossa m on pisimmän ratkaisun pituus. Paras tapaus on tietenkin silloin kun ratkaisu on mahdollisimman pitkä (esim. kun kaikki sävelet ovat samoja).
Aihe on jo aika vanha, joten et voi enää vastata siihen.