Magyar diákok az orosz Szilícium-völgyben

Beszámoló az Innopolis Open 2020 döntőjéről és a vele együtt szervezett programozó táborról

Oroszország a versenyprogramozás egyik nagyhatalma, Kína mögött második a Nemzetközi Diákolimpián szerzett érmek számában, mögöttük az Egyesült Államok a harmadik. Az orosz versenyzők közössége nemzetközi szinten is sokat tesz a programozási versenyek népszerűsítéséért és a tudásuk megosztásáért, a fiatalok oktatásáért. Elég csak a Codeforces platformra, a CP-Algorithms weboldalra, vagy Petr Mitrichev blogjára gondolni. Az innopolisi egyetem által szervezett versenyt megnyitották nemzetközi résztvevők számára az utóbbi években, és idén a téli tábort is, így belepillanthattunk abba a tehetséggondozó munkába, amelyben a világ legjobb programozói nevelkednek.

Kazany mellett épül egy új város, Innopolis, amellyel Tatárföld vezetése az orosz Szilícium-völgyet szeretné megteremteni. Tartózkodásunk alatt sokat megtudtunk erről a projektről. A 2012-ben indult folyamat első lépéseként a nemzetközi diákokat ösztöndíjakkal csábító magánegyetemet építették föl, ahova a magyar diákok is meghívást kaptak.

Ez a modern intézmény adott otthont a versenynek és a versenyre felkészítő tábornak. Az egyetem után egy hatalmas irodaház, a Technopark épült meg, ahol kedvező feltételekkel létesíthetnek irodát a nagy orosz techvállalatok.

Innopolis 2020

Többek között itt fejlesztik a Yandex önvezető autóját, amelyet nekem is volt szerencsém kipróbálnom. A szervezők bevallották, hogy mivel ingyenes taxiszolgáltatást nyújtanak, ezért sokszor ezzel járnak munkába az öt perces séta helyett a dermesztő hidegben. A városnak jelenleg mintegy 5000 lakosa van, amelynek nagy részét az IT vállalatokban dolgozó informatikusok családjai teszik ki.

Az egyetemen nagyjából 700 diák tanul, a világ 33 országából. Évente több, mint 10 000 jelentkezőből választják ki a 250 hallgatót, akik megkezdhetik náluk a tanulmányaikat.

Innopolis, Egyetem

Az Innopolis Open középiskolások számára megrendezett rangos nemzetközi programozási verseny. Két online selejtező forduló után választották ki azt a mintegy 250 versenyzőt, akik a helyszíni döntőn részt vehettek. A 2016/17-es tanév óta rendezik meg, azóta minden évben voltak magyar versenyzők a döntőben is. Idén öt magyar diák utazott kíséretemmel a versenyre: Deák Bence, Horcsin Bálint, Németh Márton, Szente Péter és Tóth Gellért. Első alkalommal mindannyian részt vehettünk az egyetem által szervezett egyhetes felkészítő táborban.

A tábor minden napján 6 óra szakmai munka volt, 4 óra délelőtt, és 2 óra délután, bár a fiúk a szabadidő egy részét is kódolással töltötték. Elvileg kötelező volt számukra a délutáni egy órás sportprogram, viszont a szervezők hamar rájöttek, hogy ez nem működik jól, így társasjátékokat is lehetett játszani, valamint a pingpongot is felvették a sportprogramba. Esténként a tábor önkéntesei nagyon jó hangulatú vetélkedőket és játékokat szerveztek a gyerekek kívánságainak figyelembe vételével.

Minden nap egy-egy témát dolgoztak fel a diákok. Az oktatás általában két részből állt, elsőként egy előadást hallgattak az adott témakörről, amelynek során rendszerint néhány tipikus feladaton keresztül tanulták meg az algoritmusokat és problémamegoldási módszereket.

Innopolis, Egyetem

Ezután kifejezetten az adott témakörhöz alkotott feladatokat oldottak meg, amelyek egy része elhangzott az előadásban, a többi hasonló elvű új feladat volt. Nagyon jónak tartom, hogy a diákok kaptak időt arra, hogy a tanultakat le is kódolják, hiszen ez a megértés egy újabb szintje, amikor önállóan reprodukálni és új helyzetekben alkalmazni is tudják az algoritmusokat.

A saját módszertanomhoz ennél már csak az áll közelebb, ha az előadás előtt kapnak feladatokat, hátha önmaguktól rájönnek a megoldás néhány elemére.

Volt két olyan nap is, ami feladatmegoldással indult. Az egyik napon egy versenyfeladatsort, a Japanese Olympiad in Informatics 2020 döntőjének feladatait kellett megoldaniuk. Egy másik napon pedig nagyon érdekes, rendhagyó feladatok voltak. Például egy kétszemélyes játékban egy véletlenszerűen játszó ellenfél legyőzése minél nagyobb eséllyel (ahol természetesen mindkét játékos program). Egy másik példa fekete-fehér képek rajzolása minél kevesebb lépésben egy olyan robot irányításával, amely csak másolni tudja a pixel színét valamelyik szomszédos pixelre. Ezeket a diákok rendkívül élvezték.

A többi nap témakörei a következők voltak:

  • NP-teljes problémák és backtrack optimalizációk, meet-in-the-middle módszer
  • Geometriai algoritmusok, söprő egyenes, sokszögek Minkowski összege
  • Aho-Corasick algoritmus karaktersorozatok feldolgozására
  • DP optimalizációk: konvex burok optimalizáció, Knuth optimalizáció, oszd meg és uralkodj módszer
  • Square Root Optimization

