Beszámoló a 2001. évi ACM programozási versenyről
Az ACM egy nemzetközi feladatmegoldó programozási verseny, melyen háromfős, egyetemistákból álló csapatok indulhatnak. Az egyetemi forduló első két helyezett csapata jut tovább a regionális fordulóba (Közép-Európa), onnan pedig az első 2-3 csapat kerül be a nemzetközi döntőbe, amelyet többnyire az Amerikai Egyesült Államokban, idén pl. Hawaii-on rendeznek. A csapatok főleg a dicsőségért és ösztöndíjakért versenyeznek.
A verseny időtartama 5 óra, ezalatt 8 programozási feladatot kell megoldani, azaz 8 programot kell elkészíteni a specifikációnak megfelelően. Tervezés és dokumentálás nem szükséges, sőt, még kommentezés vagy a program helyes működésének bizonyítása sem! Egy megoldást akkor fogadnak el a szervezők, ha a beadott program az általuk előre meghatározott bemenetre (a "tesztvektorra") rövid időn belül helyes választ ad. Természetesen a konkrét tesztvektort nem árulják el a versenyzőknek, de várható, hogy a vektor a teljes specifikációt számon kéri. A félig működő vagy közelítő megoldások érvénytelennek számítanak. Az a csapat nyer, amelyik a legtöbb jó megoldást adja be, döntetlen esetén az győz, aki - egy speciálisan számított időeredmény alapján - kevesebb idő alatt oldotta meg a feladatokat. Mindhárom forduló a fenti sémát követi, különbség csak a feladatok nehézségében mutatkozik.
A versenyzőknek egyaránt jól kell tudniuk gyors és helyes algoritmusokat tervezni, és azokat precízen lekódolni. A programok elkészítéséhez csapatonként egyetlen számítógép áll rendelkezésre (C, C++ és Pascal fordítókkal), semmilyen más félvezetőeszközt nem szabad használni. A kész program forráskódját kell beadni, melyet a szervezők azonnal tesztelnek, és néhány percen belül elárulják, hogy elfogadták-e a megoldást, vagy ha nem, akkor két szóban megmondják, miért (compile error, run-time error, wrong answer, timed out, presentation error). Egy feladatra többször is be lehet adni megoldást.
A jó szerepléshez jó szervezési készség, az algoritmusok elméletében való jártasság, kiváló problémamegoldó készség és pontos kódolási képesség szükséges. A legnagyobb nehézséget a helyes algoritmus (és adatábrázolás) megtalálása okozza. Bár a tipikus algoritmusok ismerete előnyt jelent, a feladatok nem intézhetők el pusztán a közismert algoritmusokkal: mindegyikben van néhány csavarás. A megoldás, miután megszületett, már egyszerű: a helyes mintamegoldások tipikusan 1-2 kB-os C programok. Nem is kell bennük bonyolult adatszerkezeteket használni: legtöbbször a statikusan allokált tömb is megteszi, még kupacra és bináris fára is csak ritkán van szükség. A megoldás folyamata hasonló egy matekfeladat megoldásához vagy matematikai tételbizonyításhoz - izgalmas, alkotó szellemi tevékenység. A legtöbb problémára hamar találhatunk megoldást, de ezek a hirtelen előálló algoritmusok általában túl lassúak (exponenciális, de néha még az O(n2,5) is lassú lehet) vagy túl sok memóriát használnak. Az igazi kihívás tehát a gyors (és egyúttal trükkös, szellemes) megoldás felfedezése.
A közép-európai fordulót idén Varsóban rendezték. Mind a szervezésről, mind a szállásról csak elismerően nyilatkozhatunk, a rendezők mindent megtettek a kényelmünkért. A Varsói Egyetemhez közeli Hotel Verában szálltunk meg, kényelmes, tágas, háromfős szobákban. Az étkezésre se lehet panaszunk: bőséges, svédasztalos reggeli várt minket, és napközben is rengeteg szendvicset, üdítőt és gyümölcsöt készítettek ki a versenyzőknek. Az időjárással viszont nem volt szerencsénk: szinte egész nap csípős szél fújt, borús volt az ég, és a hideg utat talált a kabátok résein.
Az ötórás verseny vasárnap zajlott, és még aznap este kihirdették az eredményeket. A verseny ideje alatt minden szobában több segítő állt a rendelkezésünkre, még a nyomtatott lapokért sem magunknak kellett elmennünk. A verseny állását egy jól megírt webes felületen követhettük nyomon, és a megoldásainkat is a weben kellett beadni. A bírálat néhány percen belül megérkezett. A szervezők itt is kitűnő munkát végeztek, a verseny gördülékenyen zajlott. Csak egyetlen feladatban adódott egy - a probléma szempontjából - lényegtelen félreértelmezési lehetőség, végül bármely értelmezés szerinti megoldásokat elfogadták.
Szombaton, a versenyt megelőző napon két érdekes előadást hallgattunk meg (angolul) az egyetem kitűnően felszerelt, új előadótermében: Tényleg szükség van véletlenszámokra? illetve Knots... címmel. Ezután egy rövid próbaversenyt tartottak, melynek során megismerkedtünk a szobával és a számunkra biztosított számítógéppel. Lehetőségünk volt saját config-file-ok létrehozására is, de ezeket este törölték, ezért kinyomtattuk, majd másnap - immár a verseny idejének rovására - begépeltük őket. A hardverrel és az előre telepített Linux rendszerrel csak apróbb kellemetlenségek voltak, de mindenben megfelelt a specifikációnak. Összefoglalásul elmondhatjuk, hogy a szervezők igencsak kitettek magukért mind a verseny ideje alatt, mind előtte.
Szakmai szempontból két problémát találtunk. Az egyik, hogy a megoldásokat elég szerencsétlen opciókkal, optimalizálás nélkül fordították (emiatt például a C++ kódban sebesség-megfontolások miatt több helyen inline függvények helyett a #define-ok sűrűjébe kényszerültünk), valamint az elvileg a versenyzők rendelkezésére bocsátott STL használatát is kerülnünk kellett. Ezt szóvá is tettük, de a kedvünkért már nem változtattak a szabályokon. A másik probléma pedig az volt, hogy nem került sor szakmai kiértékelésre, a helyes megoldások hivatalos (akár vázlatszerű) megbeszélésére. Bár ez kétségkívül időcsúszást okozott volna, még belefért volna a vasárnapi programba. (Az első, BME-n belüli fordulóban egyik probléma sem jelentkezett.)
A versenyen a legjobb teljesítményt a lengyelek nyújtották, az első 6 csapat közül 4 lengyel volt. A magyar csapatok eredményei lentebb láthatók. A BME részéről egy kis szerencsével a 11. és 18. helyezés helyett könnyen lehetett volna kb. 6. és 10., de a lengyelek eredményét - utólag visszagondolva - aligha tudtuk volna megközelíteni. A feladatok nehezek voltak (de nem megoldhatatlanok), ami jónak értékelhető, mert az első néhány helyezett sorrendjét vitathatatlanul meghatározta. Talán lehetett volna kicsit több könnyebb feladatot is berakni, hogy több 4-5 példát megoldó, és kevesebb 2-3 példát megoldó csapat legyen.
Az ACM verseny abban különbözik a valóságban végzett programozói tevékenységtől, hogy a valóságban sokkal kevesebb alkalom nyílik problémamegoldásra, kreatív munkára: helyette csak a meglevő szoftverek hibáit kell foltozgatni, kerülgetni, vagy unalmas, mechanikus adatmanipulácót, adatkonverziót kell végezni. Az ACM ügyesen elkerüli az ilyen helyzeteket, és lehetővé teszi, hogy a versenyzők teljes figyelmüket az algoritmus kiötlésére és csiszolására fordíthassák. Tévedés azonban úgy gondolkodni, hogy az ACM feladatok távol állnak a valóságos problémáktól, és - mivel az életben másra van szükség - fölösleges ilyenfajta programozási játszadozással elütni az időt. Az ACM verseny épphogy hiánypótló az egyetemi évek alatt: számos alapkészséget fejleszt, pallérozza és éberen tartja a gondolkodást. A gyakorlatiasabb megmérettetést kedvelőknek figyelmébe ajánlom a tavalyelőtti, a BME által szervezett 24 órás programozóversenyt, amely érdekes és hasznos átmenet volt a valóság és az ACM között. Reméljük, hogy a sikerén felbuzdulva idén (jövőre) is meg fogják rendezni!
Felmerül a kérdés, hogyan lehet egy ACM-szerű programozási versenyre tanulni, felkészülni. Lexikális ismeretre nincs szükség, mivel bármilyen könyv és írásos anyag használható a verseny alatt. Bár vannak típuspéldák és tipikus trükkök, ezek alkalmazása még nem elég a feladatok megoldásához. Az ACM ebben az értelemben is hasonló a matematikaversenyekhez: a széleskörű rálátás mellett elengedhetetlen a feladatmegoldási készség. Mindezeket csak sok egyéni gyakorlással, gondolkozással lehet megszerezni. Sajnos jelenleg a BME-n nincs olyan tantárgy, ami ebben segítene: a Programozás alapjai és az Algoritmusok elmélete tárgyak idejébe egyszerűen nem fér bele a nehezebb, trükkösebb programok írása. Szívesen vennénk egy új, gyakorlatiasabb választható tárgyat, amelynek fő célja a problémamegoldó-készség feljlesztése és az ACM versenyre való felkészítés lenne.
Ez a verseny a feladatok jellege folytán méltán tekinthető a Nemzetközi Informatikai Diákolimpia folytatásának. Bár a megoldásnál az Algoritmuselmélet tárgy anyagánál mélyebb ismeretekre nincs szükség, egy maxpontos zárthelyi (noha elég ritka) messze nem elég a sikeres szerepléshez, kifinomult gyakorlati érzék is szükséges hozzá. Nem véletlen, hogy az egyetemi válogató első két helyén viszonylag magasan olyan csapatok végeztek, amelyekben egy-egy volt kettős diákolimpikon szerepelt. Talán az a legfontosabb, hogy "sokat látott" emberek legyenek a csapatban. Ennek érzékeltetésére a sikerrel megoldott feladatainkat hozhatjuk fel: két példa (MAYA, CISTERN) nagyon egyszerű volt, megoldása pusztán jól koordinált programozási (kódolási) készséget igényelt (ami tanítható), és reguláris programozási kurzusok keretében elsajátítható. Ezeket egyetemünk mindkét csapata megoldotta. A második csapatunknak ezen kívül a STIRLING példát sikerült megoldania, amelyhez egy ügyes észrevétel, a feladat átfogalamazása volt szükséges (egy megfelelő változócsere). További két feladathoz (MORSE, EXCH) nagyon előremutató ötletük volt, de egy kis csavar hiányzott a befejezéshez. Első csapatunk a MORSE feladattal birkózott meg, mellyel az egyik csapattag már találkozott az 1998-as diákolimpiai válogatóverseny során, és így nem csak a megoldás alapalgoritmusát ismerte, melyet klasszikus (és tanulható) dinamikus programozási technikákkal ki lehet dolgozni a verseny ideje alatt (második csapatunk meg is tette), hanem az ennek hatékony megvalósításához szükséges adatszerkezetet is. A negyedik megoldott példánk a SEGMENTS volt, melyre rajtunk kívül csak a második helyen végzett varsói gárda adott be elfogadott programot (ők is csak kilenc (!) sikertelen próbálkozás után). Tulajdonképpen a szerencsének köszönhető ez a példa, mert az amúgy szuboptimális futási idejű program egy hajszállal átcsúszott az időlimiten. A megoldás négyzetesről majdnem lineárisra vagy legalábbis O(n·logn)-esre gyorsítható lett volna az adatszerkezet bonyolult tömörítésével (kiegyensúgyozott keresőfa, intervallum-fa), de ennek megírására nem maradt időnk. A további feladatokról: egy (GATES) teljesen megközelíthetetlen volt (csak a győztes oldotta meg), egy pedig (ALICE) majdnem reménytelen (csak az első három oldotta meg).
Összefoglalva: a diákolimpiákhoz képest, ahol az alkotó gondolkodás döntő szerepet játszik, itt esetleges ötletek és rutin szükséges - rengeteg megoldott feladat a csapat minél több tagjának háta mögött. Megkockáztatom, hogy bizonyos feladatok megoldása lehetetlen a verseny ideje alatt, ha legalább hasonlót nem oldott meg a versenyző korábbi pályafutása során. Szintén elengedhetetlen feltétel a jó szerepléshez, hogy összeszokott, jó csapattal kell kiállni, előre átgondolt szerepekkel és stratégiával (különösen mivel a megoldások beadásának ideje is számít). Ehhez pedig gyakorló versenyeket kell tartani, valódi versenyfeladatsorokkal.
Köszönettel tartozunk Benedek Balázsnak és Marx Dánielnek (volt eredményes ACM versenyzőknek) és Dr. Szirmay-Kalos Lászlónak, akik lelkesen és profi módon szervezték meg a verseny első, BME-s fordulóját, és utána is sokat segítettek a lengyelországi utunk szervezésében; valamint az Informatikai Központnak a verseny lebonyolításához szükséges termek rendelkezésre bocsátásáért.
Szintén köszönettel tartozunk dr. Rónyai Lajosnak és a Matematikai Intézet Algebra tanszéke munkatársainak, a Villamosmérnöki és Informatikai Karnak, a VIK Hallgatói Képviseletének és a Rektori Hivatalnak a kiutazásunkhoz nélkülözhetetlen anyagi támogatás felkutatásáért és adminisztrálásáért.
A megoldott példák száma:
0 csapat oldott meg 8 példát
2 csapat oldott meg 7 példát
1 csapat oldott meg 6 példát
1 csapat oldott meg 5 példát
7 csapat oldott meg 4 példát
13 csapat oldott meg 3 példát
14 csapat oldott meg 2 példát
14 csapat oldott meg 1 példát
8 csapat oldott meg 0 példát
Összesen 60 csapat Közép-Európából.
A közép-európai fordulón született magyar eredmények:
(4 jó megoldás, 11. helyezés) Pilászy István (BME III. Info.) - jobbra, Rácz Balázs(BME III. Alk. mat.) - balra, Szabó Péter (BME III. Info.) - középen
(3 jó megoldás, 18. helyezés) Golda Bence (BME II. Info.) - balra, Ritter Ádám (BME I. Info.) - középen, Sinóros-Szabó Péter (BME III. Info.) - jobbra
(2 jó megoldás, 25. helyezés) Budapest - ELTE
(2 jó megoldás, 28. helyezés) Budapest - ELTE
(2 jó megoldás, 34. helyezés) Szeged - SZTE
(2 jó megoldás, 38. helyezés) Szeged - SZTE
(1 jó megoldás, 42. helyezés) Debreceni Egyetem
(1 jó megoldás, 47. helyezés) Debreceni Egyetem
Ajánlott URL-ek:
– az idei BME egyetemi (1.) forduló lapja: résztvevők, feladatok, tesztvektorok, mintamegoldások, eredmény
http://www.iit.bme.hu/~szirmay/acm/
– az idei közép-európai (2.) forduló lapja: résztvevők, feladatok, eredmény
http://cepc.mimuw.edu.pl:8002/
– ACM versenyekről általában
– régebbi ACM versenyfeladatok
http://www.acm.inf.ethz.ch/ProblemSetArchive.html
– rengeteg ACM-hez hasonló feldat, webes kiértékeléssel
A beszámolót írta:
Szabó Péter <pts@fazekas.hu>