Keskustelu: Ohjelmointiputka: Putka Open 2025 kierros 1

Putka Open 2025 kierros 1 alkaa pian:

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

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

Onko tuloslista jo näkyvissä vai tuleeko vasta kierroksen jälkeen?

Ensimmäisellä kierroksella on hyvät tehtävät, kiitos!

Pistetaulu löytyy CSES:stä: https://cses.fi/594/scores/

Kiitos Antti, tehtävät tuntuvat hyvin onnistuneilta. D-tehtävään on saatu ovelasti monta eri tehtävää. Jännä nähdä, miten siinä tulokset kehittyvät. Välissä ehdin nähdä voittajalla jopa 60 pisteen tuloksen, vaikka järjestyksessä osatehtävistä odotus olisi 10, 20, 30, 70, 100.

Viimeinen tehtävä panee miettimään sääntöjä: miten tarkasti toivottu algoritmi pitää tietää, jotta sen toteutuksen saa etsiä netistä? Eli jos ongelma D vastaa tunnettua ongelmaa X, johon on olemassa algoritmi Y, paljonko pitää tietää aiheista X ja Y, jotta ratkaisun hakeminen perustellusti liittyy "yleisesti tunnettuihin algoritmeihin"? Esimerkiksi jos tehtävä olisi selvästi yhteydessä klassiseen kauppamatkustajan ongelmaan, jonka kaikki tuntevat ja johon tunnetusti on tietyntyyppisiä ratkaisuja olemassa, miten tarkkaan pitäisi osata määritellä haluamansa algoritmi, jotta olisi sallittua hakea netistä neuvoa algoritmiin?

Luulen että en tule keksimään D-tehtävään 4. ja 5. osatehtävään toimivaa algoritmia, niin en varmaan saa motivoiduttua tekemään myöskään 2. ja 3. osatehtävää vaikka niihin olisi tehtävissä triviaali ratkaisu (joka ei toimi myöhemmille).

Ajattelisin että eihän tässä edes voi googlettaa aiheesta kun siinäkin automaattisesti tulee tekoäly antamaan omia näkemyksiään. Ja jos ajattelisi että ongelma olisi kauppamatkustaja-tyylinen, niin siihenhän ei ole käsittääkseni olemassa täydellistä ratkaisua vaan algoritmeja jotka antavat todennäköisesti aika hyvän ratkaisun. Kilpailutehtävässä taas tulee ajatus että pitäisi olla ihan varma siitä että löytyykö ratkaisu vai ei.

Kisasivulle https://www.ohjelmointiputka.net/kilpailut/2025-putka-open/ voisi myös lisätä linkin CSES:ään.

Grez kirjoitti:

Kilpailutehtävässä taas tulee ajatus että pitäisi olla ihan varma siitä että löytyykö ratkaisu vai ei.

Yleisellä tasolla ottamatta kantaa näihin tehtäviin: Kilpailussa ei sinänsä ole mitään vaatimusta että koodin pitäisi olla todistettavasti riittävän tehokas. Esim. KKKK:n luku 5.4 "Haun optimointi" on esimerkki tekniikasta jolla saatuja ratkaisuja on usein vaikea todistaa riittävän nopeiksi.

Myös kisaformaatti vaikuttaa; Putka Openissa saat heti tietää menikö testit läpi, joten voit yrittää puukottaa epätäydellistä ratkaisua kunnes se toimii riittävän hyvin. Toisena ääripäänä taas esim. CodeForcesissa muut kisaajat voivat tehdä syötteitä koodisi pään menoksi, jolloin hajautustaulujenkin käyttö on riskialtista.

Grez kirjoitti:

Ajattelisin että eihän tässä edes voi googlettaa aiheesta kun siinäkin automaattisesti tulee tekoäly antamaan omia näkemyksiään.

Miten niin tulee? Ei itselleni ole tekoäly tullut missään antamaan mitään ellen ole mennyt tekoälyttömyyttä käyttämään. Käytänkö intterveppiä väärin kun saan vain järkeviä tuloksia eikä tekoälyttömyydet tule sotkemaan elämää?

Ai niin, en "googleta" enkä käytä muutenkaan Googlen tuotteita (miksi kukaan käyttäisi?), ehkä se tässä on se ratkaisu. Elämä paljon helpompaa.

Ja ainahan voi olla lukematta sen sepustuksia jos väkisin haluaa moista tuotetta käyttää.

