Как стать первым в спортивном программировании: Университет ИТМО делится опытом. Часть 1
Sebastiaan ter Burg / Flickr / CC
О курсе
Курс «Как побеждать в соревнованиях по программированию: секреты чемпионов» стартовал в октябре этого года. Авторами и инструкторами курса стали чемпионы студенческих олимпиад, в разные годы защищавшие честь Университета ИТМО: Максим Буздалов, доцент кафедры компьютерных технологий Университета ИТМО и чемпион ACM ICPC 2009 года, Павел Кротков, выпускник факультета информационных технологий и программирования Университета ИТМО, участник и организатор множества контестов по программированию в России и за рубежом, включая ACM ICPC NEERC (сейчас Павел работает в Facebook) и Дарья Яковлева, старший лаборант кафедры информационных систем Университета ИТМО, в этом году вошедшая в десятку на международном соревновании по программированию Google Code Jam for Women.
Курс рассчитан на 5 недель и направлен на изучение особенностей и подходов, использующихся в спортивном программировании. Участники узнают, как проходят соревнования, разбирают наиболее популярные подходы к решению задач и примеры их использования, тренируются решать олимпиадные задания в условиях, приближенных к реальным (финальный экзамен проходит в формате настоящего международного соревнования по программированию).
Авторы курса не просто «натаскивают» студентов на олимпиадные задачи, но и рассказывают о том, как работать в условиях жестких дедлайнов и находить необычные и эффективные решения.
Мы узнали у Максима, Павла и Дарьи, какими знаниями должен обладать будущий победитель олимпиад по программированию, насколько важны для победы «фишки» и лайфхаки и какие ошибки чаще всего допускают новички в спортивном программировании.
Программа-минимум: что необходимо знать для победы в соревновании
Павел Кротков называет основные навыки, необходимые для победы в олимпиадах: знание математики, алгоритмов, языка программирования. Без этих знаний преуспеть, самой собой, невозможно.
Вторая группа важных навыков: правильная тактика, знание «фишек». В командных соревнованиях это — умение оптимально использовать время за компьютером, разделение труда, умение отлаживать свои программы и программы сокомандников и искать в них ошибки. В личных соревнованиях к таким навыкам относятся, опять же, умение отлаживать/тестировать свои программы, быстро проверять те или иные гипотезы.
Максим Буздалов дополняет этот перечень и выделяет сразу семь навыков, необходимых для успешного участия в олимпиадах по программированию:
- Способность придумывать решения задач. Сюда относятся способности генерировать и проверять идеи, сводить одни задачи к другим и тому подобное.
- Эрудиция в области алгоритмов и структур данных, стандартных и не очень. Это знание о том, какие алгоритмы/структуры вообще существуют, какие задачи они решают, какие свойства они требуют от решаемой задачи, какова асимптотическая сложность этих алгоритмов или операций с этими структурами данных.
- Способность эффективно реализовывать алгоритмы и структуры данных на практике. При этом под словом «эффективно» понимаются две взаимосвязанные вещи — «эффективность» с точки зрения функционирования алгоритмов/структур и «эффективность» с точки зрения времени их написания на соревновании.
- Знание языка программирования и модели сложности операций этого языка. Так, некоторые вещи для требуемой эффективности нужно писать по-разному (с использованием разных подходов к хранению данных, структурированию кода) на C, С++, Java и Python.
- Знание различных «хаков», способных ускорить и без того грамотно написанный код.
- Умение искать ошибки в коде и отлаживать код.
- Умение эффективно распределять ресурсы — личные ресурсы, ресурсы команды вычислительные ресурсы — для достижения максимальных результатов.
Максим подчеркивает, что разные навыки требуют и различной подготовки. Так, по его мнению, чтение литературы поможет лучше разбираться в алгоритмах и структурах данных –, но не более того.
Придумывать решения задач научат занятия математикой. «Промышленное» программирование (то есть то, чем обычно программисты занимаются в рамках выполнения рабочих задач для бизнеса) обеспечит проработку навыков №4, №5 и №6. А вот способность эффективно реализовывать алгоритмы и структуры данных на практике и умение эффективно распределять ресурсы — это, по мнению Максима, типично «спортивные» навыки — те, которые без практики участия в соревнованиях развить крайне сложно.
Практически все эти пункты требуют постоянного развития и постоянной работы над собой. Например, если вы новичок в реализации алгоритмов, но хорошо их придумываете, вы можете решить (на бумаге) все задачи, но не решить (на компьютере) практически ни одной— Максим Буздалов
Еще раз про «фишки»
Мы спросили у авторов курса, может ли новичок, разбирающийся в математике и программировании, но не знакомый с «фишками», лайфхаками и другими тайными знаниями, выиграть соревнование. Победители олимпиад согласились, что «фишки» — это еще не все: без фундаментальных знаний и трудолюбия участнику олимпиады будет обойтись гораздо сложнее:
Я бы сказал, что преуспеть в соревнованиях до определённого уровня, имея только знания из первой категории [знание математики, алгоритмов, языка программирования], можно. Тем не менее, знания из второй категории [понимание правильной тактики, навыки грамотного распределения ресурсов] сильно упрощают жизнь и работают как катализатор. Как и в любом спорте: есть физические навыки, а есть знание техники, психология, и так далее. Преуспеть только за счёт первого можно, но второе будет работать катализатором— Павел Кротков
Как мне кажется, те, кто успешны в олимпиадах (занимают призовые места на ведущих соревнованиях мира), могут быть в меру невежественными в пункте №5 [из списка выше] («хаки»), а также — при условии гениальности в остальных областях — могут не придавать значения пункту №7 (работа с ресурсами)— Максим Буздалов
Дарья Яковлева отметила, что в условиях олимпиады важнее знания «фишек» может оказаться творческий подход, поэтому талантливые новички могут рассчитывать на достойный результат:
Конечно, важно знать различные методы решения задач, но нужно заметить, что жюри олимпиад старается составить задачи таким образом, чтобы участники в первую очередь придумали идею, решение самостоятельно. Однако сложные задачи, разумеется, требуют дополнительных знаний. Поэтому, я думаю, выиграть будет сложно, а попасть в топ-10 реально— Дарья Яковлева
Про работу в команде
Базовые умения и навыки в одиночном и командном программировании отличаются — правда, незначительно. Дарья уточняет:
В командных соревнованиях у команды есть только один компьютер. Поэтому в течение олимпиады только один человек пишет решение задачи на компьютере, остальные ребята решают другие задачи на листочках.Обычно в команде есть: математик, программист и любитель решать нестандартные задачи— Дарья Яковлева
Это означает, что участник командных соревнований может сделать «упор» на одной или нескольких областях — в этом случае его слабые стороны компенсируют коллеги. Максим в этой связи вспоминает турнир ACM ICPC 2009 года:
Так, например, в нашей команде (мы были чемпионами мира по программированию 2009 года) Женя Капун был непревзойденным изобретателем решений, Слава Исенбаев был отличным «универсальным бойцом», а задачи, требующие больших объемов аккуратного кода (например, задачи на вычислительную геометрию), лучше всех писал я— Максим Буздалов
Максим и Павел отмечают: разделение ролей в команде часто происходит естественным путем в течение первого десятка тренировок. Бывает, что у сокомандников есть слегка различающиеся интересы, и в результате разные участники понемногу специализируются на разных направлениях (как уточняет Максим, нелегких — например, на вычислительной геометрии, задачах на потоки, «хитрых» структурах данных, суффиксных деревьях или суффиксных автоматах и так далее). Кто-то быстрее реализовывает стандартный алгоритм, или лучше ориентируется в том или ином разделе математики — все это влияет на неформальное распределение ролей в команде.
Бывают команды с ярко выраженным «математиком» и ярко выраженным «кодером». Абсолютно изолировать эти навыки, естественно, не получается, так как кодер должен понимать математика и наоборот. Кроме того, если они также участвуют и в личных соревнованиях, неравенство со временем может уменьшаться, так как участники учатся друг у друга.В любом случае, если у вас в команде есть «математик», или «кодер», или «тестер», или специалист по суффиксным автоматам — это не означает, что вам не надо развивать соответствующие навыки. Как раз наоборот — вам есть, у кого учиться, и этим надо пользоваться
— Максим Буздалов
Бывает, что сокомандники оказываются примерно равны по силе и по набору навыков — в результате тактика работы в команде сводится к тому, что задачу пишет тот, кто первый ее решил. Однако, как отмечает Павел, распределение ролей не всегда связано со специализацией на той или иной области знаний: в большинстве команд есть также человек, который может принять решение в сложной ситуации — его можно назвать лидером или капитаном.
Подводные камни: на чем проваливаются неопытные участники
Как отмечают авторы курса, основные проблемы новичков связаны в первую очередь с переоценкой своих сил и возможностей. Максим Буздалов называет настоящим бичом неопытных участников их сногсшибательную уверенность в том, что код, который они написали, работает.
Причем они практически не различают [разницу между] «работает» и «работает на примере из условия». Им не приходит мысль проверить код еще раз, придумать контрпример, попробовать, наконец, доказать корректность решения. В частности, поэтому вердикт вида «Неверный ответ, тест 2» оставляет таких участников в крайней растерянности, а несколько таких вердиктов подряд — в состоянии основательной озлобленности.— Максим Буздалов
В качестве примера Максим приводит одну из задач с курса «Как побеждать в соревнованиях по программированию: секреты чемпионов». Дана матрица из чисел размера 3×3, необходимо выбрать из этой матрицы три числа так, чтобы ни в одном столбце и ни в одной строке не было бы выбрано более одного числа, а корень из суммы квадратов чисел был максимален.
Правильное решение этой задачи — по крайней мере, одно из них — очевидно: перебираем все возможные тройки номеров столбцов
Однако многие участники курса присылали такое решение: сначала выберем максимальное из чисел в матрице, затем вычеркнем соответствующую строку и столбец, затем опять выберем максимум, и так далее. Приводило это к неверному ответу на шестом тесте. Это решение очень легко «убить»: достаточно рассмотреть, что произойдет на такой матрице:
9 8 1
8 1 1
1 1 1
Правильное решение выберет две восьмерки и оставшуюся единицу, при этом сумма квадратов будет равна 129. «Жадное» решение выберет девятку, потом ему не остается ничего, кроме единиц, и сумма квадратов составит 83. Извлечение корня, конечно же, не изменит того, что первый ответ — больше, а следовательно, лучше.
Получив подобный пример, многие участники начали писать всевозможные разборы случаев, получая неверные ответы на том же тесте или на других тестах, при этом упуская главное — получив несложный контрпример для логики работы основной части своего решения, следует остановиться и подумать. Вместо затыкания дыр, расстановки подпорок и сколачивания костылей, хорошо бы хотя бы обосновать, почему решение вообще работает. А в идеале — математически строго доказать— Максим Буздалов
Еще одна распространенная ошибка, которую отмечает Дарья, — переполнение типа данных int:
Она [ошибка] случается в том случае, когда вы пытаетесь «положить» в переменную значение больше допустимого. Нужно быть внимательным и оценивать порядок ваших значений при решении задачи, и всё будет хорошо— Дарья Яковлева
Павел Кротков отмечает еще одну важную особенность опытных участников олимпиад — стрессоустойчивость. Ее новичкам также не хватает — именно поэтому неверное решение может легко вызвать недоумение и панику и приведет к потере драгоценного времени.
Об умении преодолеть стресс речь пойдет и во второй части нашей беседы: авторы и инструкторы курса расскажут, какую роль в процессе подготовки к соревнованию играет психология и правильный настрой, поделятся своими лайфхаками и маленькими хитростями, а также объяснят, кому (помимо будущих призеров олимпиад) может быть интересен курс «How to Win Coding Competitions: Secrets of Champions» Университета ИТМО.
Комментарии (2)
26 декабря 2016 в 14:30
0↑
↓
Для решения задачи с матрицей 3×3 перебор прокатит, а 30×30 — нет.
Тут, видимо, нужно допилить венгерский алгоритм.В курсе это раскрывается или студенты копошатся в песочнице 3×3?
itmo
26 декабря 2016 в 14:52
+1↑
↓
Уровень задач разный. При желании можно свои варианты обсуждать с организаторами курса. Новые идеи — win-win для всех.