Mindegyik témakör nekem is nyújtott számos újdonságot, bár részben ismertem őket. A legnagyobb élmény nekem a konvex sokszögek Minkowski összege volt, amely egy gyönyörű geometriai konstrukció, és segítségével nagyon hatékony algoritmus adható két konvex poligon közötti legrövidebb távolság meghatározására.

Magyar diákok Innopolisban

A hét napos tábor egyetlen csalódása számomra az volt, hogy az orosz diákok nem vettek részt az angol nyelvű foglalkozáson, nekik külön csoportokban folyt az oktatás, oroszul. Véleményem szerint a kapcsolatépítés szempontjából is jobb lett volna, ha minden oktatás angolul zajlik az orosz és nemzetközi diákoknak együtt. A tábor után egy pihenőnap következett, amelynek végén a verseny megnyitója és egy tesztforduló volt, a számítógépek és a rendszer kipróbálására. Az egyetem hatalmas, kétszintes olvasóhelyiségét megtöltötték az íróasztalok, laptopok és a tehetséges diákok szerte a világból.

Vasárnap következett a verseny. Még reggel egy-két utolsó jó tanáccsal elláttam a fiúkat, amiket nagy örömömre meg is valósítottak. Nekünk csapatvezetőknek egy workshopot rendeztek a szervezők, amely nagyon hasznos volt, minden ország képviselője beszélt a tehetséggondozó rendszeréről, és a nemzetközi versenyekről. Eközben Magyarország meghívást kapott egy Bulgáriában rendezett versenyre, az International Autumn Tournament in Informatics-ra.

Viszont a feladatokat csak a verseny végéhez közel kaptuk meg, és a verseny állását is csak két órával a kezdete után tudtuk elkezdeni követni. Innentől kezdve folyamatosan nagy izgalom volt követni a fiúk pontszámát és helyezését. Deák Bence és Tóth Gellért folyamatosan a mezőny első negyedében volt, váltották egymást a legjobb magyar versenyző pozíciójában, végül mindketten harmadik díjat kaptak azonos pontszámmal, 373 ponttal (az 500-ból), ami kimagasló teljesítmény ilyen erős nemzetközi mezőnyben. Németh Márton, Szente Péter és Horcsin Bálint is több, mint 200 pontot értek el, büszke vagyok rájuk.

Peti a legjobb helyezett lett azok közül, akik 0 pontot kaptak a második feladatra :) Ha ezt a nem túl nehéz feladatot megoldja, még sokkal előrébb végez. Marci a saját évfolyamán, a kilencedikesek között a 13. legjobb helyezést érte el. Ő az elkövetkező pár évben komoly sikereket érhet el.

A verseny feladatai klasszikus témakörökre épültek, mégis kellő nehézségűek voltak, hogy a legokosabb diákok között is különbséget tegyenek. Nemsokára  elérhetőek lesznek a verseny honlapján (https://olymp.innopolis.ru/en/ooui/information/archive/). Az első feladatot mohó algoritmussal lehet megoldani, a második egy jól ismert dinamikus programozási feladatra, a hátizsák problémára épült. Ez a feladat a következőképpen hangzott: egy pólórendelésben adott a különböző színű pólók mennyisége, de ezek a számok külön-külön jelenthetnek darabszámot, vagy százalékos arányt is, ezt nem tudhatjuk. Meg kell határozni a pólók összes lehetséges össz darabszámát. (Feltéve, hogy legalább az egyik szám darabszám, ez szükséges.) A megoldáshoz dinamikus programozással ki kell számolni, hogy ha a számok bármely részhalmaza jelent százalékos értéket, akkor ezek összege mennyit tehet ki, és ekkor mennyi a pólók összes darabszáma. Valamint ellenőrizni kell, hogy minden százalékos érték egész darabszámot fejez ki.

Az ötödik feladatot oldották még meg sokan, amelyben szintén mohó algoritmust kellett alkalmazni fejlett adatszerkezetekkel kombinálva. A negyedik feladat témája egy téglalap színezése volt, de a megoldásához gráfalgoritmusok kellettek.

A harmadik feladatot oldották meg a legkevesebben, mindössze hét versenyző ért el maximális pontot ebben a kombinatorika feladatban, amely hétszegmenses kijelzőkről szólt. Három diák ért el maximális pontot a versenyen. Közülük Ildar Gainullin már 3 óra alatt kész volt az 5 órás verseny feladataival, de nem lepődtünk meg, mert ő egy sztár ebben a közösségben. A Codeforces oldalon, ahol felnőttek, profi programozók is részt vesznek a versenyeken, jelenleg a világon 7. helyre van rangsorolva. Nagy élmény volt hozzá hasonló figurákkal együtt tölteni ezt a másfél hetet.

A hazautunk kissé kalandosra sikerült, mivel a hóvihar miatt nem tudott felszállni a repülőnk, csak 15 órával később indultunk a tervezettnél, így vízumot is kellett hosszabítanunk. A diákok viszont mindvégig jó hangulattal és kellő kitartással bírták a reptéren töltött éjszakát.

Számomra tapasztalatok és kapcsolatok szempontjából is rendkívül értékes volt a tábori részvétel, mivel erről a témáról, programozás tehetséggondozásról írom a doktorimat. A diákjaink sokat fejlődtek a bő egy hét alatt, és különösen örülök annak, hogy barátságok is fonódtak köztük. A versenyen elért siker csak hab a tortán. Remélem, hogy a jövőben még sok ehhez hasonló eseményre kísérhetem a magyar csapatot.

Az utazásunkat az Innovációs és Technológiai Minisztérium és az NJSzT támogatta, akiknek rendkívül hálás vagyok.

Nikházy László

Magyar diákok Kazanyban