Varmaan tosiaan hyvä ratkaisu hakea netistä jollain muulla kuin googlella. Mitä hakukonetta itse suosittelet? Nykyään tuntuu että kaikki on ihan hanurista kun 10 vuotta sitten google oli just hyvin toimiva.

Ja tosiaan kun et kerran käytä niin et sen takia vissiin ole huomannut, että Googleen tulee sopivilla hauilla tekoälyn muodostama vastaus ensimmäiseksi. Saahan sen yli tietty skipattua, mutta joskus sen lukee vahingossa.

Grez kirjoitti:

Kilpailutehtävässä taas tulee ajatus että pitäisi olla ihan varma siitä että löytyykö ratkaisu vai ei.

Kyllähän kisoissa nykyään on myös vaikeita ja liukuvasti pisteytettäviä optimointitehtäviä, kuten vanha putkaposti Kielitiedettä, jota jlaire on sinnikkäästi yhä ratkonut. Tällaisen tehtävän hyvä puoli on se, että myös parhaiden kilpailijoiden välille saadaan pieniä eroja.

Optimointitehtävät ovat tosiaan ihan oma genrensä, mutta jos pisteytys ei ole liukuva ja syötteitä ei nää, laadukkassa kisassa voi olettaa, että kunnollinen ja kaikille syötteille todistettavasti riittävän tehokas ratkaisu on olemassa. Tämä on yleinen näkemykseni, D-tehtävää en ole vielä kauheasti yrittänyt. (Joskus syötteet ovat piilossa, mutta ne generoidaan satunnaisesti jollain tarkasti määritellyllä menetelmällä. Silloin ei tarvitse huolehtia todella epätodennäköisistä patologisista tapauksista ja heuristisen algoritmin voi osoittaa riittävän hyväksi suurella todennäköisyydellä.)

Huonosti järjestetyissä kisoissa näin ei aina ole ollut, tulee mieleen ainakin codechefin PLUSEQ, joka oli NP-vaikea ongelma ja jälkeenpäin jokaiseen hyväksyttyyn ratkaisuun (myös tehtävän laatijan "malliratkaisuun") löydettiin syötteitä, joilla aikaraja ylittyisi.

Jos Putka Openin finaalipaikoista tulee tiukka kilpailu, vaikeimpien tehtävien osittaiset pisteet saattavat olla ratkaisevia. Mutta tässä on vielä hyvin aikaa saada 400/400...

Joo siis varmuudesta puhuessani tarkoitin juuri tätä kilpailua ja tehtävää, kun tässä käsittääkseni tulee hylky osioon jos oma ohjelma vastaa NO johonkin tehtävään, johon tarkastusohjelma tietää löytyvän vastauksen.

Oletin siis viestiä kirjoittaessani, että tähän on olemassa algoritmi, jolla selviää absoluuttisen varmasti kelpoinen järjestys aikarajan puitteissa, jos sellainen on olemassa.

Sittemmin hieman asiaa pähkäiltyäni tulin siihen tulokseen, että sinänsähän toimivan tarkistusohjelman voisi tehdä, vaikka testaaja ei itsekään tietäisi kaikkia "parhaita vastauksia". Eli jos tarkistuskoodi ei tuntisi johonkin tehtävään vastausta, niin se voisi hyväksyä sekä NO että YES vastauksen, mikäli YESin perässä tulee kelvollinen sarja.

On muuten hauska katsella millä kielellä kukakin on vastaillut. Luokkaa 90% ratkaisuista näyttää olevan c++:lla.

Grez kirjoitti:

Tosin hieman asiaa pähkäiltyäni tulin siihen tulokseen, että sinänsähän toimivan tarkistusohjelman voisi tehdä silti, vaikka testaaja ei itsekään tietäisi kaikkia "parhaita vastauksia". Eli jos tarkistuskoodi ei tuntisi johonkin tehtävään vastausta, niin se voisi hyväksyä sekä NO että YES vastauksen, mikäli YESin perässä tulee kelvollinen sarja.

En pitäisi tuollaista tarkistinta toimivana. Jos ratkaisu on olemassa, NO on väärä vastaus ja se täytyy hylätä.

jlaire kirjoitti:

En pitäisi tuollaista tarkistinta toimivana. Jos ratkaisu on olemassa, NO on väärä vastaus ja se täytyy hylätä.

