Proggy-Buggy: зачем программисты решают задачи на скорость?

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

О личном опыте

Я увлеклась спортивным программированием на первом курсе Днепропетровского Национального университета. У нас преподавал Александр Леонидович Хижа, который как раз и придумал 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 обеспечивает довольно низкий порог входа. И при этом остается интересной опытным олимпиадникам.