В этом материале мы расскажем о новом курсе, который был запущен Университетом ИТМО на платформе 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» Университета ИТМО.