Siis tarkoitin tilannetta, jossa kilpailun laatija ja tarkistussoftan tekijä on luullut, että syötteelle ei ole ratkaisua.

Eli jos tarkistusohjelma odottaa saavansa NO vastauksen, niin mielestäni olisi kohtuutonta hylätä kilpailija, joka vastaa YES ja antaa kelvollisen sarjan.

Eli juuri tuon näkemyksesi (huono tarkistin jos hyväksyy NO mihinkään, mihin on mahdollista saada YES) perusteella ajattelin ensin, että tämän tehtävän on pakko olla "täydellisesti ratkaistavissa" että tarkistin pystytään ylipäätään tekemään. Mutta sitten myöhemmin tulin siihen tulokseen ettei se ole ehdoton edellytys vaan periaatteessa voisi kisata niinkin, että pitää olla yhtä hyvä tai _parempi_ algoritmi kuin kisan suunnittelijalla.

Metabolix kirjoitti:

Viimeinen tehtävä panee miettimään sääntöjä: miten tarkasti toivottu algoritmi pitää tietää, jotta sen toteutuksen saa etsiä netistä?

Tätä ei pysty määrittelemään tarkasti, mutta itse kilpailijana ajattelisin, että jos tiedän yleisesti tunnetun algoritmin tietyn ongelman ratkaisemiseen, niin voin etsiä tästä algoritmista tietoa netistä. Esimerkiksi jos tietäisin, että binäärihaun avulla voi etsiä tehokkaasti lukua järjestetystä listasta, ja keksisin tehtävään algoritmin, jossa täytyy etsiä tehokkaasti luku järjestetystä listasta, voisin etsiä tietoa binäärihausta.

jlaire kirjoitti:

Kisasivulle https://www.ohjelmointiputka.net/kilpailut/2025-putka-open/ voisi myös lisätä linkin CSES:ään.

Lisäsin nyt linkin, josta pääsee kierrokselle 1, ja muutan sitä myöhemmin. Muutenkin parannan vielä linkitystä eri paikoissa.

Grez kirjoitti:

Sittemmin hieman asiaa pähkäiltyäni tulin siihen tulokseen, että sinänsähän toimivan tarkistusohjelman voisi tehdä, vaikka testaaja ei itsekään tietäisi kaikkia "parhaita vastauksia". Eli jos tarkistuskoodi ei tuntisi johonkin tehtävään vastausta, niin se voisi hyväksyä sekä NO että YES vastauksen, mikäli YESin perässä tulee kelvollinen sarja.

Putka Openin tehtävissä pätee, että tehtävän laatijan tiedossa on ratkaisu, joka toimii oikein ja tehokkaasti kaikilla mahdollisilla tehtävänannon mukaisilla syötteillä, jos tehtävässä ei ole mainittu muuta. Esimerkiksi tämän kierroksen tehtävässä D voi luottaa siihen, että tehtävän laatijan tiedossa on ratkaisu, joka pystyy löytämään vastauksen aina, kun sellainen on olemassa.

Sinänsä tehtävän D laatija voisi vähän turvata selustaa hyväksymällä YES-vastauksen, vaikka malliratkaisu antaisi NO-vastauksen, jos YES-vastauksessa on todella mukana kelvollinen järjestys. Tavoitteena tehtävien laatimisessa on kuitenkin, että malliratkaisu on huolellisesti testattu eikä tällaista tilannetta pitäisi esiintyä.

Eipä lähtenyt D-tehävän myöhemmät osatehtävät ratkeamaan aikarajan puitteissa. Tuleeko näistä esimerkki syötteet kierroksen päätyttyä? Olisi kiva ajaa profileria ja katsoa olisiko nykyisellä algoritmilla edes mahdollista päästä maaliin.

Antti Laaksonen kirjoitti:

Kierros 1 alkaa pe 5.9. klo 18:00 ja päättyy su 7.9. klo 23:00.

Tuo on väärin. Suomen kielessä tunnit ja minuutit erotetaan pisteellä, ei kaksoispisteellä. https://kielitoimistonohjepankki.fi/ohje/ajanilmaukset-kellonajat-merkinta-ja-taivutus/

tkok kirjoitti:

Tuleeko näistä esimerkki syötteet kierroksen päätyttyä? Olisi kiva ajaa profileria ja katsoa olisiko nykyisellä algoritmilla edes mahdollista päästä maaliin.

