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 perustelusi perusteella ajattelin ensin, että tämän tehtävän on pakko olla "täydellisesti ratkaistavissa", 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.