Kirjautuminen
Tehtävät
Kilpailu
2. kierros:
26.9. klo 18 – 28.9. klo 23
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/
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 varmistamaan että muut ratkaisuni antaa oikeita vastauksia. Eli ajoin 15 parin satunnaissyötteitä sillä ja toisella algoritmillani ja vertasin tuloksia.
Lopulta 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 nyt jokaiselle Y:lle löytyy X, joka on suurempi tai yhtä suuri, niin ratkaisu on periaatteessa 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 että kun satunnaissyötteellä testailin, niin 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
2) jos jonkin jäljellä olevan on oltava viimeinen niin se viimeiseksi
3) Muuten otetaan pienin X joka saadaan laitettua seuraavaksi
4) Jos ei ole kelvollista, poistutaan rekursiosta ja sanotaan että ei onnistu.
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