ACM Контестер

За результатами півфіналу світу зі спортивного програмування, який відбувся у Бухаресті, команда Львівського національного університету імені Івана Франка «LNU United» пройшла на Фінал світу ACM ICPC, який відбудеться в Орландо (США, штат Флорида) 30 травня 2011 року. На Фінал світу запрошені 105 найкращих команд з шести континентів, які вибороли цю можливість серед 8305 команд з 2070 університетів, які представляли 88 країн. 2011 рік для України рекордний, оскільки нашу країну представлятимуть аж 4 команди: Київського національного університету імені Т.Шевченка, Донецького національного університету, Таврійського національного університету імені В.Вернадського і Львівського національного університету імені І.Франка (ЛНУ). Склад команди ЛНУ: Євчинець Ігор, Кушнір Павло, Воєца Олександр, тренери Бабіля Руслан та Білецький Василь.

У звичних для нас видах спорту (футбол, баскетбол, …) перед великими стартами відбуваються різні тренувальні збори; так і у спортивному програмуванні також є збори різних рівнів. Найпрестижнішими є збори у Петрозаводську (Росія), які відбуваються вже десятий рік поспіль. Цього року у зборах приймали участь 20 майбутніх фіналістів світу, в тому числі всі 5 переможців європейських півфіналів, були представники 7 країн, з України було 5 команд. Це можна назвати справжньою генеральною репетицією перед Фіналом світу. Оскільки наша команда запрошена на Фінал світу, то організатори зборів у Петрозаводську запросили нас прийняти участь у цих тренуваннях; звісно ж, ми не могли пропустити такої нагоди, і приїхали на збори оптимальним складом – 3 учасники (Євчинець Ігор, Кушнір Павло, Воєца Олександр) та 1 тренер (Бабіля Руслан). Збори тривали з 28 січня по 7 лютого, складались із 9 змагальних днів і 2 днів відпочинку. Кожен день відбувався за наступним графіком: спочатку змагання, які тривали класично - 5 годин, потім лекції від найкращих спортивних програмістів світу, потім можна було весь вільний час дорозв’язувати не розв’язані під час змагання завдання, або трохи відпочити і розім’ятись у спортзалі. Оскільки там зібрались всі найсильніші команди, то всі розуміли для чого вони так далеко їхали і намагались використати час максимально ефективно, тому весь час всі учасники працювали над своїми розв’язками. На відміну від футболіста, котрий може прийти додому і, лежачи на дивані, просто відпочивати, спортивні програмісти не можуть так відпочивати, оскільки навіть під час перебування у їдальні голова думає над задачами, декому правильні розв’язки навіть сняться. Класична ситуація: у вихідний день нам організували прогулянку на бігових лижах, то деколи було чути у лісі, як котрийсь лижник кричав своєму товаришу: «Я придумав як зробити динаміку не за куб, а за квадрат!». Ці всі «муки» не є даремними, оскільки через деякий час на Фіналі світу між цими ж командами буде розігруватись звання абсолютного чемпіона світу.

Ці тренувальні змагання для нашої команди виявились надзвичайно корисними, рівень зріс дуже відчутно. Також ці збори дали змогу оцінити, між ким будуть розігруватись медалі на фіналі світу - як виявилось, конкуренція буде дуже високою, бо рівень команд дуже сильний і, що найприємніше, команда ЛНУ також має можливість вести боротьбу за найвищі нагороди. Найгірший результат нашої команди на цих тренувальних зборах – це 36 місце 9-го змагального дня, а найкращий результат – третє місце за підсумками сьомого змагального дня. На ці збори ми в першу чергу їхали з бажанням порозв’язувати завдання високої складності, оскільки російська школа спортивного програмування славиться складними завданнями, які частіше навіть складніші, ніж на фіналах світу. Авторами змагань всього було запропоновано 95 завдань, команда «LNU United» успішно розв’язала 81 завдання, більше розв’язали тільки 5 команд.

Спортивне програмування останнім часом дуже стрімко розвивається на пострадянському просторі. Провідну роль відіграє Росія, оскільки команди з цієї країни вже 6 разів ставали чемпіонами світу. Провідними центрами звичайно є університети Москви та Санкт-Петербургу, але багато університетів з інших міст також дуже сильно виступають і ведуть боротьбу за найвищі місця. Такі високі результати російських команд є результатом аналогічних до Петрозаводських тренувальних зборів, які відбуваються у Росії в багатьох регіонах майже цілий рік. Білорусь на найвищому рівні переважно представляє один університет – Білоруський державний університет, команда з Грузії також досягала високих результатів. До недавнього часу Україну на Фіналі світу представляли тільки 2 університети зі столиці – Київський національний університет імені Т.Шевченка (бронзова медаль на Фіналі світу 2003 року) та Національний технічний університет України «КПІ», до них приєднались Вінницький національний технічний університету та Львівський національний університет імені І.Франка. Команда нашого університету у складі Білецького Василя, Коркуни Остапа та Бабілі Руслана в 2008 році вперше для України на Фіналі світу зі спортивного програмування завоювала золоту медаль. Ці всі результати досягаються завдяки створенню осередків навколо ентузіастів, які займаються розвитком спортивного програмування у своїх університетах.

