Как стать первым в спортивном программировании: Университет ИТМО делится опытом. Часть 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» Университета ИТМО.
    Университет ИТМО 142,95
    IT's MOre than a University
    Поделиться публикацией
    Комментарии 12
    • –1
      Для решения задачи с матрицей 3х3 перебор прокатит, а 30х30 — нет.
      Тут, видимо, нужно допилить венгерский алгоритм.

      В курсе это раскрывается или студенты копошатся в песочнице 3х3?
      • +2
        Уровень задач разный. При желании можно свои варианты обсуждать с организаторами курса. Новые идеи — win-win для всех.
      • 0
        А какие ограничения на таких соревнованиях? Можно ли использовать произвольные языки, скажем Haskell или Prolog? Можно ли при решении одной задачи использовать несколько языков сразу (например подготовка данных на Perl, а основные вычисления на том же Haskell)?
        • +1
          Все зависит от правил конкретного соревнования и компетенций тех, кто оценивает результат :)
          • 0
            Что можете посоветовать среди книг/статей/журналов для поднятия уровня знаний и навыков в области алгоритмов, их применений и оптимизации?
            • 0
              Планируем на эту тему дайджест сделать в начале следующего года. Не переключайтесь :)
              • 0
                Тогда если позволите, небольшой совет-просьба. Включите в дайджест материал от начального и выше уровней. А то обычно пишут — «читал вот это, крутая книга....» начинаешь ее читать и оказывается что перед ней надо еще 2-3 прочитать)
                • +1
                  Договорились
          • 0
            Как правило, на соревнованиях автоматическая система тестирования решений. На тестирование присылаются только исходники. Поэтому организаторы должны заранее настроить все компиляторы, определить версии компиляторов и опции, организовать взаимодействие с запускаемой программой (например, для java обеспечить вызов jar, а не exe). Поэтому, вряд ли можно надеяться встретить на соревнованиях Prolog или Haskell.
            • +1
              На Codeforces есть и Perl и Haskell и еще два десятка языков (считая разные версии/реализации).
              Несколько языков вместе использовать, правда, нельзя — и слава богу.
              • +1
                В чём проблема компилировать и запускать программы на Haskell?) До сих пор что ли ходит миф, что программы на Haskell никто не запускает, поэтому никто не знает, как это делать?
              • 0
                Недавно участвовал в олимпиаде где был вот такой вот набор языков: Pascal, С++, .NET C#, PHP, Ruby, Python. Для всех языков правила были примерно одни и те же: программа читает данные из файла input.txt в той же директории, а отдает данные в output.txt
                Все тесты проверялись автоматически и за каждый неправильный тест начислялись дополнительные 20 минут. Победитель тот, кто решит максимальное число задач за минимальное время.
                Были олимпиады где вообще от языка не зависишь. Есть 3 входных txt файла примера и 3 выходных txt файла результата. И есть еще 5 файлов для контрольной проверки. А на каком языке ты получишь результат это не важно.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое