Хочешь освоить интеллектуальный вид спорта, где работают логика, скорость и креативность? Это спортивное программирование, площадка для тех, кто любит задачи с подвохом и ощущение вызова.

GIGASCHOOL регулярно поддерживает чемпионаты по программированию, а также – обучающие центры. Сегодня мы обратились к директору центра олимпиадного программирования ЮУрГУ, Марине Сартасовой, с вопросом о подготовке спортсменов к соревнованиям по программированию. Разобрались, с чего начать, зачем участвовать и почему знания математики или выбор языка программирования бывают решающим фактором в победе.

Что такое спортивное программирование

Если коротко – это соревнование, где участники решают нетривиальные задачи за ограниченное время (обычно 5 часов).

Решение оформляется в виде компьютерной программы, которая должна успешно пройти набор тестов. Тест состоит из двух частей: правильные исходные данные и правильный результат решения задачи для данного теста. Если программа по правильным данным получает правильный результат, то тест считается пройденным. Для каждой задачи соревнования обычно разработаны от 10 до 60 тестов. Если хотя бы один тест для твоего решения не проходит – задача не засчитывается.

Какие навыки нужны

1. Первое и главное – желание!

2. Хорошая математическая база. Геометрия, теория чисел, комбинаторика, дискретная математика – часто именно они становятся камнем преткновения.

3. Список стандартных алгоритмов, которые должны быть на подсознании, как таблица умножения. Например, некоторые из большого списка:

   • бинарный поиск;

   • полный перебор;

   • сортировки (быстрая, слиянием);

   • жадные алгоритмы;

   • работа с графами (DFS, BFS, Дейкстра);

   • динамическое программирование.

   Необходимо отточить их и писать на автомате, на хорошей скорости набирать эти коды, не задумываясь.

4. Для участия в международных чемпионатах необходимо ещё знать английский, хотя бы на базовом уровне. Участникам разрешается брать словари, чтобы подсмотреть незнакомые слова.

5. Скорость. Чем больше задач ты решишь за эти пять часов, тем выше будешь в рейтинговой таблице.

С чего начать

Учить алгоритмы и разбираться в теории математики.
Освоить хотя бы один язык программирования (чаще всего – C++ или Python).
Решать задачи – много и регулярно.
Найти единомышленников: в школе, университете или онлайн.

Где искать сообщество

Необходимый шаг для командной игры – присоединиться к олимпиадному сообществу. Ищи центр по программированию или дополнительному образованию с уклоном в IT в своем регионе.
В социальных с��тях таких центров публикуют материалы, разборы и расписания соревнований.
Например, Центр олимпиадного программирования ЮУРГУ работает на базе университета, но открыт для всех желающих.

Полезные ресурсы для подготовки

• Контест – платформа для решения задач по программированию: contest.yandex.ru

• Школа программиста (архив задач по олимпиадному программированию): acmp.ru

• Центр олимпиадного программирования (учебные материалы и задачи, в том числе на английском языке): ipc.susu.ru

• 145 алгоритмов с краткими описаниями и программами на C++:
  http://e-maxx.ru/algo/

Выбираем язык: почему C++, а не Python?

Многие начинают с Python – он проще и понятнее. Сам код писать короче, потому что в язык уже вшиты многие алгоритмы (например, арифметика, работа с длинными и вещественными числами).

Но Python – интерпретируемый язык (код выполняется построчно, а не компилируется в машинный перед запуском), он работает медленнее. В олимпиадных задачах строгие лимиты по времени и это может стоить баллов.

C++ позволяет решать задачи быстрее. Фактически, Python написан на C++, и многие его функции обращаются к тому же коду, только с расходами на интерпретацию.

Пример: задача, выполняющаяся за 2 секунды на C++, на Python может занять 4 – и решение не засчитают. Само тестирование на C++ быстрее, поэтому на серьёзных этапах выбор очевиден.

