Keskustelu: Ohjelmointiputka: Putka Open 2020 kierros 3

Putka Open 2020 kierros 3 alkaa pian:

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

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

Ensimmäisen tehtävän esimerkissä taitaa olla pieni virhe:

Tuloste
2
1 4
2 4

Pitäisi olla:
2
1 2
2 4

TapaniS: esimerkki on oikein, tulosteessa ilmoitetaan indeksit eikä lukuja.

2 4 3 1
*     * = 1 4
1 4 3 2
  *   * = 2 4
1 2 3 4

No niinpäs olikin! Vaan tuntuu silti olevan liian paha tehtävä ratkaistavaksi. No ehkäpä vielä jokin kaunis ajatus syttyy kenties ... Joskus alitajunta työskentelee jopa nukkuessammekin! :)
----
Edit: Jo syttyikin idealamppu! Uuden yrityksen vielä ehkä ehtii tekemään! :)

Täytyy kyllä sanoa, että tässäkin jälleen osatehtävät tuntuvat omituisilta. Esimerkiksi C (Kyselyt) olisi mahdollista ratkaista monella viritelmällä, joille ensimmäinen osio olisi helppo mutta jo toinen osio mahdoton lukujen ja kyselyiden suuren määrän takia, ja toisaalta toisen ja kolmannen osion välinen ero olisi useimmissa ratkaisuissa epäolennainen. Vastaavasti D (Numerot) antaa aika helposti toisen osion pisteet, mutta algoritmin parantaminen miljoonasta miljardiin ei tuota lisäpisteitä, vaan pitäisi suoraan päästä triljoonaan asti.

Jep, taas tuntui toimivan kotitestissä hyvin, mutta "WRONG ANSWER" kisakoneessa!

Pisteet on tiukassa ja voikin hyvin röyhistää rintaa, jos saa pisteitä kasaan! Yleensä eka tehtävä kai on ollut vähän helpompi, mutta nyt ainakin omalla kohdalla tuo toinen tehtävä onnistui, mutta eka ei.

Hiukan jäi mietityttämään, olisiko pitänyt saada pienin mahdollinen määrä operaatioita eka tehtävässä. Nyt vaan yritin löytää jonkin ratkaisun.
---
Edit:
Wow! Pieni vika löytyi ja 35 pistettä rapsahti laariin!! Nyt jubileeraa!!

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

Seuraava eli neljäs kierros on 6.–8.11.

Tässä on jälleen eräitä ratkaisuja. Vieraiden termien ja algoritmien selityksiä löytyy jälleen Kisakoodarin käsikirjasta.

A, Vaihdot

Tavallisesti listan voi järjestää niin, että joka kohdassa etsitään kyseiseen kohtaan kuuluva luku ja vaihdetaan se oikeaan paikkaan. Vaihtoja tulee siis enintään N-1, missä N on listan koko. Algoritmin nimi on valintalajittelu (selection sort).

Tässä tehtävässä lisähaasteena on, että ei saa vaihtaa vierekkäisiä lukuja. Toisaalta on annettu normaaliin nähden viisinkertainen määrä vaihtoja käyttöön. Tehtävä ratkeaa, kun vain keksii vierekkäisten lukujen vaihtoon oikeat temput, jotka ovat seuraavat:

B A ... N  | A ja B pitää vaihtaa, valitaan apukohta 1 tai N tilanteen mukaan.
N       B  | 1: Siirretään B apukohtaan.
  B     A  | 2: Nyt voidaan vaihtaa A ja B.
A       N  | 3: Siirretään N takaisin.
A B ... N  | A ja B vaihdettiin, N on ennallaan.

1 3 2 4  | Keskimmäiset täytyy vaihtaa neljän luvun taulukossa.
2   1    | 1: Siirretään keskimmäiset reunoihin.
  4   3  | 2: ==
3     2  | 3: Nyt voidaan vaihtaa, kun luvut ovat reunimmaisina.
1   3    | 4: Siirretään reunoilta takaisin keskelle.
  2   4  | 5: ==
1 2 3 4  | Keskimmäiset vaihdettiin, reunimmaiset ovat ennallaan.

