З 18 по 22 квітня цього року в столиці Королівства Швеції Стокгольмі відбувся 33-й фінал світу зі спортивного командного програмування – The 2009 ACM-ICPC World Finals. Від України цього разу в змаганнях брало участь аж три команди, які представляли відповідно Київський національний університет імені Тараса Шевченка, Київський національний університет “Київський політехнічний інститут” і Таврійський національний університет імені Володимира Вернадського.
Стокгольм – найбільше місто Швеції з населенням 850 тисяч, розміщене на східному узбережжі озера Меларен. Саме тут є головна резиденція шведського короля. Місто побудоване на 14-ти не зв’язних один з одним островах. Перша частина назви – “сток” – означає колоду, друга – “голм” – маленький острів. Шведська столиця зустріла учасників зовсім не весняною погодою. Пронизливий вітер і холодний дощ зі снігом нагадували про забуті вдома шапку та рукавиці. Проте краса стокгольмських островів не залишила нікого байдужим. Особливо сподобалася екскурсія на катері, що відбулася другого дня олімпіади. Зовсім не дивно, що водний транспорт тут дуже розвинений – замовити водне таксі в Стокгольмі не становить проблеми.
Як і урочистий бенкет на честь нобелівських лауреатів, відкриття фіналу цьогорічної олімпіади відбувалося в приміщенні міської ратуші, а змагання – в бібліотеці Королівського технологічного інституту (Kungliga Tekniska hogskolan, KTH). Цей навчальний заклад засновано у 1827 році. Він є одним з найкращих технічних університетів Європи, а також, разом з технологічним університетом міста Гельсінкі, – найбільшим технічним ВНЗ Скандинавії.
Перемогу в змаганнях здобула команда Санкт-Петербурзького державного університету інформаційних технологій, механіки та оптики. Головні претенденти на цьогорічну перемогу – китайська команда Tsinghua University – фінішувала на другій позиції.
Українські команди цього разу, на жаль, не змогли вибороти жодного комплекту медалей фіналу світу, але варто зазначити, що вперше Україну в фіналі представляло аж три команди. Нагадаємо, що торік команда Львівського національного університету імені Івана Франка вперше виборола для України золоті медалі. Також на регіональних змаганнях Україна вже декілька років поспіль не поступається першим місцем іншим країнам. Усе це свідчить про швидкий темп розвитку спортивного програмування в Україні. Тож уже невдовзі можемо очікувати на нові перемоги.
ACM-ICPC – найбільша студентська командна олімпіада з програмування серед університетів усього світу. Її щороку проводить Association for Computing Machinery – найдавніша і найбільша міжнародна організація в комп’ютерній галузі зі штаб-квартирою в Нью-Йорку, що об’єднує близько 83 тисяч фахівців. Організаційний центр змагань розміщено в американському Baylor University, а виконавчим директором уже багато років є професор цього університету William B. Poucher.
Витоки міжнародного командного чемпіонату з програмування сягають змагань, що їх проводили в Техаському університеті в 1970 році. Формату сучасних змагань він набув 1977-го, коли вперше чемпіонат провели в рамках наукової конференції ACM. З 1977 по 1989 в олімпіаді брали участь здебільшого команди зі США та Канади. Сьогодні олімпіада – це змагання цілої планети. Для прикладу, у 2008 році в них узяло участь близько 6700 команд, а в фіналі за головний трофей боролися 100 найкращих команд світу. За статистикою, кількість команд щороку зростає на 10-20%.
Олімпіада складається з кількох етапів. Чимало університетів організовує внутрішні змагання, щоб визначити найкращі команди, які представлятимуть ВНЗ на регіональних змаганнях. Потім проводять національні та регіональні змагання планетного рівня. Найкращі команди з кожного регіону планети беруть участь у фінальному етапі чемпіонату світу. На відміну від регіональних змагань, у фіналі кожен університет може представляти тільки одна команда.
Участь у таких змаганнях беруть команди в складі трьох студентів. Також до участі допускають аспірантів. Проте учасник, який побував на двох фіналах чи на п’яти регіональних змаганнях, більше не може брати участі в олімпіаді.
Упродовж змагань кожній команді видають один комп’ютер і набір задач на п’ять годин. Команди пишуть розв’язки задач алгоритмічними мовами програмування C, C++, Java і відсилають їх на сервер для тестування. Програми тестують на чималій кількості різноманітних тестів, які невідомі учасникам. Якщо програма видала неправильну відповідь або не вклалася в обмеження часом чи пам’яттю, команда отримує про це повідомлення і може відсилати на тестування нову, виправлену версію. Задачу вважають розв’язаною, якщо програма дала правильні відповіді на всі тести. На відміну від інших олімпіад, часткові розв’язки не враховують.
Перемагає команда, яка правильно розв’язала найбільшу кількість задач. Якщо декілька команд розв’язали однакову кількість задач, то їхні позиції в рейтингу визначають штрафним часом. Спочатку штрафний час кожної команди дорівнює нулю. За кожну правильно розв’язану задачу до штрафного часу додають час (у хвилинах), що минув від початку змагань до моменту здачі. Якщо ж перед цим у команди було декілька невдалих спроб здати цю ж задачу, то за кожну з них до штрафного часу команди додають 20 хвилин. За невдалі спроби здати задачу, яку команда так і не змогла розв’язати, штрафний час не нараховують.
Відмінність таких змагань від інших олімпіад полягає в тому, що команда має розв’язати порівняно значну кількість задач за відносно малий час. Ураховуючи те, що кожна команда має у своєму розпорядженні лише один комп’ютер, уміння ефективно працювати в команді виходить на перший план.
Фінал змагань відбувається в різних містах світу. Цього року – в Стокгольмі, наступного – в китайському місті Харбін, де олімпіада пройде паралельно з відомим міжнародним фестивалем льодяних ліхтарів і скульптур. У 2011-му фінал переїжджає до столиці Малайзії – міста Куала-Лумпур, а в 2012-му найкращі програмісти світу поїдуть у Варшаву. Тож, можливо, програмування не завжди є таким нудним, як воно видається на перший погляд.
Василь Білецький
Від редакції
У 2008 році в житті нашого Університету сталася визначна подія – команда зі спортивного програмування ЛНУ ім. Івана Франка в складі Василя Білецького, Остапа Коркуни та Руслана Бабілі завоювала вперше в історії України одну з 4 х золотих медалей студентського командного чемпіонату світу з програмування, що проходить щороку під егідою ACM (Association for Computing Machinery). 32-й фінал світових змагань відбувся 9 квітня 2008 р. в місті Банф (Альберта, Канада) і став історичним для України.
Після перемоги нашої університетської команди в Канаді сьогодні відбувається бурхливий розвиток спортивного програмування як інтелектуального виду спорту в Україні. Тому не випадково, що від України цього разу у світових змаганнях зі спортивного програмування брало участь аж три студентські команди.
Пропонуємо увазі читачів матеріал про цьогорічний командний чемпіонат світу зі спортивного програмування Василя Білецького, якого запросили як почесного гостя організатори фіналу світових змагань.