Завдяки підтримці компанії «SoftServe» нам вдалось прийняти участь у харківських зборах аж двома командами з факультету прикладної математики та інформатики Львівського національного університету імені І.Франка. Одна команда – професіонали «LNU United», які готуються до Фіналу світу, інша команда – першокурсники «LNU Juniors» (склад Глова Павло, Миляник Іван, Прищенко Богдан, тренер Бабіля Руслан), які нещодавно були школярами, а тепер з усіх сил намагаються «догнати» своїх старших колег. Також були представники факультету електроніки – команда «Karpaty» (у складі Кость Ярослав, Демчук Іван, Козак Михайло, тренер Хвищун Іван Олександрович).

Одного січневого вечора я дізнався, що в лютому відправлюсь на тренувальні збори в Харкові. Ті самі збори, про які розповідали мені, ще коли я був школярем. У зборах брала участь також і команда «LNU United», котра активно готувалась до фіналу ACM ICPC – адже за підсумками півфіналу у Бухаресті хлопці увійшли до ста п’яти кращих команд світу та вибороли право захищати честь університету у цій битві найсильніших. Всі можливі проблеми з нашого шляху усували – щоб ми не відволікались від основної цілі подорожі. Команду було забезпечено фінансуванням, також у нас не було потреби вирішувати проблему з місцем проживання.

Сніданок - як і личить серйозним міжнародним зборам, їдальня залишала лише найкращі враження; після смачного сніданку - лекція. Після лекції – тренувальні змагання від лектора поточного дня. Після завершення туру - обід, опісля – розбір задач, спочатку – з вищої ліги, далі – з юніорської. Після розбору – «добивання». «Добивання» на схожих зборах – це окремий залік; процес добивання полягає в тому, що учасники розв’язують задачі, котрі не змогли розв’язати під час основних турів.

Далі у розкладі – вечеря. Після вечері – підведення підсумків дня. Деякі команди не відвідували розбір; у них на це були різні причини: хтось розв’язав всі задачі під час основного туру, хтось вважав за краще самостійно дійти до правильного алгоритму. Так от, підведення підсумків оминала ще більша кількість команд. Дехто прагнув за цей час відпочити, дехто не хотів відволікатись від добивання (дехто навіть вечеряв, не відриваючись від добивання).

Під час онлайн-листування з одногрупниками я зіткнувся з цікавим баченням зборів: «Класно вам там, майже нічого не робите, одну лекцію посидіти, написати декілька програмок, а далі – халява! А у нас тут пари, «грузять», складно…». Хочеться розвіяти цей міф. Звісно, коли у вас є можливість одинадцять днів займатись справою, яка вам подобається, і при цьому не треба ні на що відволікатись – це приємне проведення часу. Але збори з програмування, як і будь-які інші тренувальні спортивні збори – це значне навантаження, хоч і приємне. Не лише через любов до програмування, а й через спортивний азарт та прагнення самовдосконалення багато учасників займались складною розумовою працею 15-17 годин на добу.

Збори у Харкові не були жодною з крайностей: йдеться не про дві сотні фанатиків, котрі по 16 годин на день проводили на лекціях або за розв’язуванням задач, але також і не про зібрання туристів, що цілими днями вивчали Харків та бавились у комп’ютерні ігри. Кожна із команд сама для себе обирала найкращий варіант. Декому сподобались організовані спільними зусиллями товариські мініфутбольні матчі о дев’ятій вечора чи екскурсію замість обіду і розбору, і їм вдавалось поєднати цю фізичну активність з активністю розумовою. Інші з головою поринули у програмування, обмежуючи фізичну активність ранковою зарядкою, бо Харків для них був нецікавим, та й на збори вони прибули з іншою метою.

Ми входили до числа останніх. Збори виявились для нас певним шоком – після учнівських олімпіад, на котрих використовується порівняно мала кількість алгоритмів та багато задач вимагають просто навиків реалізації, на студентських змаганнях потрібно використовувати значно ширший спектр знань. Йдеться і про велику кількість алгоритмів, і про «звичайні» математичні знання, частину з яких ми вже почерпнули за час навчання в університеті. Яскравий приклад – алгоритми FFT (швидкого перетворення Фур’є), з усіма тонкощами котрих ми розбирались від другого лекційного дня (який саме цьому і був присвячений) до завершення зборів. Чимало з алгоритмів, котрі вже зараз використовуються для розв’язування олімпіадних задач, ще 10-20 років тому не були відомі науці (роки відкриття деяких алгоритмів: Штор – Вагнера – 1994 рік, Бендера – Фарах-Колтона - 2000 рік).

Приклад задачі зі змагань: вам відома кількість пального, яку необхідно витратити на переліт між кожною парою міст (при цьому для протилежних напрямів перельоту між однією парою міст ці значення можуть відрізнятись – тобто задано орієнтований граф), в кожному із міст можна дозаправлятись. Завдання – визначити, який мінімальний можливий об’єм бака літака, при якому він може потрапити з будь-якого міста країни у будь-яке інше (можливо, з дозаправками).