Kahden luvun taulukossa ei voi tehdä mitään vaihtoa, ja kolmen luvun taulukossa voi vaihtaa vain päätyluvut keskenään, joten näissä taulukoissa ratkaisua ei aina löydy.

Tässä on oma versioni.

B, ABC-poisto

Lopputilanteessa merkkijonoon jää vain yhtä merkkiä. Loogisesti voidaan todeta, että parempaa tulosta varten kyseistä merkkiä olisi pitänyt poistaa enemmän. Ongelman välttämiseksi kannattaa siis poistaa merkkijonosta aina sitä merkkiä, jota on eniten.

Huomataan, että merkkien järjestyksellä ei ole väliä, vaan ratkaisu riippuu merkkien määristä. Jos kahta muuta merkkiä on yhteensä vähemmän kuin runsainta merkkiä, kaikkia ei saada poistettua ja erotus jää jäljelle. Muussa tapauksessa saadaan kaikki poistettua, paitsi jos merkkejä on pariton määrä, jolloin yksi jää aina jäljelle.

Tässä on oma versioni.

C, Kyselyt

Tehtävässä puhutaan hämäävästi operaatioista. Kysymyksen voi muotoilla toisin: Käydään läpi luvut taulukon väliltä A–B, pidetään kirjaa suurimmasta tähän mennessä nähdystä luvusta, ja jokaisen luvun kohdalla ”operaatioiden määrään” lisätään nykyisen luvun ja suurimman nähdyn luvun erotus. Jatkossa käytän operaatioiden määrästä sanaa hinta.

Jokin luku (kohdassa C) on aina lukuvälin suurin. Tämän luvun ja kohdan selvittämiseen voidaan rakentaa binääri-indeksipuu (Fenwick-puu), jolloin tietyn välin maksimi löytyy logaritmisessa ajassa.

Suurimman luvun jälkeisen alueen hinta selviää siten, että jokainen myöhempi luku pitää nostaa suurimman luvun tasoon. ”Operaatioita” kertyy siis lukujen määrä kertaa suurin luku miinus loppuosan lukujen summa. Jotta tämä saadaan nopeasti laskettua, tarvitaan luvuista summataulukko, joka on helppo koota suoraan samalla, kun lukuja luetaan.

Suurinta lukua edeltävän alueen hinta on sama kuin hinta alueen alusta taulukon loppuun miinus hinta suurimmasta luvusta taulukon loppuun. Tällainen hintataulukko täytyy erikseen koota lopusta alkuun päin. Kokoaminen toimii näin: Pidetään muistissa, montako kappaletta mitäkin lukua on loppupuolella. Joka luvun kohdalla korotetaan myöhemmät tätä pienemmät luvut tähän tasoon (ja lisätään hintaan kyseinen korotus) ja lisätään sitten tämä luku muistiin. Tämän prosessin aikavaativuus on O(N log N), koska luvun korotuksen yhteydessä se päätyy samalle tasolle toisen luvun kanssa ja siis jokainen erillinen luku joudutaan korottamaan enintään kerran, tietorakenteessa on enintään N lukua ja lukujen lisäys ja poisto binääripuusta tai C++:n map-tietorakenteesta on logaritminen toimenpide.

Jokaiselle kyselylle haetaan siis alueen suurin luku logaritmisessa ajassa ja sen jälkeen lasketaan valmiista taulukoista hinta vakioajassa.

Tässä on oma versioni. (Tässä on summataulukon sijaan käytännössä vastaavan tiedon antava tehtävän mukainen hintataulukko alusta kuhunkin lukuun ja tieto minimitasosta kussakin kohdassa. Summataulukko olisi ollut helpompi, mutta ajatusvirheen takia ehdin jo tehdä tällaisen taulukon, joten käytin sitä sitten.)

D, Numerot

