Як стати першим в спортивному програмуванні: Університет ІТМО ділиться досвідом. Частина 1

У цьому матеріалі ми розповімо про новий курс, який був запущений Університетом ІТМО на платформі edX в цьому році. Під катом – розповідь про проект «How to Win Coding Competitions: Secrets of Champions» і велике інтерв'ю з авторами і інструкторами курсу, в якому вони міркують про те, що повинен знати і вміти майбутній переможець, і діляться своїм досвідом і спогадами від участі в олімпіадах з програмування.


Sebastiaan ter Burg / Flickr / CC

Про курс
Курс «Як перемагати в змаганнях з програмування: секрети чемпіонів» стартував у жовтні цього року. Авторами та інструкторами курсу стали чемпіони студентських олімпіад, в різні роки захищали честь Університету ІТМО: Максим Буздалов, доцент кафедри комп'ютерних технологій Університету ІТМО і чемпіон ACM ICPC 2009 року, Павло Кротков, випускник факультету інформаційних технологій і програмування Університету ІТМО, учасник і організатор багатьох контестів з програмування в Росії і за кордоном, включаючи ACM ICPC NEERC (зараз Павло працює в Facebook) і Дарья Яковлєва старший лаборант кафедри інформаційних систем Університету ІТМО, в цьому році увійшла в десятку на міжнародному змаганні з програмування Google Code Jam for Women.

Курс розрахований на 5 тижнів і спрямований на вивчення особливостей і підходів, що використовуються у спортивному програмуванні. Учасники дізнаються, як проходять змагання, розбирають найбільш популярні підходи до вирішення задач та приклади їх використання тренуються розв'язувати олімпіадні завдання в умовах, наближених до реальних (фінальний іспит проходить у форматі цього міжнародного змагання з програмування).

Автори курсу не просто «натаскують» студентів на олімпіадні завдання, але і розповідають про те, як працювати в умовах жорстких дедлайнів і знаходити незвичайні і ефективні рішення.

Ми дізналися у Максима, Павла і Дар'ї, якими знаннями повинен володіти майбутній переможець олімпіад з програмування, наскільки важливі для перемоги «фішки» та лайфхаки і які помилки найчастіше допускають новачки в спортивному програмуванні.

Програма-мінімум: що необхідно знати для перемоги в змаганні
Павло Кротков називає основні навички, необхідні для перемоги в олімпіадах: знання математики, алгоритмів, мови програмування. Без цих знань досягти успіху, самою собою, неможливо.

Друга група важливих навичок: правильна тактика, знання «фішок». У командних змаганнях це — вміння оптимально використовувати час за комп'ютером, поділ праці, вміння налагоджувати свої програми і програми партнерів по команді і шукати в них помилки. В особистих змаганнях до таких навичок належать, знову ж таки, вміння налагоджувати/тестувати свої програми, швидко перевіряти ті чи інші гіпотези.

