«Спортивное программирование» — настольная книга новичка + 5 советов по подготовке к соревнованиям

Спортивное программирование — это состязания по решению задач на алгоритмы и отличный карьерный старт: победителей часто нанимают интернет-гиганты, такие как Amazon, Google, Facebook, VK, Яндекс и другие.

Но как победить в контесте и привлечь к себе внимание хедхантеров?

Издательство «ДМК Пресс» выпустило книгу «Спортивное программирование». Она вышла при поддержке Moscow Workshops, Mail.ru Group и МФТИ и нашего издания Tproger. Эта книга — полноценный гайд по спортивному программированию: в ней собраны теория, практика, лайфхаки и редкие темы, о которых мало кто пишет.

Спортивное программирование

Купить

Авторы книги — Стивен Халим и Феликс Халим — преподают в Школе программирования Национального университета Сингапура. Они — наставники команд Сингапура, которые участвуют в соревнованиях ACM ICPC и IOI.

Книга охватывает много тем. В ней содержится более 200 упражнений и около 1500 задач. Некоторые из них аналогичны задачам, которые используются на соревнованиях мирового уровня (ACM ICPC и IOI). Книга подойдёт как новичкам, так и опытным участникам.

Издательство «ДМК Пресс» подготовило промокод для наших читателей. Подробности в конце статьи.

Советы по подготовке к соревнованиям

В самой книге каждый из этих советов расписан гораздо подробнее и включает в себя конкретные практики, подводные камни и советы от наставников. Мы же только кратко расскажем о каждом из них:

• Учитесь быстро печатать. Банально? Да. Но в соревнованиях на время каждая секунда на счету. Бывает, участники не проходят, просто опоздав с решением. И речь здесь не только о наборе текста: нужно быстро набирать и сам программный код.
  Скорее всего, вы будете использовать IDE с автодополнением, и из этого тоже нужно выжать максимум. Уделите внимание знакам: следует легко ориентироваться, в каком регистре и на какой раскладке находятся нужные знаки.
  Среднее значение скорости печати — 200–250 знаков в минуту, но желательно добиться лучшего показателя. Чтобы проверить скорость печати, существуют онлайн-утилиты. Для программного кода есть тренажёр с выбором языка программирования.
• Оптимизируйте алгоритмы. Обычно одну и ту же задачу можно решить несколькими способами. На олимпиадном программировании вместе с заданием могут выдавать требования к программе: время выполнения и объём памяти. Перед началом разработки продумайте оптимальный для вашей задачи способ решения.
  Стоит знать, какие функции и операции ресурсозатратны, а какие — нет. Допустим, алгоритм должен вычислять много квадратных корней и сравнивать результат с каким-то значением. Операция извлечения корня потребляет больше ресурсов, чем базовые математические операции. Так что лучше отказаться от извлечения корня и сравнивать число со значением, возведённым в квадрат. Результат выйдет таким же при меньшей нагрузке на машину.
• Изучайте тонкости языков программирования. Основные языки для спортивного программирования — C++ и Java. C++ быстрый, а Java функциональна. Выбирайте язык в зависимости от задачи. Как минимум вам стоит уметь писать рабочий код на этих языках. Важно освоить как можно больше возможностей языка, чтобы использовать его эффективно, избегая костылей и велосипедов.
• Тестируйте код. На олимпиадах ICPC вы получаете баллы за полностью решённые задачи. Код должен пройти все секретные тесты, разработанные под эту задачу. Хорошей практикой будет написание собственных тестов. С их помощью нужно проверить:соответствие входных и выходных данных;выдачу одних и тех же данных в случае с мультитестами;наличие краевых случаев;способность обработать большой объём данных.
• Практикуйтесь. Даже если вы мастерски владеете каким-то языком, это не гарантирует успех в спортивном программировании. Постоянно решайте задачи и старайтесь превзойти себя — только так вы сможете добиться хороших результатов.
  Можно зайти в архив Timus Online Judge — крупнейший в России сборник задач по программированию с автоматической проверяющей системой. Другой отличный вариант — Codeforces.
  Если хотите потренироваться в спортивном программировании — заходите на Exercism.io. Там после каждой решённой задачи вы общаетесь с наставником: он поможет улучшить решение. acmp.ru — ещё один сервис с олимпиадными задачами и встроенной системой проверки.

В книге вас ждут и практические советы по решению, более сложные темы вроде декомпозиции задач и эффективных методов динамического программирования, малораспространённые темы вроде алгоритма Хопкрофта-Карпа, задачи 2-SAT и многое другое. Чтобы подробнее познакомиться с книгой и понять, какие темы она затрагивает, можно посмотреть оглавление и отрывки.

Специально для наших читателей издание ДМК Пресс подготовило промокод TPROGER15. Он даёт скидку 15% на покупку бумажной и электронной версии.