Proggy-Buggy: навіщо програмісти розв’язують задачі на швидкість?

21 жовтня
Proggy-Buggy: навіщо програмісти розв’язують задачі на швидкість?
24 жовтня DataArt проведе традиційну олімпіаду з програмування Proggy-Buggy. Ми поговорили з Віолетою Подволоцькою — розробником із Дніпра й автором більшості задач турніру. Трохи про Proggy-Buggy та складання завдань, а здебільшого про спортивне програмування загалом: його плюси для самих спортсменів (їх більше) та мінуси (вони теж є).

ПРО ОСОБИСТИЙ ДОСВІД

Я захопилася спортивним програмуванням на першому курсі Дніпропетровського національного університету. В нас викладав Олександр Леонідович Хижа, президент DataArt Dnipro та доцент ДНУ, який якраз і придумав Proggy-Buggy та розвиває турнір у DataArt — він проводив додаткові заняття, де ми розбирали олімпіадні задачі. Зокрема й веселі задачі з Proggy-Buggy. Ми зібрали команду та почали брати участь в олімпіадах: обласних, регіональних і всеукраїнських.

Справа в мене в принципі пішла, оскільки певний досвід я вже мала. Коли вчилась у фізмат ліцеї, регулярно брала участь в олімпіадах з математики. Про програмування лише думала — вся енергія йшла на математику. Правда, виявилось, що на студентському рівні змагання з програмування зовсім інші. Якщо школярі просто приходять і поодинці розв’язують математичні задачі чи складають програми-рішення, студенти-програмісти завжди працюють у командах. На Proggy-Buggy регламент набагато м'якший: якщо команда не зібралась, можна брати участь індивідуально. На турнірах основного стандарту ACM ICPC з цим суворо — тільки три людини за одним комп'ютером, інакше можлива дискваліфікація. Але якраз працювати над задачами спільно з командою мені сподобалося навіть більше.

Наша команда не була найсильнішою, але ми двічі виходили на національні змагання: одного разу в другій лізі їздили до Одеси, іншого — до Вінниці, вже в першій. Але, треба сказати, конкурувати з найсильнішими надзвичайно складно: зазвичай перші місця в рейтингах посідають люди, які займаються спортивним програмуванням з 7–8-го класу школи та присвячують йому дуже багато часу. Вони, на відміну від більшості однокурсників, не йдуть на другому або третьому році навчання на роботу, роблячи ставку саме на олімпіади. У цьому я могла переконатись і на турнірах KPI Open, які теж виявилися досить важкими. Але, думаю, участь у них все одно була корисною.

ПРО ПЛЮСИ ТА МІНУСИ

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

Досвід олімпіадного програмування допомагає в пошуку швидких рішень, продумуванні деталей на березі. Впевнена, що розв’язання задач робить розум більш живим, а отриманий на турнірах адреналін підтримує любов до написання коду. Нарешті, стосунки з багами в олімпіадника будуються інакше: як правило, він здатний прогнати програму в голові та побачити помилки без дебагера і налагодження. Адже на змаганнях часто доводиться дивитися код з аркуша, налагоджувати його просто нема коли та на чому — адже комп'ютер на трьох усього один і він майже завжди зайнятий.

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

ПРО СПОРТ І КАР'ЄРУ

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

Існують і компанії, які, навпаки, полюють за тими, хто домігся успіху в спортивному програмуванні. Перш за все, йдеться про FAANG (Facebook, Apple, Amazon, Netflix і Google) + Microsoft. Але й шукають вони людей рівня чемпіонів світу, тобто найсильніших олімпіадників, що посідають перші рядки в рейтингах ACM ICPC. І тут, звісно, йдеться про тих, хто виступає ще зі школи.

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

Нарешті, в тих самих компаніях FAANG практикується формат співбесід, де олімпіадники отримують серйозну перевагу. Зазвичай спілкування з ними починається з двох дистанційних зустрічей, під час яких вам можуть запропонувати розв’язати якусь задачу, почавши писати програму просто в редакторі коду. Зрештою, не знання ж фреймворків їм перевіряти — може, вони взагалі запропонують вам освоїти щось нове, виключно для внутрішнього користування. Більшість олімпіадників пишуть на Java та особливо C++, яка залишається найшвидшою за інші мови та не уповільнює розв’язання.