Kierroksen päätyttyä tulee saataville testiaineisto ja CSES:ssä näkee myös kunkin testisyötteen ajankäytön.

Jaska kirjoitti:

Tuo on väärin. Suomen kielessä tunnit ja minuutit erotetaan pisteellä, ei kaksoispisteellä. https://kielitoimistonohjepankki.fi/ohje/ajanilmaukset-kellonajat-merkinta-ja-taivutus/

Mielestäni kaksoispiste on parempi, koska se on yleisesti käytetty ja tunnettu merkintä eikä mene sekaisin päivämäärän kanssa. Itse asiassa linkittämässäsi ohjeessa lukee näin:

Kielitoimiston ohjepankki kirjoitti:

Kansainvälisen standardin mukainen kaksoispisteellinen kellonajan merkintä (9:15) on yleinen tietoliikenteessä, digitaalisissa kelloissa yms., ja näissä yhteyksissä kaksoispistettä voi käyttää.

Ohjelmointiputkan viestit ovat tietoliikennettä, eli tuonkin ohjeen perusteella näkisin, että kaksoispistettä voi käyttää.

No, en tiedä niin tarkasti kielioppisääntöä tuolta osin. Kielimalli neuvoi:

lainaus:

Suomessa oikea tapa merkitä kellonaika on pistettä käyttäen, eli:

15.30 (ei 15:30)

9.05 (ei 09:05)

Tämä on virallinen suositus esimerkiksi Kielitoimiston ohjepankin mukaan.

📌 Milloin kaksoispistettä näkee?

Kansainvälisissä yhteyksissä (englannin vaikutus, esim. tietokoneiden käyttöjärjestelmät, digitaaliset näytöt, verkkosovellukset).

Teknisissä ympäristöissä, joissa ohjelmistot noudattavat ISO 8601 -standardia (esim. 15:30:00).

Joillakin nettisivuilla (varsinkin monikielisissä palveluissa) käytetään kaksoispistettä, koska se on yleisempi merkintätapa muualla maailmassa.

👉 Jos siis teet suomenkielistä nettisivua suomalaisille, kielenhuollon suositus on käyttää pistettä (15.30).
👉 Jos taas sivulla on kansainvälinen yleisö, kaksoispiste voi olla selkeämpi ja yhtenäisempi käytäntö.

Antti Laaksonen kirjoitti:

Ohjelmointiputkan viestit ovat tietoliikennettä, eli tuonkin ohjeen perusteella näkisin, että kaksoispistettä voi käyttää.

Itse näkisin että ohjelmointiputkan viestit (eli tekstisisältö) ovat proosaa ja tietoliikennettä on tekniikka, jolla ne tuodaan käyttäjille.

Olisi myös älyllisesti epärehellistä väittää, että suomenkielisten viestien yleisö on kansainvälistä.

Itse ajattelisin, että foorumin käyttäjäkunta on ohjelmoijat, jotka yleisemmin käsittelevät ja joille siksi kenties ajan kanssa tutumpi on kaksoispiste, kuin pistettä.

Toisaalta tuolla viimeisimmällä logiikalla voisi myös ajatella että keskustelu käytäisiin englanniksi, kun sitä ohjelmointiasioissa useammin käytetään.

Viitsiikö joku kärkijoukosta selittää D:tä yleisölle? Kisakoodeista on vaikea dekryptata logiikkaa ja perusteluja.

Kierros 1 on päättynyt ja tämä oli mainio aloitus kilpailulle: mukana on hyvä määrä osallistujia ja paljon kiinnostavia ratkaisuja.

Tässä keskustelussa voi mielellään kertoa omista ratkaisuista, etenkin tehtävään D.

Seuraava kierros 2 on syyskuun lopussa alkaen perjantaina 26.9.

Metabolix kirjoitti:

Viitsiikö joku kärkijoukosta selittää D:tä yleisölle? Kisakoodeista on vaikea dekryptata logiikkaa ja perusteluja.

Tähän on varmaan joku tyylikäskin algoritmi, mutta itse en sellaisista mitään tiedä niin jouduin vain "Excelissä" pähkimään asiaa ja kehittelemään omani suunnilleen "puhtaalta pöydältä".