Зрозуміло, що відповідь не перевищує максимальне зі значень «вартості» перельоту для всіх пар міст. А як визначити мінімальне значення? Є декілька способів це зробити. Перше спостереження – якщо якогось об’єму достатньо, то достатньо і більшого об’єму. Тому можна скористатись бінарним пошуком. А як провірити, чи підходить задана кількість пального? Побудуємо граф, в якому між парою міст є дуга, якщо між ними можливий прямий переліт, і відсутня дуга, якщо переліт неможливий. Ми звели задачу до повірки існування шляхів між всіма парами вершин у заданому орієнтованому графі. Це можна зробити алгоритмом Флойда або швидше – конденсацією графа чи поєднанням обходу в ширину для початкового та інверсованого графа.

Як наслідок, всі вечори виглядали схоже – ми з United’ами до півночі чи навіть довше сиділи над задачами, кожен над своїми, і змагались не лише із набором завдань, а й між собою. United’и не вперше брали участь у цих зборах, тому їх не надто цікавили екскурсії – хлопці встигли оглянути Харків у попередні роки. Обидві команди нашого факультету не покидали першу десятку заліку добивання, і навіть час від часу потрапляли у трійку лідерів. За підсумками добивання дві команди ЛНУ потрапили у першу п'ятірку.

Згадалась одна цікава простенька задача, котра колись була доволі складною: візьмемо базовий рядок «01», і будемо генерувати з неї рядок нескінченної довжини, дописуючи в кінець його ж, але із заміною 0 на 1 і навпаки (з «01» одержимо «0110», далі – «01101001»). Необхідно визначити, який символ буде на позиції із заданим номером (і номер цей може бути до мільярда). Перша думка – будувати весь рядок до заданого номера. Такий розв’язок вимагає забагато часу та пам’яті. Потрібно використати той факт, що нас цікавить лише один символ, а не вся послідовність. Визначимо для цього символу «батьківський», з якого він одержаний – де стояв символ, котрий ми скопіювали на задану позицію та змінили. Далі визначимо «батьківський» для «батьківського» і т.д. Оскільки номери символів будуть весь час зменшуватись приблизно вдвічі, то ми колись дійдемо до котрогось з двох символів початкового рядка. Його ми знаємо, залишились лише за кількістю кроків визначити, в що саме даний символ перетворюється на заданій нам позиції.

Дні минали, учасники щодня слухали лекцію та писали черговий тур змагання. Окрім кількох тематичних тренувань, учасники зіткнулись і з кількома наборами задач, наближеними до реальних змагань. Такі тренування є корисними, оскільки це моделювання реальних змагань – на звичайних змаганнях навряд чи з 10 задач 8-9 будуть на геометрію, перетворення Фур’є або потоки, варто не лише знати певні алгоритми, але й уміти розпізнати їх.

Про рівень зборів свідчить хоча б те, хто читав нам лекції. Переглянувши список лекторів, ви знайдете там призерів АСМ ІСРС – людей, що досягли успіху на найвищому рівні спортивного програмування. Оргкомітет до останнього не знав, чи вдасться створити оптимальні умови для всіх лекторів. Планувалось, що в команд буде один вихідний день – приблизно посередині зборів. Але в останню мить погодився прочитати лекцію Петя Мітрічев – поточний лідер рейтингу TopCoder, дворазовий золотий призер ACM ICPC, легенда спортивного програмування. Як наслідок, вихідний відмінили, зате всі учасники змогли відвідати дуже цікаву лекцію найвищого рівня.

Також Петя запропонував задачу для нового змагання – на найкоротший код. Такі змагання є досить популярними, але у Харкові раніше не проводились. Суть змагання в тому, щоб не лише розв’язати задачу, а й записати розв’язок на одній із дозволених мов програмування, використовуючи мінімальну кількість символів. Зазвичай, задача або має красивий короткий розв’язок, або ж вимагає дуже хорошої оптимізації коду.

Після останнього змагального дня, коли вже відомі були списки переможців, ще залишалась одна інтрига – хто переможе у заліку «добивання». Близько десятка команд, які серйозно взялись за цей конкурс, до останнього не втрачали шансів на перемогу. Ніхто з лідерів не міг впевнено оцінити свої шанси на перемогу, адже будь-хто міг скористатись заготовками «з шухляди». Йдеться про доволі цікаву тактику, яку не надто поважають – на протязі всього «добивання» писати розв’язки, але не здавати їх, а у останні декілька годин здати одразу ті кілька десятків задач, котрі вдалось зробити раніше, і піднятись з «хвоста» таблиці в групу лідерів.

Оргкомітет «пожалів» учасників та закрив добивання ввечері того ж дня, коли було проведено останній тур, навіть не о 00.00, як це прийнято, а майже на 5 годин раніше – після цього навіть «добивачі» могли зітхнути з полегшенням, бо і для них змагання завершились. Хтось підводив підсумки і аналізував свої результати, шукаючи помилки та позитивні тенденції, хтось нарешті зміг спокійно лягти спати, хтось почав складати план екскурсії на наступний день.