Toisen osatehtävän ratkaisu onnistuu melko suoraviivaisesti dynaamisella ohjelmoinnilla: Luvuista 1–9 vähennyksiä tarvitaan yksi (luku itse). Tästä ylöspäin joka luvun kohdalla voidaan vähentää jokin numero (aina 1–9), jolloin päästään varmasti lukuun, josta tulos on jo laskettu. Optimointina huomataan, että aina kannattaa vähentää suurin mahdollinen numero; pienemmällä ei saa koskaan parempaa tulosta. Tällä tavalla voidaan laskea taulukkoon tulokset toisen osatehtävän kokoluokkaan asti, nimittäin f(7864342) = 1000000. Nämä voidaan käydä sitten vaikka silmukalla läpi ja kääntää uuteen taulukkoon niin päin, että saadaan se tehtävässä kysytty asia eli pienin toivotun tuloksen tuottava luku.

Tehokas ratkaisu perustuu muutamaan havaintoon: Kun luvun pienempää päätä lasketaan, iso pää ei muutu. Isosta päästä laskentaan vaikuttaa vain suurin numero. Järkevä rekursioon tai dynaamiseen ohjelmointiin sopiva versio saadaan, kun ratkaistaan sellaiset loppuosat, joissa on vain kaksi numeroa ja välissä nollia. Luku voidaan siis jakaa osiin: {alkumax}{ylin}{nollia}{alin}, missä alkumax on alun suurin numero, ylin on loppuosan ensimmäinen numero, välissä on nollia, ja alin on loppuosan viimeinen numero. Esimerkiksi luku 1340005 jakautuisi osiin {alkumax=3}{ylin=4}{nollia=3}{alin=5}.

Rekursiossa ensin silmukassa vähennetään luvusta 1–2 kertaa suurin mahdollinen numero (max(alkumax,ylin,alin)), jotta tapahtuu kymmenylitys: ylin laskee yhdellä, nollien tilalle tulee yhdeksikköjä. Tämän jälkeen voidaan rekursiivisesti eliminoida yhdeksiköt niin, että välissä on taas pelkkiä nollia. Tätä toistetaan, kunnes loppuosan ensimmäinen numero saadaan nollaksi.

Esimerkkinä rekursion keskeltä: luvusta 1340005 tulee ensin kahdella askeleella 1340000 ja 1339996. Tämän jälkeen voidaan laskea taas rekursiivisesti pienestä päästä lähtien: ratkaistaan (13399)96 eli {alkumax=9}{ylin=9}{nollia=0}{alin=6}, tuloksena (1339)90a; ratkaistaan {alkumax=9}{ylin=9}{nollia=1}{alin=a}, tuloksena (133)900b; ratkaistaan {alkumax=3}{ylin=9}{nollia=2}{alin=b}, tuloksena 133000c, ja sitten jatketaan silmukan alkuun tekemään uutta kymmenylitystä. Lopulta päästään tulokseen 130000x. Samalla logiikalla saadaan nollattua loputkin numerot luvusta. Kaikkien vaiheiden käyttämät askeleet (numeron vähennykset) lasketaan tietenkin yhteen.

Muistitaulukkoon saadaan eri parametreille tieto, montako askelta menee ja paljonko luku muuttuu (eli mitä tulee viimeiseksi numeroksi), jotta saadaan lisää nollia lukuun. Tällä tiedolla saadaan nopeasti nollattua mistä tahansa luvusta ylemmät numerot niin, että jää vain viimeinen numero 1–9, minkä jälkeen tietenkin yhdellä vähennyksellä päästään nollaan.

Ratkaisuun tarvitaan vielä toinen osa: Nyt voidaan tehokkaasti laskea f(k)=x, mutta miten lasketaan x:n perusteella k? Tässä tapauksessa tuloksen voi etsiä binäärihaulla eli haarukoimalla eri k:n arvoja, koska funktio on kasvava (eli isommalla syötteellä ei koskaan tule pienempää vastausta). Lisäoptimointina haussa voisi hyödyntää tietoa, että k/x lähestyy arvoa 9, mutta tällä kertaa se ei ole tarpeen.

Tässä on oma versioni.

Eliittihakkerit voivat löytää epävirallisen koosteen yhteenlasketuista pisteistä.

Kärki on todella tasaisen kova! Kaikki 12 kärjessä ottivat tältä kierrokselta täydet pisteet! Laskujeni mukaan nyt on kaikille kierroksille osallistunut 21 kisaajaa, jos lasketaan mukaan myös osallistuminen, vaikka pisteitä ei tulisikaan.