Tein ensin perus brute force koodin, jolla sai 1 osatehtävän läpi, mutta oli jo alkuun selvää, että sillä ei niihin muihin olisi mitään jakoa. Sitten 2. ja 3. osatehtävä meni logiikalla että kaikki vaan nousevaan X järjestykseen ja sillähän se menee jos oli mennäkseen. (niin itsekin näköjään teit)

Käytin myöhemmin vielä tuota brute force algoritmia testaamaan erilaisia algoritmiajatuksia. Eli ajoin 15 parin satunnaissyötteitä sillä ja kehitteillä olevalla algoritmillani ja jos puhdas bruteforce sai ratkaisua sellaisen, mitä toinen ei, niin otin syötteen exceliin ja pyörittelin sitä siellä käsin nähdäkseni mitä voisi parantaa.

Lopulta ratkaisuni on oikeastaan bruteforce pienillä optimoinneilla ja pyrin havainnoimaan mahdollisimman aikaisessa vaiheessa jos homma ei ole mahdollista. Ja siitä syystä joka iteraation alussa käytin sellaista logiikkaa, että järjestin X:t ja Y:t järjestykseen

Eli jos parit oli

10 12
80 23
29 79
30 11
24 90

niin näistä voi katsoa X ja Y järjestyksessä ( * tarkoittaa mitä vaan kun eka tai vika ei ole rajoitettu)

jX jY
10 **
24 11
29 12
30 23
80 79
** 90

Jos tämän taulukon jollakin Y on piempi kuin X, niin ajattelisin että ratkaisu ei ole mahdollinen.

Sitten yritin sitä että mennään parit X:n mukaan järjestettynä ja lisätään aina ensimmäinen ei-käytetty pari joka soveltuu jatkoksi.

Valitettavasti huomasin, kun satunnaissyötteellä testailin, että pelkästään yksi "mahdollisuustarkistus" alussa ei riittänyt, vaan silloin tällöin tuli tilanne, jossa testin mukaan olisi pitänyt mennä läpi mutta se ei mennytkään. Eli järjestysalgoritmini ei ollut riittävän hyvä. ( Ja ehkä testausalgoritmikaan ei ollut aukoton, vaan jotkin mahdottomat näyttivät mahdollisilta? )

Tein sinne sitten rekursion jossa joka kierroksella
1) jos jonkin jäljellä olevan on oltava ensimmäinen niin se ensimmäiseksi ja seuraava rekusioaskel
2) Jos selvitettävän osion ratkaisu ei näytä mahdolliselta, palataan "epäonnistui" lipulla
3) jos jonkin jäljellä olevan on oltava viimeinen niin se viimeiseksi ja seuraava rekursioaskel
4) Muuten laitetaan seuraavaksi pienin X joka sopii ja seuraava rekursioaskel
5) Jos ei ole kelvollista, poistutaan rekursiosta "epäonnistui" lipulla

Tällä systeemillä sain nyt sitten oikeita vastauksia, mutta ilmeisesti se ei ollut ihan riittävän nopea, kun 30 pistettä jäi saamatta ilmoituksella "TIME LIMIT EXCEEDED". Koodailin omalla koneella sitä C#:lla ja siinä se kyllä kaikilla kilpailun rajojen mukaisilla satunnaissyötteillä homma meni ihan reilusti alle sallitun ajan, mutta joko C++:lle tekemäni versio oli hitaampi tai jokin syöte oli satunnaisia pahempi. Nyt kun syötteet on julkisia, niin täytyykin jossain kohti testata mikä siinä mätti. Sinänsä yhtä syötettä lukuun ottamatta ajat kyllä näyttää ihan vertailukelpoisilta täydet pisteet saaneiden kanssa.

Sinänsähän olisin voinut tehdä vielä paljonkin optimointeja, mutta kun en oikeastaan osaa C++:aa ja ylipäätään sain toimivan algoritmin valmiiksi vasta pari tuntia ennen ajan loppumista, niin optimointi jäi vähän ohueksi. Lisäksihän oli tietysti mahdoton sanoa että kuinka kaukana olin "maalista". Eli olisiko koodini suoriutunut testisyötteellä 1.03 sekunnissa, vai 103 sekunnissa. Kumpikin menee yli aikarajan, mutta jälkimmäinen ei ehkä ihan pienellä optimoinnilla olisi korjaantunut :D

Tässä joitakin kommentteja tehtävien laatijan näkökulmasta:

Tehtävä A: Harkitsin myös luvun 42 liittämistä tehtävään, mikä olisi ollut mahdollista ainakin kahdella tavalla. Luvussa 2025 * 1337 = 2707425 esiintyy luku 42 osajonona, minkä lisäksi 2025 = 3⁴ * 5² eli potenssit muodostavat myös luvun 42.

Tehtävä B: Kun arpojen määrä n kasvaa, todennäköisyys lähestyy lukua 1-1/e, missä e on Neperin luku, eli suurilla n:n arvoilla todennäköisyys on noin 63 %. Tähän on viittaus myös tehtävän pisteytyksessä, koska toisen osatehtävän arvo on 63 pistettä. Tämä on mielestäni kiinnostava tieto, koska intuitiivisesti voi olla vaikeaa arvioida, miten suuri todennäköisyys on saada voittava arpa.

Tehtävä C: Tämä on muunnelma tunnetummasta tehtävästä, jossa luvut tulee jakaa kahteen joukkoon vastaavalla tavalla. Muutamaa pientä tapausta lukuun ottamatta ratkaisu on aina mahdollinen, jos summa 1+2+...+n on jaollinen 3:lla. Tähän tehtävään on olemassa tehokkaita konstruktioita, mutta myös raakaan voimaan perustuva haku toimii hyvin, koska mahdollisia kelvollisia ratkaisuja on suuri määrä.

Tehtävä D: Tehtävä on selvästi vaikeampi kuin muut kierroksen tehtävät. Oli kiinnostavaa nähdä, että tehtävään tuli useita erilaisia lähestymistapoja 100 pisteen ratkaisuun. Tehtävässä jotkin ahneet virheelliset ratkaisut toimivat yllättävän hyvin, minkä takia tehtävän laatimisessa haasteena oli tehdä riittävän hyvä testiaineisto. Jälkeenpäin ajatellen testiaineisto olisi saanut olla vielä kattavampi: ainakin yhdessä lähetetyssä ratkaisussa vain yksittäinen testi syötteessä #12 toi esille, että ratkaisu ei toiminut oikein osatehtävässä 4.

Nolottaa selittää D-ratkaisuaan kun esim. ollpun koodin perusteella tein ihan tarpeettoman vaikeasti mutta tässä tulee jotain :D.

TL;DR: maksimiparitus + syklien poisto

Lisätään lukuparien joukkoon aluksi alkupari (0,0) ja loppupari (inf,inf).
Sitten lasketaan maksimiparitus syötteen lukuparien välille ehdolla että (a,b) voi parittaa (c,d) kanssa joss b<=c.
Maksimiparitus yhdistää jokaisen syötteen lukuparin toiseen lukupariin joka voidaan laittaa järjestyksessä sen perään.
Jos maksimiparitus ei löydä paria jollekin lukuparille, vastataan NO.

Kun katsotaan maksimiparituksen muodostamaa polkua alkuparista loppupariin, saadaan osittainen ratkaisu josta mahdollisesti puuttuu joitakin syötteen lukupareja.
Puuttuvat parit muodostavat syklejä, esim. joukko {(a,b),(c,d),(e,f)} joille b<=c, d<=e ja f<=a.

Syklit yhdistetään ratkaisupolkuun ahneesti: käydään läpi ratkaisupolun jokainen vierekkäinen pari (a,b),(c,d), ja käydään sille läpi kaikkien syklien kaikki vierekkäiset parit (x,y),(z,w), ja jos (b<=z) ja (y<=c), niin työnnetään sykli tähän väliin osaksi ratkaisua (z,w) alkaen.

Lopulta tarkistetaan saatiinko kaikki syklit yhdistettyä ratkaisuun, ja vastataan YES vain jos ratkaisu sisältää koko syötteen.

Ratkaisu tuntuu toimivalta, mutta en ole keksinyt oikein kunnollista todistusta sen oikeellisuudesta. Jos maksimiparitus löytää suoraan kokonaisen ratkaisun niin se on selvästi oikein, mutta vaikea osuus on varmistaa ettei "syklien poisto" jätä jotain mahdollista ratkaisua huomioimatta. Intuitiivisesti voi ajatella että syklejä on "helppo" lisätä polkuun koska syklin voi liittää sen mistä tahansa kohdasta, joten riittää että ratkaisupolku sisältää luvun joka on syklin pienimmän ja suurimman arvon välillä. Näin ollen ainoa tapaus, jossa syklin lisäys ei onnistu on että ratkaisuun kuuluu pari (x,y) jossa x<a<y kaikille syklin luvuille a, joten (x,y) estää syklin osien liittämisen ratkaisuun menetelmästä riippumatta.