На співбесідах у найбільші IT-компанії навичка спортивного програмування — саме те, що треба. На третьому етапі вам можуть запропонувати приїхати в офіс, на вакансію в якому ви претендуєте, і там писати код маркером на дошці. Щоб підготуватися до цих інтерв'ю, існують курси на Coursera, сайт LeetCode та інші аналогічні проекти. Останні пропонують алгоритмічні задачі та навіть мокові інтерв'ю з іншими учасниками спільноти, які виступають як рекрутер, що проводить співбесіди. Самі задачі дуже схожі на олімпіадні: на теорію графів, на динамічне програмування, на теорію чисел, різні сортування тощо. Загалом проходити співбесіду, маючи досвід спортивних турнірів, простіше на порядок. Залишиться хіба що повторити окремі алгоритми, ну й не забувати про дисципліну.

Що стосується мене, я взагалі не думала про професію програміста, коли вступала до університету. Швидше думала про чисту математику, можливо, про роботу викладача. Але саме через олімпіади зрештою опинилась у промисловій розробці.

ПРО ЗАДАЧІ ДЛЯ PROGGY-BUGGY

Я почала допомагати з задачами для Proggy-Buggy у 2018 році. Більшу частину тоді писав мій колега Євген Радченко — сильний олімпіадник, який півтора роки тому пішов у Google. Зараз я складаю більше завдань, але творчість є колективною, що мені якраз із самого початку сподобалось. Зазвичай одна людина вигадує ідею, інші намагаються трохи ускладнити умови, а заодно якось обіграти наших героїв. Такі обговорення зазвичай виходять дуже веселими. Наприклад, берете відомий алгоритм або математичний факт, а потім створюєте для нього легенду. Минулого року наш позитивний герой Прогі здебільшого виступав у ролі Шерлока Холмса, а його антагоніст Багі — професора Моріарті. Ось, скажімо, задача “Кримінальний професор”:


Будучи за сумісництвом професором математики, геній кримінального світу Багі відбирає розумних студентів до злочинного угруповання. Цього разу він запропонував своїм студентам для заданих чисел A і K знайти результат роботи наступного алгоритму:

1. Знайти добуток K натуральних чисел, що йдуть поспіль, починаючи з числа A.
2. Поки в числі більше однієї цифри — шукати суму цифр отриманого числа.
Наприклад, A = 2, K = 3, тогда 2 * 3 * 4 = 24, 2 + 4 = 6 (тільки одна цифра). Відповідь: 6.
Спробуйте й ви написати програму, яка розв’язує задачку від професора.

Input
В єдиному рядку задано 2 натуральних числа A і K 
(10^1 <= A, K <= 10^1000), відокремлених одним пробілом.
Output
Вивести результат алгоритму.

Розбір задачі:

Число А, з якого починається добуток, взагалі не має ніякого значення. Оскільки K >= 10 > 9, то добуток 9 та більше чисел, що йдуть поспіль, ділиться на 9, оскільки хоча б одне з цих чисел є кратним 9. Значить сума цифр P1 числа P також ділиться на 9. А значить сума цифр P2 числа P1 також ділиться на 9. І так далі... Очевидно, що P > P1 > P2 > P3 > ... А значить починаючи з якогось Pk залишиться число, що складається з однієї цифри та ділиться на 9. Таким чином для обмежень у задачі відповіддю завжди буде 9.


Мені здається, що наші задачі є веселішими за традиційні. Та й триває турнір усього 42 хвилини, які знайти простіше, ніж цілий день. При цьому, думаю, той, хто спробував спортивне програмування, без нього страждає — іноді починаєш підозрювати, що вже трохи отупів. Напевно, тому й проводиться стільки онлайн-конкурсів: досить згадати Google Code Jam і Facebook Hacker Cup. Але повторюся, в нас простіше й веселіше.

У Proggy-Buggy дві категорії: досвідчені спортсмени — ті, хто брав участь в олімпіадах ACM ICPC, та новачки. Команди бувають найрізноманітнішими, мені здається, до нас приходили навіть учасники чемпіонату світу. Цікаво, що на Proggy-Buggy є й зовсім молоді програмісти, і люди старшого віку, для яких турнір, можливо, є також приводом зайвий раз поспілкуватись. Я знаю, що один наш колега — Senior PM із Лондона — бере участь у Proggy-Buggy вже кілька років. Все ж щось важливе ми даємо людям, якщо вони залишаються з нами. Спортивне програмування підходить не всім, але олімпіада Proggy-Buggy забезпечує досить низький поріг входу. І при цьому залишається цікавою досвідченим олімпіадникам.

Proggy-Buggy 2020 відбудеться вже цієї суботи. Дізнатися більше та зареєструватися (до вечора 22 жовтня) можна за цим посиланням.

  • Україна, Дніпро; Україна, Київ; Україна, Львів; Україна, Одеса; Україна, Харків; Україна, Херсон
    3 грудня