Tänään Kansainvälisen ohjelmointikilpailun ICPC 2019 finaali järjestetään Portugalin kaupungissa Portossa, johon osallistuvat ITMO-yliopiston edustajat ja muut joukkueet Venäjän, Kiinan, Intian, USA:n ja muiden maiden yliopistoista. Kerrotaanpa tarkemmin.
icpcnews /flickr/ CC BY / Kuvia ICPC-2016 finaalista Phuketissa
Mikä on ICPC
ICPC on kansainvälinen ohjelmointikilpailu opiskelijoiden kesken. Niitä on järjestetty yli 40 vuotta – ensimmäinen finaali olin jo vuonna 1977. Valinta tehdään useassa vaiheessa. Yliopistot on jaettu alueittain (Eurooppa, Aasia, Afrikka, Amerikka jne.). Jokainen niistä isännöi välivaiheita, erityisesti Pohjois-Euraasian välierät tapahtui yliopistollamme. Alueellisten vaiheiden voittajat osallistuvat finaaliin.
ICPC:ssä kolmen osallistujan ryhmiä pyydetään ratkaisemaan useita ongelmia yhdellä tietokoneella (ei Internet-yhteyttä). Ohjelmointitaitojen lisäksi testataan siis myös ryhmätyötaitoja.
Kilpailun aikana joukkueet saa yhden tietokoneen kolmelle hengelle. Siinä on Ubuntu 18.04, ja siinä on esiasennettuna vi/vim, gvim, emacs, gedit, geany ja kate. Voit kirjoittaa ohjelmia Pythonilla, Kotlinilla, Javalla tai C++:lla.
Kun tiimi ratkaisee ongelman, se välittää sen edelleen testauspalvelimelle, joka arvioi koodin. Osallistujat eivät tiedä, mitä testejä kone tekee. Jos kaikki onnistuvat, joukkue saa bonuspisteitä. Muussa tapauksessa syntyy virhe ja opiskelijat lähetetään korjaamaan koodi.
ICPC:n sääntöjen mukaan eniten ongelmia ratkaiseva joukkue voittaa. Jos tällaisia joukkueita on useita, voittaja määräytyy pienimmän rangaistusajan perusteella. Osallistujat saavat sakkominuutteja jokaisesta ratkaistusta ongelmasta. Minuuttimäärä on yhtä suuri kuin aika kilpailun alkamisesta siihen, että testipalvelin hyväksyy tehtävän. Jos joukkue löytää ratkaisun, se saa vielä kaksikymmentä minuuttia rangaistusta jokaisesta virheellisestä syöttöyrityksestä.
icpcnews /flickr/ CC BY / Kuvia ICPC-2016 finaalista Phuketissa
Esimerkkejä tehtävistä
Mestaruuden tavoitteet vaativat joukkueen koordinaatiota ja keskittymistä. Lisäksi he testaavat yksittäisten matemaattisten algoritmien tuntemusta. Tässä on esimerkki tehtävästä, joka tarjottiin ICPC 2018 -osallistujille:
Typografiassa on termi "joki" - tämä on sanojen välisten välilyöntien sarja, joka muodostuu useista tekstiriveistä. Tietty jokien asiantuntija (todella) haluaa julkaista kirjan. Hän haluaa, että sivulle "muodostuvat" pisimmät typografiset joet, kun tulostetaan yksivälisellä fontilla. Osallistujien oli määritettävä niiden kenttien leveys, joilla tämä ehto täyttyy.
Ohjelma sai syötteessä kokonaisluvun n (2 ≤ n ≤ 2), joka määrittää tekstin sanojen määrän. Seuraavaksi kirjoitettiin teksti: yhden rivin sanat erotettiin yhdellä välilyönnillä, eivätkä ne saa sisältää yli 500 merkkiä.
Lähdössä ohjelman piti näyttää niiden kenttien leveys, joihin pisin "joki" muodostuu, ja tämän joen pituus.