Sisuaski kirjoitti:

Ratkaisu tuntuu toimivalta, mutta en ole keksinyt oikein kunnollista todistusta sen oikeellisuudesta.

Tämä pätee omaankin ratkaisuuni. Kuten lauantaisesta viestistäni näkee niin meinasin sen takia lyödä hanskat tiskiin.

Oma ratkaisu D:hen ehti hioutua melko yksinkertaiseksi, kun päätin jättää toteutuksen aamuun, mutta ei sitä malttanut nukkumaan mennessä olla miettimättä.

Ensin samoja aineksia, kuin Grezin ja Sisuaskin kuvauksissa: Lisään ylimääräisen parin (ääretön, 0), joka on sekä aloitus- että lopetusmerkki. Sitten järjestän x:t ja y:t erikseen.

Järjestämisen jälkeen koon n+1 maksimiparitus löytyy (jos on löytyäkseen) valitsemalla kaaret suoraan y:stä x:ään järjestyksessä. Tämä johtuu siitä, että mahdollisten kaarien joukko kasvaa monotoniseseti, kun edetään y:n mukaisessa laskevassa järjestyksessä. Hyödyllinen muttei välttämätön esitieto on Hallin avioliittolause.

Parituksesta saattaa tosiaan muodostua useampi sykli: yksi, johon alku/loppumerkki kuuluu, sekä muita, joihin se ei kuulu. Yritän sitten yhdistellä syklejä samalla idealla kuin Sisu. Parituksessa yhdistely näyttää siltä, että vaihdetaan kahden y:n kaaret x:n puolella keskenään, missä kaaret kuuluivat aluksi eri sykleihin. Jos erehtyy vaihtamaan samassa syklissä olevien kaaret keskenään, jakautuu sykli kahtia. Koodissa paritus esitetään taulukossa p käänteisesti. Käyn x:t läpi järjestyksessä, ja vaihdan peräkkäisiin x:iin osoittavat kaaret parituksessa, mikäli se on mahdollista ja kaaret kuuluvat vielä eri sykleihin. Aikavaativuus on siis O(tn log n)

Miksi ahne (tai oikeastaan mikä tahansa) strategia syklien yhdistelyyn toimii? Hahmotin asiaa näin: Määritellään syklille S={(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)} välijoukko I_S lukusuoralla seuraavasti: piste t kuuluu I_S:ään, jos y_m <= t <= x_m+1 jollekin m (syklisesti, eli n+1=1).

Kaksi eri sykliä A, B voidaan yhdistää täsmälleen silloin, kun niiden välijoukoilla I_A, I_B on jokin yhteinen piste t. Jos tälläinen piste on olemassa, löytyy syklistä A peräkkäiset lukuparit (a,b),(c,d), joilla b <= t <= c sekä syklistä B peräkkäiset lukuparit (x,y),(z,w), joilla y <= t <= z. Siispä yhdistäminen näistä kohdista onnistuu. Voidaan myös päätellä, että yhdistetyn syklin C välijoukko I_C on yhdiste joukoista I_A ja I_B, eli mitään ei "menetetä". Sama pätee toiseenkin suuntaan: jos sykli jaetaan kahteen osaan, niin välijoukkojen yhdiste ei muutu ­— se on invariantti.

Jos sattuu niin, että syklin S välijoukko on täysin erillinen kaikista muista, ei tätä sykliä saada millään yhdistettyä muualle. Ei vaikka sallittaisiin myös syklien jakaminen osiin. Jollain siirtosarjalla, joka pitää syklit kelvollisina, pitäisi kuitenkin päätyä ratkaisuun. (Helpoin nähdä parituksessa: kaarien päätepisteitä vaihtelemalla pääsee mihin tahansa toiseen kelvolliseen paritukseen.) Voidaan siis todeta, että ratkaisua ei löydy.

Olipas oikein hienot tehtävät! Vikassa alkoi ahdistamaan, kun alkoi haiskahtamaan rekursiolta. Täytyis varmaan tuo rekursio -juttu ottaa paremmin hanskoihin, mutta en oo saanut siihen tolkkua. Ehkä joku sateinen päivä tuo avautuu.