Putka Open 2020 kierros 2 alkaa pian:
https://cses.fi/putka-open-2020/
Kierros 2 alkaa pe 25.9. klo 18:00 ja päättyy su 27.9. 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!
Aika haastavan tuntuisia ovat tämänkin kierroksen tehtävät! No varmaan jyvät ja akanat pitää jotenkin saada eroteltua :)
Ensimmäiseen tehtävään voisi ehkä tarkentaa, että kortteja ei välttämättä anneta syötteessä suuruusjärjestyksessä ...
On tosiaan vaikeita tehtäviä tällä kierroksella. Monessa tehtävässä jopa alkeellisen ratkaisun tekeminen vaatii tällä kertaa melko paljon vaivaa, ja tehokkaat ratkaisut ovat vaikeampia keksiä kuin viime kierroksella. Voin kirjoittaa näistä taas kierroksen päätyttyä.
Vähän tuli hölmö olo, kun omassa testiajossa ohjelma tuntuisi toimivan, mutta sitten kuitenkaan se ei anna yhtään pistettä :(
No varmaan koodissa on joku vika, yritin rakentaa rekursiota kolmanteen tehtävään (Summat). Rekursio on aina ollut itselleni hankala hahmottaa / hallita, joten ei tämä sinänsä ole yllätys, jos ei toimi.
Olisi mukava saada tietää, mihin testiin ohjelma kaatuu. Nyt "WRONG ANSWER" ei anna kovin paljon vihjettä, mikä menee vikaan. No ehkä kilpailun jälkeen tuota voisi vielä ihmetellä.
TapaniS kirjoitti:
Vähän tuli hölmö olo, kun omassa testiajossa ohjelma tuntuisi toimivan, mutta sitten kuitenkaan se ei anna yhtään pistettä :( – – Olisi mukava saada tietää, mihin testiin ohjelma kaatuu. Nyt "WRONG ANSWER" ei anna kovin paljon vihjettä, mikä menee vikaan.
Noin käy joskus, ja silloin joutuu vain kaivamaan vielä tarkemmin omaa koodia läpi tai tekemään tarpeeksi suuren määrän omia testitapauksia. Onneksi näissä tehtävissä on helppo tehdä itse syötteitä. Summat-tehtävässä myös oikea ratkaisu on luontevasti tiedossa (koska syötteet pitää kuitenkin generoida tehtävänannon mukaisesti). Muissa tehtävissä pitää vain tehdä pieniin tapauksiin niin idioottivarma ratkaisu, että voi tarkastaa tulokset sillä.
Jos epäonnistuneet testit näytettäisiin, ne voisi ratkaista valmiiksi ja sisällyttää valmiit vastaukset ohjelmaan. Ja toisaalta jos vain osa testeistä näytettäisiin, olisi taas sama tilanne, eli jokin muu testi saattaisi kuitenkin epäonnistua.
No joo, vikaa sieltä löytyi! Ja 12 pistettä rapsahti laariin! Wow!
Enää ei anna edes "WRONG ANSWER" vaan "TIME LIMIT EXCEEDED" eli rekursio kyllä toimii, mutta se on tehoton ja hidas. No kuitenkin hieno tunne, kun lähti toimimaan!
Metabolix kirjoitti:
Voin kirjoittaa näistä taas kierroksen päätyttyä.
Odotan innolla tehokasta ratkaisua torni tehtävään. Tuli upotettua useampia tunteja sen pohtimiseen. Veikkaan, että tehokas ratkaisu käyttää valmista laskukaavaa, tai dynaamista ohjelmointia.
Kierros 2 on nyt päättynyt ja tulokset ovat täällä:
Nyt CSES:n kautta näkee myös kaikki lähetykset ja testit.
Seuraava kierros järjestetään 16.–18.10.
Tämä kierros oli tosiaan vaikea, täysiä pisteitä tuli vain muutama. Tässä ovat keksimäni ratkaisut:
A, Kortit
Hidas ratkaisu käy läpi kaikki mahdolliset tavat omien korttien pelaamiseen. Nopea ratkaisu perustuu strategiaan, jossa joka kierroksella lyödään isoin kortti, jos se voittaa vastustajan kortin, tai muuten lyödään pienin kortti, kun hävitään kuitenkin. Käytännössä tämän voi toteuttaa seuraavasti: Tallennetaan taulukkoon kaikkien korttien kohdalle tieto, onko kortti oma vai vastustajan. Käydään kortit läpi isoimmasta pienimpään. Jos kortti on oma, nostetaan omien korttien laskuria. Jos kortti on vastustajan ja omia kortteja on vielä, vähennetään laskuria ja merkitään yksi voitettu kierros lisää. (Jos omia kortteja ei ole enää, ei tapahdu mitään. Pienen kortin lyömistä ei tarvitse erikseen toteuttaa.)
B, Torni
Ratkaisut perustuvat siihen, että tornissa on kaksi pinoa. Jos pinot ovat samalla tasolla, voidaan laittaa jokin kahden levyinen palikka, jolloin molempien pinojen korkeus muuttuu saman verran. Aina voidaan myös laittaa matalampaan pinoon jokin yhden levyinen palikka. Hidas ratkaisu käy kaikki mahdollisuudet läpi esimerkiksi rekursiolla.
En kokeillut, mutta luvuista päätellen keskimmäiseen portaaseen riittäisi jo se, että yksinkertaisen rekursion tulokset muistettaisiin. Tämä kannattaa opetella ihan rutiiniksi, tämähän vaatii käytännössä vain yhden ehtolauseen funktion alkuun ja yhden sijoituslauseen ennen funktion päättymistä.
Parempi ratkaisu ei tee pinoja erikseen vaan laskee koko tornia pätkissä: kun pinot ovat samalla tasolla, voidaan jatkaa tornia nolla tai useampia kerroksia vain yhden levyisillä palikoilla, ennen kuin laitetaan seuraava kahden levyinen palikka. Tällöin ei tarvitse käsitellä ollenkaan tilanteita, joissa pinot ovat eri tasolla, vaan rekursiossa pinot ovat aina yhtä korkeat. Voidaan erikseen laskea, monellako tavalla tietynlaisen pinon voi tehdä yhden levyisillä palikoilla, ja kahden pinon kohdalla tämä vaihtoehtojen määrä nousee toiseen potenssiin. Tämä ei vielä riitä vielä täysiin pisteisiin, mutta tälle olisi voinut olla tuloksissa oma portaansa.
Nopeaa ratkaisua varten pitää korvata rekursiossa olevat silmukat sopivilla summamuuttujilla; muuten tämä onkin triviaalia, mutta yhdessä silmukassa pitää huomata, että vain 1-levyisistä palikoista N-korkuisen tornin rakentamistavat kasvavat neljän potensseina.
Itse tein ensin tuon ei-ihan-riittävän ratkaisun ja muutin sitten rekursion silmukaksi (eli lasketaan järjestyksessä taulukoita torneille 1…N), minkä jälkeen optimoin sisäkkäiset silmukat summamuuttujiksi. Välivaiheita optimoinnista ei toki ole nähtävillä mutta alku ja loppu ovat. Optimointi olisi varmaan onnistunut myös rekursiivisessa muodossa, mutta ainakin minusta silmukkaa on helpompi käsitellä optimointivaiheessa. Harjoituksena voi yrittää toistaa optimointitemput tuolle koodilleni.
Rekursion muuttaminen silmukaksi tapahtuu yleensä niin, että funktion (tai tässä tapauksessa kaikkien rekursiivisten funktioiden) sisältö siirretään silmukkaan ja rekursiokutsun sijaan otetaan aikaisempi arvo taulukosta ja palauttamisen sijaan laitetaan uusi tulos taulukkoon. Pitää vain olla tarkkana, että arvot lasketaan oikeassa järjestyksessä, ettei käytetä taulukosta keskeneräisiä tuloksia.
C, Summat
Hidas ratkaisu käy läpi kaikki mahdolliset lukutaulukot ja tarkastaa, tuleeko niistä toivottu summataulukko. Keskimmäinen ratkaisu kokeilee kaikkia lukuja ratkaisun pienimmäksi, ja seuraava puuttuva luku saadaan aina, kun pienimmästä puuttuvasta summasta vähennetään aloitusluku. Jos seurauksena syntyy summia, joita ei pitäisi olla, ratkaisu on väärä ja pitää aloittaa alusta jollain toisella luvulla. Eri summien toivotut ja saavutetut määrät kannattaa tallentaa hajautustauluun (C++: unordered_map), jotta niitä on nopeaa ja helppoa käsitellä. Nopea ratkaisu tulee tästä pienellä parannuksella, nimittäin aloitusluvuksi ei tarvitse kokeilla kaikkia lukuja, vaan vaihtoehdot löytyvät summataulukosta: summataulukon pienimmät luvut ovat a+b ja a+c, ja jostain pienemmästä päästä löytyy myös b+c, jolloin ((a+b)+(a+c)-(b+c))/2 on ratkaisun pienin luku a. Koodini ei ole erityisen kaunis mutta löytyy tästä.
D, Planeetat
Joka planeetalla on yksi teleportti, eli toisin sanoen planeetat voidaan esittää taulukkona, jossa jokaisessa kohdassa 1…N on seuraavan planeetan numero eli 1…N. Tästä voidaan helposti todeta, että erilaisia yhdistelmiä on N potenssiin N eli todella paljon. Hidasta mutta hyväksyttävää ratkaisua tähän tehtävään en suoralta kädeltä keksi, koska jo pienin osatehtävä N=10 on niin iso, että kaikkien mahdollisten yhdistelmien kokeilu ei ole mahdollista.
Keskimmäinen ratkaisu perustuu kombinatoriikkaan. Planeettojen ja komponenttien määrän mukainen ratkaisu f(P,K) sisältää kolme eri tilannetta: Jos K=P, joka planeetalta pääsee vain itselleen ja vastaus on 1. Jos K=1, ratkaisu on P potenssiin P miinus kaikki muut ratkaisut K=2…P. Muissa tilanteissa käydään läpi jokainen mahdollinen komponentin koko M (väliltä 2…P-1). Komponenttiin valitaan M-1 planeettaa lopuista P-1 planeetasta, kombinaatioiden määrä on siis binomikerroin C(P-1,M-1). Komponentin sisäiset järjestykset löytyvät rekursiolla f(M,1). Loppuosan järjestykset löytyvät rekursiolla f(P-M,K-1). Lausekkeeksi tulee siis summa C(P-1,M-1)*f(M,1)*f(P-M,K-1) arvoille M väliltä 2…P-1. Ratkaisun voi tehdä rekursiolla ja välimuistilla tai suoraan järjestyksessä taulukkoon kokoamalla. Ratkaisua varten pitää toteuttaa tehokas potenssifunktio ja modulon kanssa toimiva jakolasku; näitä käsitellään Kisakoodarin käsikirjan luvussa Modulolaskenta. Tällä ratkaisulla lohkeaa tehtävästä 49 pistettä.
Täysiä pisteitä varten pitää luultavasti olla guru kombinatoriikassa tai syöttää saatuja tuloksia hakukoneeseen ja löytää kyseisten lukujen laskemiseen tunnettu ratkaisu ja toteuttaa se tehokkaasti modulolaskennan keinoin. Oma versioni löytyy tästä ja sisältää myös C++-funktiot potenssilaskuun ja jakolaskuun.
Metabolix kirjoitti:
Täysiä pisteitä varten pitää luultavasti olla guru kombinatoriikassa tai syöttää saatuja tuloksia hakukoneeseen ja löytää kyseisten lukujen laskemiseen tunnettu ratkaisu ja toteuttaa se tehokkaasti modulolaskennan keinoin.
Itse asiassa tehtävän voi ratkaista täysin pistein itse miettimällä ilman erityisiä tietoja matematiikasta.
Oma ratkaisuni muodostui kahdesta osasta, joista toinen osa muodostaa pelkät syklit ja toinen osa lisää sykleihin ulkoa tulevat polut.
Osa 1: Jos verkossa on n solmua ja k sykliä ja siihen lisätään uusi solmu, niin uusi solmu voi joko mennä osaksi jotain aiempaa sykliä (n tavalla), jolloin syklien määrä on edelleen k, tai sitten uusi solmu voi perustaa uuden syklin (yhdellä tavalla), jolloin syklien määrä on k+1.
Osa 2: Voidaan valita jäljellä olevista solmuista pienin ja etsiä siitä lähtien polku, joka johtaa lopulta sykleissä olevaan solmuun. Polkuun voidaan liittää solmun eteen jokin määrä muita jäljellä olevia solmuja. Tässä tulokseen vaikuttaa vain, montako solmua on jäljellä ennen polun muodostamista.
Molemmat osat voidaan toteuttaa ajassa O(n^2) dynaamisen ohjelmoinnin avulla, joten ratkaisu on riittävän tehokas, kun n=5000.
Mistä löytyy kisan yhteenveto (eri kierrosten yhteenlasketut tulokset)?
Tällä hetkellä ei mistään, mutta sellainen on kyllä tulossa.
Epävirallisia tuloksia keräsin tänne.
Laskujeni mukaan molemmille kierroksille osallistuneita olisi 25, jos nekin lasketaan mukaan, jotka ainakin yrittävät, mutta pisteitä ei kuitenkaan tullut.
Kärjessä on hyvin tasaista, ihan kaikki eivät päässeet molemmilla kierroksilla kisaan.
Antti Laaksonen kirjoitti:
Voidaan valita jäljellä olevista solmuista pienin ja etsiä siitä lähtien polku, joka johtaa lopulta sykleissä olevaan solmuun. Polkuun voidaan liittää solmun eteen jokin määrä muita jäljellä olevia solmuja. Tässä tulokseen vaikuttaa vain, montako solmua on jäljellä ennen polun muodostamista.
En saa tästä ajatuksesta kiinni. Voisitko selventää vielä?
Entä millaista ratkaisua ajattelit ensimmäiseen portaaseen (n=10)?
Tässä esimerkki:
Solmujen määrä on n=10 ja sykleihin on valittu k=4 solmua (oletetaan, että syklien solmut ovat 1, 3, 4 ja 8).
Pienin solmu jäljellä olevista on 2 ja tästä solmusta täytyy jotenkin olla polku sykliin. Polulla on vähintään 1 solmu ja enintään n-k solmua. Jos polulla on 1 solmu, polkujen määrä on k, jos on 2 solmua, polkuja on k*(n-k-1), jos on 3 solmua, polkuja on k*(n-k-1)*(n-k-2) jne.
Oletetaan, että valitaan polku 2->7->4. Nyt myös solmut 2 ja 7 on kiinnitetty sykleihin, joten sykleihin on valittu k=6 solmua.
Tämän jälkeen jatketaan prosessia valitsemalla taas seuraava polku pienimmästä jäljellä olevasta solmusta alkaen (tässä solmu 5). Oleellista on, että polkujen määrään vaikuttaa vain jäljellä olevien solmujen määrä eikä se, montako sykliä on tai miten solmut on liitetty sykleihin.
Tapaukseen n=10 ajattelin joko optimoitua raa'an voiman algoritmia tai sitten ratkaisua, johon on kovakoodattu hitaammalla algoritmilla lasketut tapausten 1–10 tulosteet (koska on vain 10 tapausta ja vähän tulostetta, niin onnistuu hyvin).
Kiitos selityksestä, Antti! Hauskaa, miten eri kaavoilla pääsee samaan tulokseen. Itse nimittäin pääsin nyt tuohon siten, että jokaiseen syklissä olevaan solmuun liitetään jokin määrä muita solmuja, ja näiden solmujen mahdolliset järjestykset saadaan Cayleyn kaavalla (nⁿ⁻²).
Seuraavaa erää odotellessa onkin hyvä harjoitella Datatähden tehtävillä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.
