Beszámoló az 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-három 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. Hollywoodban rendeznek. A csapatok főleg a dicsőségért és ösztöndíjakért, álláslehetőségeké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 hatá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, aki a legtöbb jó megoldást adja be, döntetlen esetén egy speciálisan számolt időeredmény dönt (az győz, aki 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, time limit exceeded). 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: mindegyiben 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. Gyakran 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. Persze minden feladatsorban van legalább egy példa, melynek optimális futási idejű megoldás a kiegyensúlyozott keresőfát igényel. 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(n^2.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 is 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, két-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. Idén az időjárással is hihetetlen szerencsénk volt: november közepén is kora őszi meleg fogadott bennünket. Láttunk lengyeleket az utcán fagyizni.J

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 se 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 megadni. 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. Pusztán az értékelés specifikációjának (futáshoz használható memória limite) utolsó pillanatbeli lazítása okozott némi gondot, melyet utólag korrigáltak, ám a verseny végeredményében alig okozott változást.

Szombaton, a versenyt megelőző napon két érdekes előadást hallgattunk meg (angolul) az egyetemen: az első előadó a Szilikonvölgy emberének életviteléről, munkastílusáról és lehetőségeiről beszélt, a második pedig a molekuláris biológia egy számítástudományi problémájában frissen elért eredményekről számolt be közérthetően. 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 csupán egy problémát találtunk, 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. (A BME válogatóversenyén ez a probléma nem jelentkezett.)

A versenyen a legjobb teljesítményt a lengyelek nyújtották, az első 6 csapat közül 4 lengyel volt. A házigazda két csapata magasan verte a mezőnyt 7, illetve 5 sikeres megoldással, míg a harmadik helyezett csak 3 helyes példát adott be, s ezzel jutott ki Hollywoodba. (Negyedik(!) a BMEII., szintén három megoldással.)

A feladatok igen nehezek voltak, ez jól látható a mezőny teljesítményéből is. A csapatok mintegy fele nyolcból egyetlen példát sem tudott megoldani! De messze nem voltak megoldhatatlanok a feladatok, egy jó algoritmustervező és kódolási képességeket, stabil, nyugodt versenyrutint felvonultató csapat könnyen kijuthatott volna idén a világbajnokság döntőjébe is. Talán lehetett volna kicsit több könnyebb feladatot is berakni, hogy több 3-4-5 példát megoldó, és kevesebb sikerélmény nélkül távozó 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áció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 gondolkozni, 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 BME által szervezett 24 órás programozási 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 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.

Nagy segítséget nyújtott azonban idén a válogatóverseny előtt Benedek Balázs, Friedl Katalin és Marx Dániel vezetésével tartott felkészítő előadássorozat, melyben rengeteg valódi ACM feladatot dolgoztunk fel tematikusan. Reméljük, ennek lesz folytatása is a jövőben akár egy választható tárgy formájában is, amelynek fő célja az algoritmuselméleti 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 alap Algoritmuselmélet 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ő három helyén olyan csapatok végeztek, amelyekben egy (vagy több) volt kettős diákolimpikon szerepelt. Talán az a legfontosabb, hogy ,,sokat látott emberek legyenek a csapatban. Ekkor van esély arra, hogy a szükséges trükkök korábbi feladatok analógiájaként felfedezhetőek legyenek. Szintúgy hihetetlenül fontos, hogy rutinos, jó kódoló legyen aki a programot írja. Hiába tudná ugyanis egy csapat elméletben az összes feladatot megoldani, ha a program írásakor apró programozási hibák miatt órákat kell hibakereséssel töltenie a versenyidőből.

Összefoglalva: a diákolimpá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) valamint Friedl Katalinnak és Rónyai Lajosnak, akik lelkesen és profi módon szervezték meg a felkészítést és a verseny első, BME-s fordulóját, majd utána is sokat segítettek a lengyelországi utunk szervezésében, különös tekintettel az anyagi fedezet előteremtésére.

Köszönjük továbbá támogatóinknak – a BME Informatikai Központnak, a BME Rektori Hivatalnak, a Számítástudományi és Információelméleti Tanszéknek valamint a Matematikai Intézetnek – hogy lehetővé tették csapataink eredményes szereplését, mind a válogatóverseny feltételeinek biztosításával, mind az utazási költségek és nevezési díjak fedezésével.

A Közép-Európai Programozási Versenyt 2003-ban is a Varsói Egyetem rendezi, azonban a 2004-től kezdődő három éves periódus sorsa még nyitott. Előzetes hírek alapján a BME jó eséllyel indulhat a rendezés jogáért.

Szabó Péter, Rácz Balázs

A közép-európai fordulón született
magyar eredmények

BME II.:

3 megoldott példa – 4. helyezés

Darabos Dániel (Info IV.)

Felföldi Zsolt (Info IV.)

Németh András (Info IV.)

BME I.:

2 megoldott példa – 13. helyezés

Földényi Tamás (Info I.)

Hargitai Gábor (Info I.)

Pallos Péter (Info I.)

BME III.:

2 megoldott példa – 14. helyezés

Rácz Balázs (Mat. IV.)

Ritter Ádám (Info II.)

Szabó Péter (Info IV.)

28. helyezést ért el 1 megoldott példával az ELTE I. csapat, a további magyar csapatok (ELTE II., BMF, Debrecen I., Debrecen II., Szeged I., Szeged II.)
nem adtak be helyes megoldást.

A mezőny teljesítménye

0 csapat oldott meg 8 példát

1 csapat oldott meg 7 példát

0 csapat oldott meg 6 példát

1 csapat oldott meg 5 példát

0 csapat oldott meg 4 példát

5 csapat oldott meg 3 példát

15 csapat oldott meg 2 példát

8 csapat oldott meg 1 példát

31 csapat oldott meg 0 példát

Összesen 61 csapat Közép-Európából.

Ajánlott URL-ek

– az idei BME egyetemi (1.) forduló lapja (résztvevők, feladatok, tesztvektorok, mintamegoldások, eredmény): http://www.cs.bme.hu/acm/

– az idei közép-európai (2.) forduló lapja (résztvevők, feladatok, eredmény): http://cepc.mimuw.edu.pl/

– az ACM versenyekről általában:
http://icpc.baylor.edu/icpc/

– régebbi ACM versenyfeladatok:
http://www.acm.inf.ethz.ch/ProblemSetArchive.html

– rengeteg ACM-hez hasonló feldat, webes kiértékeléssel: http://acm.uva.es/problemset/