Itse en tänä viikonloppuna kerennyt muiden menojen takia tehdä tehtäviä. Pitääpä koittaa ratkoa niitä nyt jälkikäteen.

Ensimmäiseen tehtävään kerkesin tehdä ratkaisun, jolla olisi saanut täydet pisteet jos olisin älynnyt, että tilanne 1 3 2 4 on mahdollinen ratkaista. Ajattelin jonkun aivopierun takia, että voin vaihtaa vain paikkoja 1-3 ja 2-4, vaikka 1-4 on tietenkin myös mahdollinen :/

https://cses.fi/341/result/A/1151188/

AtskaFin kirjoitti:

Itse en tänä viikonloppuna kerennyt muiden menojen takia tehdä tehtäviä.

Itselläkin vähän sama tilanne, tosin arkisin on sit töitä. Ehkä näitä voi sitten ratkoa eläkkeellä :)

Metabolix kirjoitti:

C, Kyselyt

Minulla oli hieman erilainen ratkaisu, joka perustuu hyppytauluun. Idea on siis, että jokainen taulukon alkio pitää kirjaa siitä missä on seuraava itseä korkeampi alkio sekä hintaa välissä olevien alkioiden korottamiseksi omalle tasolleen. Nämä tiedot voidaan koostaa nopeasti käymällä taulukko lopusta alkuun ja pitämällä pinossa kirjaa korkeimmista arvoista. Jokaisen alkion kohdalla poistetaan ensin pinosta kaikki itseä pienemmät tai samankokoiset arvot, lasketaan välin täyttämiseen kuluva hinta samalla tavalla kuin Metabolix sen tekee, ja lisätään oma arvo pinoon. Tämä toimii lineaarisessa ajassa, sillä jokainen alkio lisätään pinoon kerran ja poistetaan siitä korkeintaan kerran.

Tästä rakenteesta voidaan hakea välin [a, b] summa seuraavasti: käytetään hyppytaulua välin alkupään siirtämiseksi lähemmäs loppupäätä kunnes seuraava hyppy veisi lopun yli samalla pitäen kirjaa hinnasta. Tämän jälkeen tiedetään että kaikki loput välin alkiot ovat matalampia kuin löydetty alkio, joten loppualueen hinta voidaan löytää helposti summataulukon avulla.

Tämä rakenne ei vielä itsessään ole tarpeeksi nopea sillä pahimmassa tapauksessa väliä pitää pienentää hyppytaulukon avulla lineaarinen määrä kertoja. Tähän löytyy kuitenkin yksinkertainen optimointi, jolla saadaan yksittäinen kysely nopeutettua vain logaritmisen ajan vieväksi: sen lisäksi, että pidetään kirjaa seuraavasta suurimmasta alkiosta, pidetään kirjaa myös "kahden päässä" olevasta suuremmasta alkiosta, "neljän päässä" olevasta suuremmasta alkiosta jne. aina kahden potensseissa. Tässä "kahden päässä" tarkoittaa siis alkiota joka on alkiota seuraavaa suurempaa alkiota seuraava suurempi alkio jne. Nämä pidemmät hypyt taulukossa voidaan esilaskea nopeasti lyhyempien hyppyjen avulla: Pitkän hypyn kohde on löytyy tekemällä kaksi lyhyempää hyppyä, ja sen hinta on osahyppyjen hintojen summa.

Tästä kokonaisesta hyppytaulukosta haku toimii nyt logaritmisessa ajassa, sillä voidaan aina yrittää hypätä mahdollisimman pitkä hyppy ja kun se ei enää onnistu hypyn pituutta voidaan lyhentää. Kunhan hyppytaulukossa on tarpeeksi monta kerrosta, riittää aina hypätä korkeimmalla tasolla korkeintaan kerran, ja matalammilla tasoilla hypätään korkeintaan kerran sillä jos pitäisi hypätä samalla tasolla useamman kerran, olisi voitu ylemmällä tasolla hypätä pidemmälle. Koska hyppytaulukossa on logaritminen määrä kerroksia ja jokaisella kerroksella hypätään korkeintaan kerran, kestää yhden kyselyn laskemiseen vain O(log N) aikaa.