За результатами півфіналу світу зі спортивного програмування, який відбувся в Бухаресті (див. “Каменяр” №9 за листопад 2010 р.), команда Львівського національного університету імені Івана Франка “LNU United” пройшла на Фінал світу ACM ICPC, який відбудеться в Орландо (США, штат Флорида) 30 травня 2011 року. На Фінал світу запрошено 105 найкращих команд із шести континентів, які вибороли цю можливість серед 8305 команд із 2070 університетів, що представляли 88 країн. 2011 рік для України – рекордний, оскільки нашу країну представлятимуть аж 4 команди: Київського національного університету імені Т. Шевченка, Донецького національного університету, Таврійського національного університету імені В. Вернадського і Львівського національного університету імені Івана Франка. Склад команди ЛНУ ім. Івана Франка: Ігор Євчинець, Павло Кушнір, Олександр Воєца, тренери – Руслан Бабіля та Василь Білецький.
У звичних для нас видах спорту (футбол, баскетбол) перед великими стартами відбуваються тренувальні збори; у спортивному програмуванні також є збори різних рівнів. Найпрестижніші – в Петрозаводську (Росія), що відбуваються вже десятий рік поспіль. Цього року в них брали участь 20 майбутніх фіналістів світу, зокрема всі 5 переможців європейських півфіналів, були представники 7 країн, з України – 5 команд. Збори можна назвати справжньою генеральною репетицією перед Фіналом світу. Оскільки нашу команду запрошено на Фінал світу, організатори зборів у Петрозаводську запросили нас узяти участь у тренуваннях; звісно, ми не могли пропустити такої нагоди й приїхали на збори оптимальним складом – 3 учасники (Ігор Євчинець, Павло Кушнір, Олександр Воєца) та 1 тренер (Руслан Бабіля). Збори тривали з 28 січня по 7 лютого, складалися з 9 змагальних днів і 2 днів відпочинку. Щодня був такий графік: змагання, які тривали класично – 5 годин, потім лекції від найкращих спортивних програмістів світу, далі – вільний час, можна було завершити не розв’язані під час змагання завдання або трохи відпочити й розім’ятися в спортзалі. Оскільки зібралися найсильніші команди, то всі розуміли, для чого вони так далеко їхали й намагалися використати час максимально ефективно, тому всі учасники постійно працювали над своїми розв’язками. На відміну від футболістів, які можуть прийти додому і, лежачи на дивані, відпочивати, у спортивних програмістів навіть під час перебування в їдальні голова працює над задачами, декому правильні розв’язки навіть сняться. Класична ситуація: у вихідний день нам організували прогулянку на бігових лижах, і деколи було чути в лісі, як котрийсь лижник кричав своєму товаришу: “Я придумав, як зробити динаміку не за куб, а за квадрат!”. Такі “муки” не є даремними, оскільки через якийсь час на Фіналі світу між цими командами розігруватимуть звання абсолютного чемпіона світу.
Тренувальні змагання були надзвичайно корисними для нашої команди, відчутно зріс рівень. Також мали нагоду оцінити, хто змагатиметься за медалі на Фіналі світу – як з’ясувалося, конкуренція буде високою, бо рівень команд дуже сильний і, що найприємніше, команда ЛНУ ім. Івана Франка також має змогу боротися за найвищі нагороди. Найгірший результат нашої команди на цих тренувальних зборах – 36 місце дев’ятого змагального дня, а найкращий – третє місце за підсумками сьомого змагального дня. На збори ми насамперед їхали з бажанням порозв’язувати завдання високої складності, оскільки російська школа спортивного програмування славиться складними завданнями, які часто навіть складніші, ніж на фіналах світу. Автори змагань запропонували 95 завдань, команда “LNU United” успішно розв’язала 81 завдання, більше розв’язали тільки 5 команд.
Спортивне програмування віднедавна стрімко розвивається на пострадянському просторі. Провідну роль відіграє Росія, оскільки команди з цієї країни вже 6 разів ставали чемпіонами світу. Провідними центрами, звісно, є університети Москви та Санкт-Петербурга, але багато університетів із інших міст також дуже сильно виступають і ведуть боротьбу за найвищі місця. Такі високі результати російських команд – результат аналогічних до Петрозаводських тренувальних зборів, які відбуваються в Росії в багатьох регіонах майже цілий рік. Білорусь на найвищому рівні здебільшого представляє один університет – Білоруський державний університет. Команда з Грузії також досягала високих результатів. Донедавна Україну на Фіналі світу представляли тільки 2 університети зі столиці – Київський національний університет імені Т. Шевченка (бронзова медаль на Фіналі світу 2003 року) та Національний технічний університет України “КПІ”, до них приєдналися Вінницький національний технічний університет та Львівський національний університет імені Івана Франка. Команда нашого Університету в складі Василя Білецького, Остапа Коркуни та Руслана Бабілі 2008 року вперше для України на Фіналі світу зі спортивного програмування завоювала золоту медаль (див. “Каменяр” №6 за жовтень 2008 р.). Таких результатів досягнуто завдяки створенню осередків навколо ентузіастів, які розвивають спортивне програмування у своїх університетах.
У Харківському національному університеті радіоелектроніки (ХНУРЕ) вдалося реалізувати ідею зборів, аналогічних до петрозаводських, які відбуваються з 2008 року. Цього року харківські збори тривали 11–21 лютого. Наш Університет за підтримки компанії “Softserve” представляли три команди: професіонали “LNU United”, команда початківців з першого курсу “LNU Juniors” (склад: Павло Глова, Іван Миляник, Богдан Прищенко, тренер – Руслан Бабіля) та команда “Karpaty” (у складі Ярослава Костя, Івана Демчука, Михайла Козака, тренер – Іван Хвищун).
Руслан Бабіля
тренер команди
Розповідь учасника про збори в Харкові
Одного січневого вечора я дізнався, що в лютому вирушаю на тренувальні збори в Харкові. Ті самі збори, про які розповідали мені, ще коли я був школярем. У зборах брала участь також команда “LNU United”, яка активно готувалася до фіналу ACM ICPC.
Настав день відправлення, ніхто не запізнився на поїзд – усе складалося дуже добре. Я вперше в житті потрапив на Лівобережжя. На платформі в Харкові нас зустріли – не через якесь особливе ставлення – усіх учасників волонтери зустрічали на місці прибуття й супроводжували до ХНУРЕ.
Після прибуття до ХНУРЕ необхідно було пройти реєстрацію. Для досвідчених спортсменів ця процедура, мабуть, є звичною. Але вперше… Якось, із допомогою волонтерів та старших колег, ми зареєструвалися, сфотографувалися з пам’ятником програмістові, вирушили заселятися.
Здавалося б, перший день, вільний від змагальних турів – море вільного часу. Але цей час якось так непомітно летить… Поселення, розпакування речей, церемонія відкриття, вечеря… І тоді, після важкої подорожі й сповненого вражень дня, виникає бажання поспати.
Розклад дня, до якого ми звикли за наступні одинадцять днів: лекція, змагання, розбір завдань, “добивання”, підбивання підсумків. Далі дехто відпочивав, дехто проводив час за спілкуванням із однодумцями, “добиванням” задач та вивченням алгоритмів. Під час онлайн-листування з одногрупниками я зіткнувся з цікавим уявленням про збори: “Класно вам там, майже нічого не робите, одну лекцію посидіти, написати декілька програмок, а далі – халява! А в нас тут пари, “грузять”, складно…”. Хочеться розвіяти цей міф. Звісно, коли у вас є можливість одинадцять днів займатися справою, яка вам подобається, і не треба ні на що відволікатися – це приємне проведення часу. Але збори з програмування, як і будь-які інші тренувальні спортивні збори, – чимале навантаження, хоч і приємне. Не лише через любов до програмування, а й зі спортивного азарту та прагнення самовдосконалення багато учасників займалися складною розумовою працею 15–17 годин на добу.
Збори в Харкові не були жодною з крайностей: ідеться не про дві сотні фанатиків, котрі по 16 годин на день проводили на лекціях або за розв’язуванням задач, але також і не про зібрання туристів, які цілими днями вивчали Харків та бавилися в комп’ютерні ігри. Кожна із команд сама для себе обирала найоптимальніший варіант. Декому сподобалися організовані спільними зусиллями товариські міні-футбольні матчі о дев’ятій вечора чи екскурсія замість обіду й розбору, і їм вдавалося поєднати фізичну активність із розумовою. Інші з головою поринули в програмування, обмежуючи фізичну активність ранковою зарядкою, бо Харків для них був нецікавим, і на збори вони прибули з іншою метою.
Ми входили до числа тих, хто занурився у програмування. Збори виявилися для нас якоюсь мірою шоком: після учнівських олімпіад, на яких використовують порівняно малу кількість алгоритмів і багато задач потребують просто навичок реалізації, на студентських змаганнях потрібно використовувати значно ширший спектр знань. Ідеться і про значну кількість алгоритмів, і про “звичайні” математичні знання, частину з яких ми вже почерпнули за час навчання в Університеті. Яскравий приклад – алгоритми FFT (швидкого перетворення Фур’є), усі тонкощі яких ми вивчали від другого лекційного дня до завершення зборів. Чимало алгоритмів, які тепер використовують для розв’язування олімпіадних задач, ще 10–20 років тому не були відомі науці (роки відкриття деяких алгоритмів: Штор–Вагнера – 1994 рік, Бендера–Фарах-Колтона – 2000 рік).
Завдання змагальних турів ми розв’язували не надто добре, тому вирішили взятися до “добивання” та засвоєння матеріалу лекцій максимально серйозно, щоб реабілітуватися за основний залік і почерпнути якнайбільше нового з цих зборів. Як наслідок, усі вечори виглядали схоже – ми з United’ами до півночі чи навіть довше розв’язували задачі, кожен свої. United’и не вперше брали участь у цих зборах, тому їх не надто цікавили екскурсії – хлопці встигли оглянути Харків за попередні роки. Обидві команди ЛНУ ім. Івана Франка не покидали першої десятки заліку “добивання”, і навіть час до часу потрапляли до трійки лідерів.
“Добивали” ми в будь-який відносно вільний час. Одного разу я здогадався, де помилка, яку шукав у своєму розв’язку другий день поспіль, уже засинаючи… Однак не мав сил і бажання вставати з ліжка й виправляти помилку, і “здолав” цю задачу о сьомій ранку наступного дня.
Про рівень зборів свідчить хоча б те, хто читав нам лекції. Переглянувши список лекторів, знайдете там призерів АСМ ІСРС – людей, що досягли успіху на найвищому рівні спортивного програмування. Оргкомітет не знав, чи вдасться створити оптимальні умови для всіх лекторів. Планували, що в команд буде один вихідний день – приблизно посередині зборів. Але останньої миті погодився прочитати лекцію Петя Мітрічєв – поточний лідер рейтингу TopCoder, дворазовий золотий призер ACM ICPC, легенда спортивного програмування. Тому вихідний скасували, зате всі учасники змогли відвідати дуже цікаву лекцію найвищого рівня.
Після останнього змагального дня, коли вже були відомі списки переможців, збереглася ще одна інтрига – хто переможе в заліку “добивання”. Близько десяти команд, які серйозно поставилися до цього конкурсу, не втрачали шансів на перемогу. Ніхто з лідерів не міг упевнено оцінити свої шанси на перемогу. Оргкомітет “пошкодував” учасників і закрив “добивання” ввечері того самого дня, коли проведено останній тур, навіть не о 00:00, як це заведено, а майже на 5 годин раніше – після цього навіть “добивачі” могли зітхнути полегшено, бо й для них змагання завершилися. Хтось підбивав підсумки й аналізував свої результати, шукаючи помилки та позитивні тенденції, хтось нарешті зміг спокійно лягти спати, хтось почав складати план екскурсії на наступний день.
А на церемонії закриття всіх запросили на Літню школу, яка пройде в серпні. Хороша ідея – не чекати на таке дійство цілий рік, до Зимової школи-2012, а наблизити це задоволення. Усі охочі зможуть “прогріти” мозок перед новим навчальним роком та продемонструвати, на що вони спроможні.
Богдан Прищенко
учасник команди “LNU Juniors”