Півфінальний етап найпрестижнішої студентської олімпіади з програмування – ACM Programming Contest пройшов 19-22 жовтня в Бухаресті (Румунія). Тут змагалися 40 команд з Румунії, Болгарії, Молдови, Сербії, Угорщини, Ізраїлю та України, які представляли 31 навчальний заклад. Загалом зібралося 170 учасників.
Серед команд, які представляли Україну, дві було з КПІ: перша у складі Кирила Веденського, Володимира Гігіняка та Олександра Рибака (всі з ФТІ) та друга у складі Володимира Ткачука (ФТІ), Володимира Качуровського (ФТІ) та Дмитра Кордубана (ІПСА), тренер – Ірина Жданова, доцент ФТІ. Результат, який показали наші команди, без перебільшення можна назвати видатним, адже обидві зайняли призові місця – перше і третє. До цього жодному ВНЗ України не вдавалося “взяти” два призових місця одночасно.
Про перебіг подій розмовляємо з Володимиром Гігіняком.
– Як було зорганізовано змагання?
– Офіційно олімпіада займає три дні: перший – відкриття і пробний тур, де учасники могли ознайомитися з програмним забезпеченням та перевірити працездатність системи. Другий день – основний тур. Він тривав п’ять годин, протягом яких команди мали розв’язати дев’ять задач. Переможець визначається за кількістю розв’язаних задач, а також за штрафними балами, які залежать від швидкості розв’язання та від кількості невдалих спроб. Цікаво, що за півгодини до закінчення змагання поточні результати команд перестають бути видимими, і про підсумки олімпіади команди дізнаються вже на церемонії нагородження, яка проходить через декілька годин після закінчення випробувань. Тож учасникам якийсь час доводиться добряче нервувати. Ну а далі – культурна програма (екскурсія).
– Як готувалися до турніру, в чому, на Вашу думку, “секрет” високих результатів?
– До високого результату ми йшли цілих чотири роки, кожного разу займаючи все більш високі місця. За цей час, у результаті постійних тренувань, участі в різноманітних українських чемпіонатах та інтернет-змаганнях, у нашій команді для кожного чітко визначилися “ролі”. Це дуже важливо, бо під час олімпіад команді відводиться тільки один комп’ютер, тому результат напряму залежить від ефективного використання часу. Олександр Рибак у нас займається теоретичним розв’язанням важких алгоритмічних та математичних задач. Кирило Веденський дуже швидко розв’язує і програмує, тому перші години змагання комп’ютерний час належить йому. До того ж він є капітаном команди, тому приймає рішення: хто яку задачу має розв’язувати і програмувати. Я, Володимир Гігіняк, програмую важкі алгоритмічні задачі, мій час – наприкінці змагання.
– Задачі виявилися дуже каверзними?
– Виступ нашої команди у півфіналі був досить драматичним. Перші три прості задачі ми розв’язали дуже швидко, і впевнено йшли на першій позиції. Згодом “здали” і четверту. А далі з нами трапилася історія, яка повторювалася з року в рік уже чотири рази, скільки ми брали участь у півфіналах. За всіма ознаками проста задача – ніяк не здавалася. У такій ситуації команда втрачає багато часу і до того ж заробляє штрафні бали. Поки ми з нею боролися, нас обійшло близько п’яти команд, які на той час мали п’ять-шість зданих задач. Нарешті нам вдалося зібратися, і за годину ми здали ще дві задачі і знайшли помилку в тій самій проблемній “простенькій” задачі. Таким чином ми і ще дві команди мали по сім задач. На першому місці були румуни, на другому і третьому – КПІ. У нас залишилось дві задачі, одна з яких вимагала дуже багато часу на реалізацію (в результаті її не здала жодна команда), а друга гарантовано не мала швидкого правильного алгоритму розв’язання. Але оскільки останню здало декілька команд, то досвід підказав, що існує неправильний в загальному випадку алгоритм, який все ж таки може дати правильну відповідь на авторських тестах. Саме так все і сталося, отож ми здаємо восьму задачу за сорок хвилин до закінчення – і нам залишається лише чекати. Тільки через чотири години, коли координатор змагань оголосив, що лише одна команда розв’язала вісім задач, стало зрозуміло, що ми перемогли!
– Що було потім?
– У піднесеному настрої пройшла церемонія нагородження, окрім цінних призів від спонсорів олімпіади нас очікував найголовніший – участь у фінальній частині ACM олімпіади, яка проходитиме в березні у Токіо. Наступного дня нас повезли на екскурсію у Трансільванію з відвідуванням замку Бран – замку графа Дракули.
– Які найближчі плани у переможців?
– Тепер нас очікують чотири місяці напружених тренувань, а потім виступ у фіналі. Сподіваємося на вдалий виступ на цих важливих змаганнях.