×Закрыть

Україну на Фіналі світу зі спортивного програмування будуть представляти аж 4 команди

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

Зазвичай Фінал світу відбувається у березні, цього року він також мав відбутись 3-го числа березня місяця в Шарм-ель-Шейху, але через революцію в Єгипті організатори змагання прийняли рішення про його перенесення. Відтак Фінал світу зі спортивного програмування відбудеться 30 травня в Орландо.

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

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

Також у Харківському національному університеті радіоелектроніки (ХНУРЕ) вдалось реалізувати ідею зборів подібних до Петрозаводських, які відбуваються з 2008 року. Цього року харківські збори відбувались з 11 по 21 лютого.

Завдяки підтримці компанії «SoftServe» нам вдалось прийняти участь у харківських зборах аж двома командами з Львівського національного університету імені І.Франка. Одна команда — професіонали, які готуються до Фіналу світу, інша команда — юніори, які нещодавно були школярами, а тепер з усіх сил намагаються «догнати» своїх старших колег.

<p>Бабіля Руслан<br>
тренер команди Львівського національного університету імені І.Франка</p>

Розповідь учасника про збори у Харкові

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

Після прибуття до ХНУРЕ необхідно було пройти реєстрацію. Для досвідчених спортсменів ця процедура, мабуть, є звичною. Але вперше... Якось, з допомогою волонтерів та старших колег, ми зареєструвались, сфотографувались з пам’ятником програмістові, вирушили заселятись.

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

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

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

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

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

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

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

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

Змагання непомітно завершились, після останнього туру учасники нарешті змогли розслабитись. А на церемонії закриття всіх запросили на Літню Школу, котра пройде у серпні у ... Хороша ідея — не чекати на таке дійство цілий рік, до Зимової Школи 2012, а наблизити це задоволення вдвічі. Всі бажаючі зможуть «прогріти» мозок перед новим навчальним роком та показати, на що вони спроможні.

<p style="text-align:right">Богдан Прищенко<br>учасник команди "LNU Juniors"</p>

LinkedIn

18 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Будем вболівати

Ось тут офіційний сайт змагання cm.baylor.edu
там можна буде дивитись на результати онлайн.
Також минулого року було організовано онлайн трансляцію з коментарями професіоналів, з «підглядуванням» в монітори (тобто виводили картинку з моніторів учасника) і таке інше. Надіюсь цього року також таке зроблять.

Тому вболівати буде як :).

Цікаво чи всі учасники отримають візи в Штати :)

ACM (під егідою якої відбуваються ці змагання) дуже крута організація. Вони можуть залучити до вирішення візових та інших організаційних питань дуже впливових людей. Поки, за всі роки, я не чув жодного випадку, щоб не дали якійсь команді візу (в будь яку країну, де б не відбувався Фінал).

Ну я навіть нещодавно читав на форумі ТопКодера, що команді з Ірану здається не давали віз в Єгипет. І раніше чув про випадки, правда не впевнений, що це було про фінал ACM, можливо про інші топові змагання

Я знаю випадки, що на ТопКодер не їхали через, те що їм не дали, або за пізно дали візи.

А от про АСМ не чув.

Ага :)
На Фіналі дають по 4 комплекти медалей, тобто 4 золоті, 4 срібні, 4 бронзові.

Якраз нашим всім командам вистачає «золота».

А яким макаром діляться комплекти? Там є різні вагові чи вікові категорії?

Ні, просто 12 призових місць, перші 4 — золоті медалі, наступні 4 — срібні...

Ну це в першу чергу пов’язано з тим, що дуже велика кількість команд приймає участь. У минулому році прийняло участь у цьому чемпіонаті аж 8305команд.

Мало який вид спорту може похвалитись такими цифрами.

До речі.

Вже 9 квітня в Україні починається наступний чемпіонат 2011-2012 років. Цього року трохи змінився регламент проведення чемпіонату в України, тепер університетські змагання офіційно включені в головну відбіркову сітку і можна точно відслідкувати яка кількість команд приймає участь.

Зареєструвалось в Україні 647 команд!!!

Кількість команд ще не означає сильнішу конкуренцію:)

я якраз подумав, чому developers.org.UA. а статті всі російською?

почитаю :)

а название команды топикстартера не удивляет?

Наверное потому, что авторы статей пишут по русски? Хотите украинский — пишите статьи. Английский тоже ок, бтв.

вперед, ребята!

Подписаться на комментарии