Кому и зачем участвовать

• Школьникам – чтобы разобраться, подходит ли программирование как профессия. Олимпиады дают портфолио достижений и дополнительные баллы при поступлении.

• Студентам – ради перспектив и стипендий. Например, в программах ТОП‑500 достижения конвертируются в баллы, повышающие размер стипендии (на Урале – это может быть 25–50 тысяч рублей).

• Профессионалам – ради азарта и самого процесса соревнования. Это также может быть плюсом в резюме.

Если у ICPC (студенческий командный чемпионат мира по программированию) есть ограничения по возрасту до 24 лет, то в России участвовать можно в любом возрасте!

Что развивает олимпиадное программирование

Кроме хард‑скиллов (алгоритмы, код, математика), формируются и софт‑скиллы:

• концентрация и устойчивость в стрессовых условиях,

• анализ, планирование и адаптивность,

• скорость мышления,

• умение находить ошибки в чужом коде,

• умение придумать тест по задаче, чтобы найти место, где найденное решение ломается,

• командная работа и распределение ролей.

Олимпиады могут стать отправной точкой карьеры в IT – они создают базу для алгоритмического мышления, системного подхода и подготовки к техническим собеседованиям.

Марина убеждена, что «Мозги – это мускулы. Их необходимо тренировать.»

Не бойся соревноваться с профи

На многих олимпиадах уровень разделён: для новичков, продвинутых и профи.
Профи – это те, кто участвуют уже не первый год (например, участники четвертьфинала и полуфинала).

Такая система работает на Открытых командных соревнованиях по спортивному программированию Prime Time. Задачи одинаковые, но рейтинг ведется отдельно по каждой группе.

Кстати, иногда школьники обходят профессионалов!

Захватывающий вид спорта

В статье мы часто делаем упор на скорость, потому что олимпиадное программирование учит работать в условиях ограниченного времени. И это захватывающий вид спорта. Чтобы хотя бы немного передать атмосферу таких соревнований, расскажем про традицию с шариками на представительских олимпиадах и чемпионатах, на примере финала ICPC 2011 в Орландо.

Ни сами участники, ни зрители, никто не видит статус решения задач, пока не вынесут шарики — и зал в напряжении следит, кому они достанутся? На каждом шарике написан номер решенной задачи. Его получают команды, решившие задачу!

Проверь себя

Попробуй решить реальную задачу, а ниже мы приведем разбор.

Задача «Живой металл»

Некроны – древние создания из живого металла – славятся своей живуч��стью. Космодесантники ведут огонь из своих болтеров по некрону-криптеку, имеющему ? единиц энергии. При каждом попадании некрон теряет ? единиц энергии, но (если выжил) сразу же после этого восстанавливает половину всех текущих повреждений, то есть разницы между максимальным и текущим уровнем энергии (с округлением вниз). Определите, смогут ли десантники победить некрона, а если смогут – то сколько выстрелов им потребуется.

В единственной строке ввода содержится пара натуральных чисел: ?
– максимальная энергия некрона и ?
– урон от одного выстрела (0<?,?≤109).

Выведите единственное число – количество выстрелов, необходимое космодесантникам для того, чтобы довести энергию некрона до 0. Если сделать это невозможно, выведите -1.

Необычные решения

Спросили у Марины про одно из самых необычных решений ее учеников.

«Команда – призер ВКОШП, делилась впечатлениями: «Задача не заходила. Мы взяли, все засунули в большой двумерный массив. И в зависимости от значения N и M, просто выводили соответствующую строку. И всё!!!» У них задача зашла.

То есть, по-всякому придумывают. Просто на большие размеры матрицы или, что там у них было, не заходила. Бывает, по времени не заходит. Вот они придумали такой вариант».

Разбор задачи

Хочешь рассказать свою историю участия в олимпиадах или поделиться опытом подготовки? Пиши в комментариях, соберем практический гайд для начинающих!