КОМАНДА З УКРАЇНИ ВПЕРШЕ ВЗЯЛА «ЗОЛОТО» НА ЧЕМПІОНАТІ СВІТУ ЗІ СПОРТИВНОГО ПРОГРАМУВАННЯ

9 квітня 2008 року в місті Банф (Альберта, Канада) під егідою ACM (Association for Computing Machinery) відбувся фінал 32-го студентського командного чемпіонату світу зі спортивного програмування.

Команда Львівського національного університету імені Івана Франка у складі Василя Білецького, Остапа Коркуни та Руслана Бабілі (всі вони з факультету прикладної математики та інформатики – декан Ярема Савула) завоювала одну з чотирьох золотих медалей.

1995 року команда Київського національного університету імені Тараса Шевченка стала першою командою з країн колишнього СССР, що взяла участь у фіналі студентського чемпіонату світу зі спортивного програмування. Однак лише цього року львівські студенти стали першими українцями, що завоювали «золото» у фіналі чемпіонату світу.

Команда Вінницького національного технічного університету, яка також виступала в цьогорічному фіналі, розв’язала чотири задачі й зайняла 32-е місце.

Чемпіонами світу 2008 року стала команда Санкт-Петербурзь­кого університету інформаційних технологій, механіки та оптики. На другому місці студенти Массачусетського технологічного інституту (США), третє місце дісталось команді Іжевського ДТУ.

У відбіркових турах цьогорічного чемпіонату взяли участь 6700 команд з 1821 університету 83 країн світу. Для фінальних змагань було відібрано 100 команд.

Слід зазначити, що минулого року в Бухаресті команда ЛНУ імені Івана Франка стала переможницею Південно-Східного півфінального змагання 32-ї першості світу зі спортивного програмування. Українські команди тоді посіли три призові місця – друге місце дісталося команді Вінницького національного технічного університету, третє місце вибороли студенти Київського національного університету імені Тараса Шевченка. Львівська команда у півфіналі розв’язала всі запропоновані дев’ять задач всього за дві години з відведених п’яти, встановивши своєрідний рекорд півфіналів. Підтвердженням високого класу української команди, продемонстрованого у півфіналі, став чудовий виступ львів’ян у фіналі – золота медаль на чемпіонаті світу в Канаді. Щоб зайняти третє місце команді ЛНУ імені Івана Франка забракло двох хвилин.

Львівські студенти привернули до себе увагу експертів зі спортивного програмування близько двох років тому, коли на Інтернет-контест серверах несподівано яскраво проявив себе самородок Василь Білецький, до цього не відомий в середовищі спортивного програмування.

Окрім уміння програмувати заняття спортивним програмуванням потребує серйозних знань в галузі математики й алгоритмів, а також постійних тренувань. Завдяки своїй наполегливості львівські студенти змогли забезпечити собі належні умови для інтелектуального розвитку. Вони беруть активну участь в різноманітних міжнародних змаганнях, зокрема TopCoder.com, а також проводять власні тренування та змагання. Вони, зокрема, внесли свою частку до конкурсної програми фестивалю DE:CODED^08, де пройдуть змагання за правилами ACM і TopCoder, в яких зможуть взяти участь всі бажаючі. Слід зазначити, що Львів – єдине зі всіх міст Східної та Західної Європи, в якому заплановано проведення спеціального онсайт-конкурсу TopCoder вже цієї весни. Популяризації спортивного програмування у Львові та за його межами сприяє створений львівськими студентами веб-сайт «АСМ Контестер», який став осередком для Інтернет-спілкування зацікавлених учнів та студентів зі всієї України.

Коротко про суть змагань ACM ICPC. Чемпіонати світу з програмування за версією ACM проводяться з 1977 року за багаторівневою системою (спершу відбіркові змагання, потім – фінальні). 1977–1985 рр. у змаганнях брали участь тільки північноамериканські команди. Першою командою поза США і Канади, що взяла участь в змаганнях 1986 року, стали студенети з Нової Зеландії. Генеральним спонсором змагань сезону 1997–1998 рр. є компанія IBM.

За правилами чемпіонату світу, в змаганнях можуть брати участь команди університетів у складі трьох членів. Кожен учасник має бути студентом або аспірантом. При цьому одній і тій же людині заборонено виступати більш ніж у двох фіналах. На час змагань (зазвичай він триває п’ять годин) кожній команді надається один комп’ютер із встановленими на ньому засобами розробки програм і виходом на систему автоматичного або напівавтоматичного (як це прийнято в фіналі) тестування. Для розв’язування завдань учасникам пропонується від восьми до дванадцяти задач. Розв’язком кожної має бути програма на одній з прийнятих на змаганнях мов програмування (цього року – Java, C, C++). Якщо команда вважає, що розв’язок готовий, вона надсилає його на тестування. Система тестує розв’язок на заздалегідь заданому автором задачі наборі тестів. Якщо на якомусь тесті програма некоректно завершилася, перевищила заданий в умові задачі час роботи на одному тесті або дала неправильну відповідь, то команда отримує коротке повідомлення про помилку. При цьому сам тест, на якому виникла помилка, команді не повідомляється. Якщо ж програма правильно відпрацювала на всіх тестах, то задача команді зараховується. Крім того, до «штрафного часу» додається час від початку змагань до моменту здачі задачі, а також по 20 хвилин за кожну невдалу спробу здати цю задачу. Перемагає команда, яка здає найбільше задач, а якщо таких команд кілька – та з них, що отримала найменший «штрафний час».

Учасники змагань, які посіли 1–4 місця, отримують золоті медалі, з 5-го по 8-е – срібні, місця з 9-го по 12-е – бронзові. Відбір на фінальні змагання проводиться за багатоступеневою схемою: всі університети світу розбиті на регіони за територіальною ознакою, в них і проводяться півфінали. Найбільші регіони розбиті на підрегіони, а відбір до півфіналу здійснюється за результатами чвертьфіналів. У деяких регіонах (наприклад, у Китаї) вже проводяться і 1/8 фіналу. Для кожного півфіналу щороку визначається квота команд, які виходять від півфіналу у фінал, при цьому у фінальних змаганнях не може брати участь більше одної команди з однієї і тієї ж вищої школи. Квота, яка надається регіонові, залежить від кількості команд цього регіону, що брали участь у відбіркових змаганнях, а також результатів, показаних регіоном, та деяких інших факторів. За результатами фіналу визначаються чемпіони континентів, тобто краща команда серед усіх, що вийшли у фінал з приписаних до континенту регіонів.

Підготував Олег РОМАНЧУК,
шеф-редактор журналу «Універсум»

За матеріалами, люб’язно наданими факультетом прикладної математики ЛНУ імені Івана Франка.