Максим Буздалов доповнює цей перелік і виділяє відразу сім навичок, необхідних для успішної участі в олімпіадах з програмування:

  1. Здатність придумувати рішення завдань. Сюди відносяться здатності генерувати і перевіряти ідеї, зводити одні завдання до інших тощо.
  2. Ерудиція в області алгоритмів і структур даних, стандартних і не дуже. Це знання про те, які алгоритми/структури взагалі існують, які завдання вони вирішують, які властивості вони вимагають від розв'язуваної задачі, яка асимптотична складність цих алгоритмів або операцій з цими структурами даних.
  3. Здатність ефективно реалізовувати алгоритми і структури даних на практиці. При цьому під словом «ефективно» розуміються дві взаємопов'язані речі — «ефективність» з точки зору функціонування алгоритмів/структур і «ефективність» з точки зору часу їх написання на змаганні.
  4. Знання мови програмування і моделі складності операцій цієї мови. Так, деякі речі для необхідної ефективності потрібно писати по-різному (з використанням різних підходів до зберігання даних, структурування коду на C, С++, Java і Python.
  5. Знання різних «хаків», здатних прискорити і без того грамотно написаний код.
  6. Вміння шукати помилки в коді і налагоджувати код.
  7. Вміння ефективно розподіляти ресурси — особисті ресурси, ресурси команди обчислювальні ресурси для досягнення максимальних результатів.
Максим підкреслює, що різні навички і вимагають різної підготовки. Так, на його думку, читання літератури допоможе краще розбиратися в алгоритмах і структурах даних – але не більше того.

Придумувати вирішення завдань навчать заняття математикою. «Промислове» програмування (тобто те, чим зазвичай програмісти займаються в рамках виконання робочих завдань для бізнесу) забезпечить опрацювання навичок №4, №5 та №6. А ось здатність ефективно реалізовувати алгоритми і структури даних на практиці і вміння ефективно розподіляти ресурси – це, на думку Максима, типово спортивні навички – ті, які без практики участі у змаганнях розвинути вкрай складно.

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

– Максим Буздалов
Ще раз про «фішки»
Ми запитали у авторів курсу, може новачок, розбирається в математиці і програмуванні, але не знайомий з «фішками», лайфхаками та іншими таємними знаннями, виграти змагання. Переможці олімпіад погодилися, що «фішки» — це ще не все: без фундаментальних знань і працьовитості учаснику олімпіади буде обійтися набагато складніше:

Я б сказав, що досягти успіху в змаганнях до певного рівня, маючи тільки знання з першої категорії [знання математики, алгоритмів, мови програмування], можна. Тим не менш, знання з другої категорії [розуміння правильної тактики, навички грамотного розподілу ресурсів] сильно спрощують життя і працюють як каталізатор. Як і в будь-якому спорті: є фізичні навички, а є знання техніки, психологія, і так далі. Досягти успіху лише за рахунок першого можна, але друге буде працювати каталізатором

– Павло Кротков
Як мені здається, ті, хто успішні в олімпіадах (займають призові місця на провідних змаганнях миру), можуть бути в міру неосвіченими в пункті №5 [зі списку вище] («хакі»), а також — за умови геніальності в інших областях — можуть не надавати значення пункту №7 (робота з ресурсами)

– Максим Буздалов
Дарина Яковлєва зазначила, що в умовах олімпіади важливіше знання «фішок» може виявитися творчий підхід, тому талановиті початківці можуть розраховувати на гідний результат:

Звичайно, важливо знати різні методи вирішення завдань, але потрібно зауважити, що журі олімпіад намагається скласти завдання таким чином, щоб учасники в першу чергу придумали ідею, рішення самостійно. Однак складні завдання, зрозуміло, вимагають додаткових знань. Тому, я думаю, виграти буде складно, а потрапити в топ-10 реально

– Дарина Яковлєва
Про роботу в команді
Базові вміння та навички в особистому та командному програмуванні відрізняються — щоправда, незначно. Дарина уточнює:

В командних змаганнях у команди є тільки один комп'ютер. Тому протягом олімпіади тільки одна людина пише розв'язок задачі на комп'ютері, інші хлопці вирішують інші завдання на листочках.Зазвичай в команді є: математик, програміст і любитель вирішувати нестандартні завдання

– Дарина Яковлєва
Це означає, що учасник командних змагань може зробити «наголос» на одній або декількох областях – в цьому випадку його слабкі сторони компенсують колеги. Максим у зв'язку з цим згадує турнір ACM ICPC 2009 року:

Так, наприклад, в нашій команді (ми були чемпіонами світу з програмування 2009 року) Женя Капун був неперевершеним винахідником рішень, Слава Исенбаев був відмінним «універсальним бійцем», а завдання, які потребують великих обсягів акуратного коду (наприклад, завдання на обчислювальну геометрію), найкраще писав я

– Максим Буздалов
Максим і Павло відзначають: розподіл ролей у команді часто відбувається природним шляхом протягом першого десятка тренувань. Буває, що у партнерів по команді є злегка розрізняються інтереси, і в результаті різні учасники потроху спеціалізуються на різних напрямках (як уточнює Максим, нелегких — наприклад, обчислювальної геометрії, завдання на потоки, «хитрих» структурах даних, суффиксных деревах або суффиксных автоматах і так далі). Хтось швидше реалізовує стандартний алгоритм, або краще орієнтується в тому чи іншому розділі математики — все це впливає на неформальне розподіл ролей в команді.

Бувають команди з яскраво вираженим «математика» і яскраво вираженим «кодером». Абсолютно ізолювати ці навички, природно, не виходить, так як кодер повинен розуміти математика і навпаки. Крім того, якщо вони також беруть участь в особистих змаганнях, нерівність з часом може зменшуватися, так як учасники вчаться один у одного.

У будь-якому випадку, якщо у вас в команді є «математик», або «кодер», або «тестер», або фахівець з суффиксным автоматів — це не означає, що вам не треба розвивати відповідні навички. Як раз навпаки — вам є, у кого вчитися, і цим треба користуватися

– Максим Буздалов
Буває, що союзники виявляються приблизно рівні по силі і по набору навичок — в результаті тактика роботи в команді зводиться до того, що завдання пише той, хто перший її вирішив. Однак, як зазначає Павло, розподіл ролей не завжди пов'язане зі спеціалізацією на тій чи іншій області знань: у більшості команд є також людина, яка може прийняти рішення в складній ситуації — його можна назвати лідером або капітаном.

Підводні камені: на чому провалюються недосвідчені учасники
Як відзначають автори курсу, основні проблеми новачків пов'язані в першу чергу з переоцінкою своїх сил і можливостей. Максим Буздалов називає справжнім бичем недосвідчених учасників їх дивовижну впевненість у тому, що код, який вони написали, працює.

Причому вони практично не розрізняють [різницю між] «працює» і «працює на прикладі з умови». Їм не приходить думка перевірити код ще раз, придумати контрприклад, спробувати, нарешті, довести коректність рішення. Зокрема, тому вердикт виду «Невірна відповідь, тест 2» залишає таких учасників крайньої розгубленості, а кілька таких вердиктів поспіль — у стані грунтовної озлобленості.

– Максим Буздалов
В якості прикладу Максим призводить одну із задач з курсу «Як перемагати в змаганнях з програмування: секрети чемпіонів». Дана матриця з чисел розміру 3x3, необхідно вибрати з цієї матриці три числа так, щоб ні в одному стовпці і ні в одному рядку не було б обрано більше одного числа, а корінь з суми квадратів чисел був максимальний.

Правильне рішення цього завдання — принаймні, одне з них — очевидно: перебираємо всі можливі трійки номерів стовпців <a, b, c>, а для кожної такої трійки перевіряємо вибір, у якому в першому рядку вибирається стовпець a, у другій — стовпець b, а в третій — стовпець c.

Проте багато учасників курсу надсилали таке рішення: спочатку виберемо максимальне з чисел матриці, потім викреслимо відповідний рядок і стовпець, потім знову виберемо максимум, і так далі. Це призводило до хибної відповіді на шостому тесті. Це рішення дуже легко «вбити»: достатньо розглянути, що відбудеться на такій матриці:

9 8 1
8 1 1
1 1 1

Правильне рішення вибере дві вісімки і решту одиницю, при цьому сума квадратів буде дорівнює 129. «Жадібне» рішення вибере дев'ятку, потім йому не залишається нічого, крім одиниць, і сума квадратів складе 83. Витяг кореня, звичайно ж, не змінить того, що перша відповідь — більше, а отже, краще.

Отримавши подібний приклад, багато учасників почали писати всілякі розбори випадків, отримуючи невірні відповіді на тому ж тесті або на інших тестах, при цьому упускаючи головне — отримавши нескладний контрприклад для логіки роботи основної частини свого рішення, слід зупинитися і подумати. Замість затикання дірок, розміщення підпорок і сколочування милиць, добре б хоча б обгрунтувати, чому рішення взагалі працює. А в ідеалі — математично строго довести

– Максим Буздалов
Ще одна поширена помилка, яку зазначає Дарина, — переповнення даних типу int:

Вона [помилка] трапляється в тому випадку, коли ви намагаєтеся «покласти» в змінну значення більше допустимого. Потрібно бути уважним і оцінювати порядок значень при рішенні задачі, і все буде добре

– Дарина Яковлєва
Павло Кротков відзначає ще одну важливу особливість досвідчених учасників олімпіад — стресостійкість. Її новачкам також не вистачає — саме тому невірне рішення може легко викликати подив і паніку і призведе до втрати дорогоцінного часу.

Про вміння подолати стрес мова піде і у другій частині нашої розмови: автори та інструктори курсу розкажуть, яку роль у процесі підготовки до змагання відіграє психологія і правильний настрій, поділяться своїми лайфхаками і маленькими хитрощами, а також пояснять, кому (крім майбутніх призерів олімпіад) може бути цікавий курс «How to Win Coding Competitions: Secrets of Champions» Університету ІТМО.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.