Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 <a>#статьи</a>

2 <ul><li>15 апр 2024</li>

3 <li>0</li>

4 </ul><h2>О код, ты - мир: что такое спортивное программирование и при чём тут спорт</h2>

5 А также даёт ли выбор языка программирования преимущество при решении задач.

6 Фото: Leon Neal / Getty Images

7 Пишет об истории IT, разработке и советской кибернетике. Знает Python, JavaScript и немного C++, но предпочитает писать на русском.

8 В одном из выпусков подкаста "Люди и код" мы поговорили с Ильёй Кучумовым, который на протяжении семи лет участвовал в различных соревнованиях по спортивному программированию и побеждал в них. Илья рассказал, что это за спорт такой, и поделился собственными наблюдениями о подготовке, тактике и психологии соревнований.

9 Эта статья - конспект беседы от первого лица. Послушать<a>аудиоверсию</a>можно на одной из популярных подкаст-площадок.

10 Руководитель отдела разработки поиска по товарам в "Яндексе". Во время обучения в университете стажировался в одном из европейских офисов Google.

11 В 2018 году занял второе место в финале Google Hash Code, а в 2017-м - 14-е место в финале<a>ICPC</a>. Является автором двух задач для финального раунда<a>Yandex Cup 2022</a>в дисциплине "Алгоритм".

12 Суть спортивного программирования заключается в том, что участникам нужно за ограниченное время решить несколько сложных алгоритмических задач. В описании каждой задачи определён формат входных и выходных данных, а также приведены примеры и соответствующие им результаты. Участникам предоставляют компьютеры: один на команду или по одному на каждого участника - в зависимости от условий.

13 При этом недостаточно написать код, который будет выдавать верный результат. Программа должна быть достаточно быстрой, то есть находитьрешения с разными входными данными за отведённое в условии время (например, за 1 секунду) и не потреблять объём памяти выше заданного значения (например, 256 МБ).

14 Как правило, очевидные решения, которые приводят к правильному результату, оказываются слишком медленными или "тяжёлыми", поэтому приходится разрабатывать более эффективные алгоритмы.

15 Типичная задача для соревнований, взятая из архива<a>codeforces.com</a>.

16 Ограничение по времени на тест:3 секунды

17 Ограничение по памяти на тест:256 мегабайт

18 Ввод: стандартный ввод

19 Вывод: стандартный вывод

20 На двухмерной декартовой плоскости расположеноnгородов. Расстояние между двумя городами равняется Манхэттенскому расстоянию между ними (определение см. в примечаниях). Гамильтоновым циклом указанных городов является перестановка из nгородов. Длина этого Гамильтонова цикла определяется как сумма расстояний между смежными городами в перестановке плюс расстояние между первым и последним городом в перестановке. Пожалуйста, подсчитайте длиннейшую возможную длину Гамильтонова цикла данных городов.

21 Входные данные

22 В первой строке записано целое числоn(3 ≤n≤ 105). Затем следуетnстрок, в каждой записано по два целых числаxiи yi(0 ≤xi,yi≤ 109), обозначающих координаты города. Все данные точки различны.

23 Выходные данные

24 Выведите единственную строку, обозначающую наибольшую возможную длину Гамильтонова цикла данных городов. Сам цикл выводить не надо, только его длину.

25 Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

26 Примеры

27 Входные данные41 11 22 12 2Выходные данные6Командные.Обычно проводятся среди студентов. Группы по три человека в течение пяти часов решают алгоритмические задачи, которые предполагают наличие точного решения. На команду выдаётся по одному компьютеру. Количество задач - от 8 до 12. Кто решил больше, тот и выигрывает.

28 Самый популярный чемпионат этого формата -<a>ICPC</a>(International Collegiate Competitive Contest). Соревнование состоит из четырёх, иногда из пяти этапов. Финал проводится в разных странах, среди которых США, Португалия, Индонезия, Бангладеш и другие. Ежегодно в ICPC участвует около 1300 студентов.

29 Индивидуальные.Это довольно суровые баталии, как правило, без ограничений по возрасту, поэтому на них можно встретить ветеранов с 15-20-летним стажем. Победить или хотя бы пройти в финал невероятно сложно.

30 Самые известные и престижные индивидуальные состязания -<a>Topcoder Open</a>,<a>AtCoder</a>и Google Code Jam (прекращено в 2023 году). Есть и локальные российские события вроде<a>Yandex Cup</a>.

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

32 Оптимизационные задачи решают на Topcoder Open Marathon и Google Hash Code.

33 В 2018 году мы с командой участвовали в Google Hash Code. В финале была задача по проектированию города. Нужно было расставить жилые дома, детские сады и больницы так, чтобы жителям было достаточно комфортно там жить: чтобы дорога до больницы не занимала много времени, детские площадки были не слишком далеко от домов и так далее. Выиграл тот, кто разместил на карте больше всего жителей. У этой задачи не существует математически оптимального решения - любое решение можно понемногу оптимизировать.

34 Также появляются новые форматы, связанные с машинным обучением, но они не относятся к классическому спортивному программированию.

35 Слово "спорт" в нашем деле появилось не случайно, ибо здесь, как и в баскетболе, хоккее и других командных играх, важны подготовка и тактика. Нужно эффективно использовать время и сильные стороны членов команды, а также достичь высокой степени сыгранности. В связи с этим возникают разные требования к командному составу: нельзя просто взять и набрать трёх сильных программистов - у каждого должна быть специализация.

36 Например, один участник, отлично знающий язык программирования, может отвечать за программную реализацию алгоритма. Другой - быть спецом в узкой теме вроде линейной алгебры или вычислительной геометрии, а третий - выполнять роль этакого универсального солдата, способного выстроить "мостик" между тиммейтами.

37 В условиях ограниченного времени важно определить, какие задачи брать в работу в первую очередь, какие - во вторую, а какие вовсе лучше выбросить. Поэтому в любой хорошей команде должен быть лидер, за которым остаётся последнее слово в таких вопросах. Хотя, конечно, почти всегда это решается сообща.

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

39 Часто на соревнованиях выдаётся один компьютер на команду, поэтому если кто-то отлаживает программу, то другую в этот момент писать нельзя. Так что тестирование - один из важнейших элементов тактики.

40 У нас были свои хаки в тестировании. Например, мы могли быстро запустить программу на тест-кейсах, распечатать на принтере промежуточные значения и по листочкам разбираться, что пошло не так. Или быстро написать генератор тестов, запустить перебор и найти случайный тест, на котором решение не сработает.

41 Выбор конкретной модели поведения зависит от вида соревнований и ваших возможностей. На сложных и ответственных играх, таких как финал чемпионата мира, где даётся только одна попытка, чаще всего придерживаются консервативной тактики. Не нужно пытаться решить задачу в одиночку, рисковать и принимать опрометчивые решения.

42 Это зависит от соревнований.

43 Например, на Codeforces вводятся отдельные ограничения по времени для скриптовых языков, таких как Python. И если решение на C++ должно срабатывать не более чем за две секунды, то на Python - не более чем за пять. Поэтому на таких соревнованиях язык большой роли не играет.

44 На соревнованиях вроде ICPC или Topcoder Open картина немного иная. Набор языков там гораздо уже. Например, на ICPC это C++, Java, Python и, вы удивитесь, Ada. Никаких "поблажек" для скриптовых языков там нет: одинаковое ограничение по времени и для C++, и для Java, и для Python. Поэтому выбор языка здесь очень важен.

45 Обычно выбирают между C++ и Java. При этом жюри гарантирует, что решение, которое укладывается в заданные ограничения, существует как для C++, так и для Java, которая по умолчанию более медленная. Но, положа руку на сердце, у команды с "плюсами" часто больше шансов пройти по времени: иной раз даже более-менее простые решения со сложностью О (n^2) укладываются в 1,95 секунды. И это, конечно, важное преимущество.

46 Тогда почему некоторые всё-таки выбирают Java? Банально потому, что в Java легче отлавливать баги: чуть что - язык тут же расскажет и покажет, что и где пошло не так, и это намного приятнее, чем словить undefined behavior и полчаса его дебажить.

47 Иногда мы влюбляемся в собственные идеи и долго не можем от них отказаться. В спортивном программировании это может стать большой проблемой. Подобно лудоманам, вы рискуете попасть в ловушку азарта и думать, будто, просидев за задачей ещё пять минут, уж точно найдёте решение. А часы продолжают предательски тикать, оставляя всё меньше времени на остальные задачи…

48 Принять решение помогает таблица результатов, в которой видно, сколько команд решили ту или иную задачу. Если вы бьётесь над как бы очевидной задачей, которую "вот-вот решите", а все команды ловят за неё прочерки, то это явный сигнал, что надо бросать.

49 Гораздо сложнее, когда все задачу сдают, а вы нет. В таком случае полезно отложить её на время, например на час, и переключиться на что-то другое. Или устроить перезагрузку: отбросить всё, что нарешали, и начать сначала. Также иногда помогает "брутфорс" с помощью генератора случайных тестов, о котором я писал выше.

50 Умение вовремя остановиться полезно и в промышленной разработке. Увлеченные программисты в поисках бага способны просидеть сутки перед монитором, хотя часто бросить и смириться с тем, что сегодня "не идёт", бывает куда эффективнее. Вполне вероятно, что уже на следующий день, когда вы вернётесь к коду, отдохнув и сбросив контекст, неуловимый баг отыщется в считаные минуты.

51 Нерешаемые или очень сложные задачи в спортивном программировании в шутку называют "гробами". Важно как можно раньше их распознать, чтобы отложить напоследок или вовсе отбросить и не тратить время впустую. Здесь хорошо помогает опыт, интуиция и наблюдение за другими участниками: если никто задачу не сдаёт, значит, скорее всего, это "гроб".

52 С другой стороны, далеко не всегда стоит следовать за толпой - даже если это толпа программистов-олимпиадников. Бывает, что несколько команд не могут сдать задачу просто потому, что что-то упустили, а остальные пугаются и отбрасывают её. Потом эта же задача встречается на локальном соревновании, какая-нибудь команда её решает в первый час, и за ней находят решение другие. Мнение толпы иногда сильно влияет на результат.

53 Один из примеров "гробов" - геометрия, в частности с трёхмерным пространством, с математическими моделями, подход к которым непонятен.

54 Решать, решать и ещё раз решать! Чем больше задач разберёте, тем выше вероятность, что на соревнованиях попадётся что-то знакомое или даже аналогичное ("баян", другими словами). Мы использовали архивы уральского чемпионата на <a>acm.timus.ru</a>. К концу олимпиадной карьеры у всех в личном зачёте было примерно по тысяче задач.

55 Но решать задачи в "тепличных условиях" - это всё равно что готовиться к чемпионату мира по футболу, играя только с товарищами по команде. Нужно постоянно мериться силами с соперниками, чтобы понимать свой реальный уровень подготовки. Для этого есть несколько инструментов.

56 Виртуальные соревнования.Всё, чему вы научились на первом этапе, нужно отработать в стрессовых условиях ограниченного времени. Для этого на площадках вроде Codeforces и Opentrains есть виртуальный режим, который позволяет участвовать в соревновании так, будто с вами в реальном времени соревнуются другие команды. Результаты отображаются в таблице, и исход игры заранее неизвестен.

57 Во время активной подготовки мы играли в таком режиме два-три раза в неделю. Далее приступали к разбору нерешённых задач: изучали решение на сайте и попутно необходимую теорию. Всё это занимало более 30 часов в неделю, как настоящая работа на фултайме.

58 Загородные сборы.Это отличная возможность помериться силами с реальными соперниками и порешать задачи, которых ещё ни разу не было на соревнованиях. Сборы проводятся в Москве, Петрозаводске, Ижевске и <a>других городах</a>и длятся одну-две недели.

59 Локальные соревнования.Участвуйте в местных чемпионатах, которые проходят в Екатеринбурге, Новосибирске, Москве, Санкт-Петербурге и других региональных центрах России. Регулярное участие повышает стрессоустойчивость и адаптивность к смене локаций и позволяет подходить к более глобальным соревнованиям, таким как финал ICPC, менее восприимчивым к раздражителям, которых там в изобилии.

60 ?Советы от профи

61 Найти советы по подготовке можно на <a>Codeforces</a> - это одна из крупнейших мировых площадок по спортивному программированию. Помимо контестов и отдельных задач, там есть блоги, в которых участники сообщества публикуют советы. Можно найти десять самых залайканных постов и выбрать подходящую стратегию. Если человек входит в мировой топ-100 или топ-200, то, скорее всего, знает, о чём говорит.

62 Я бы рекомендовал отталкиваться от задач: сначала попытаться что-то решить, а потом изучить соответствующую теорию. Не существует волшебной книги, по которой можно подготовиться, как готовятся к экзамену в университете.

63 Спортивное программирование развивает навык решать алгоритмические задачи любой сложности. Многие задачи перестают казаться хоть сколько-нибудь сложными, и это даёт вам преимущество на технических интервью, особенно в крупных IT-компаниях, где алгоритмам уделяется много внимания.

64 Когда я проходил собеседование в "Яндексе", алгоритмическая часть прошла очень легко. Более того, я умудрился отравиться перед вторым этапом, но всё же решил не переносить его… Думаю, что даже в таком моем состоянии интервьюер быстро понял, что я легко справляюсь с алгоритмическими задачами.

65 Есть и менее очевидные вещи, которые также важны.

66 ✅ Во-первых, на соревнованиях прививается "алгоритмический подход" к решению задач:

67 <ul><li>сформулировать задачу,</li>

68 <li>понять её;</li>

69 <li>определить "корнер-кейсы" и ограничения;</li>

70 <li>расписать решение в общем виде.</li>

71 </ul>Другими словами, это способ решать задачи без паники и распыления фокуса. К нему довольно быстро привыкаешь - и начинаешь использовать даже в процессе проектирования крупных систем.

72 ✅ Во-вторых, спортивное программирование прокачивает навык работы в стрессовых ситуациях, когда нет права на ошибку.

73 Мне это пригодилось на on-call-дежурствах, когда случались неожиданные всплески трафика или череда "четырёхсотых" ответов. Нам известно лишь, что мы падаем, и ещё какие-то симптомы. Времени на тестовый запуск кода и отладку нет, на руках только снапшот кода, который полчаса будет собирать нужный бинарник, а сервис падает прямо сейчас.

74 Стандартная ситуация на олимпиаде: до окончания 15 минут, при одном из тестов программа выдаёт неверный результат, и в таком стрессе, под огромным давлением нужно успокоиться и сконцентрироваться. С опытом учишься отбрасывать эмоции и продолжать думать ровно до тех пор, пока соревнование не закончится.

75 ✅ В-третьих, соревнования учат работать в команде со сложными, но талантливыми людьми. Особенно это касается серьёзных соревнований, когда вы попадаете в топ-100 в мире или в топ-10 по России в командном зачёте. На этом уровне остаются очень талантливые ребята, у которых высокое (что справедливо) мнение о себе. Эти люди способны решить практически любую техническую задачу, хоть и не все обладают сильными софт-скиллами.

76 Теперь о недостатках. Их почти нет.

77 ❌ Низкое качество кода.Нужно признать, что с точки зрения продакшена качество олимпиадного кода оставляет желать лучшего. С другой стороны, олимпиадные программы и не нужно поддерживать.

78 Код - это инструмент, с помощью которого люди решают задачи. Если вы разрабатываете сервис, над которым работают десятки и сотни инженеров, то да, качество выходит на первый план. Но на олимпиаде, в условиях ограниченного времени, когда нужно решить 8-12 задач за пять часов, важно лишь получить работающее решение (иногда это актуально и в профессиональной разработке).

79 Я нанимал много ребят с олимпиадным прошлым и могу точно сказать: если понятно и аргументированно объяснить джуну, почему надо соблюдать код-стайл, проблем не возникнет. В то же время умение быстро написать работающий "одноразовый" код для проверки гипотезы высоко ценится.

80 ❌ Игра (не) стоит свеч.Многие плюсы, которые я перечислил выше, появляются, когда вы добрались до топ-100 - топ-200 в мировом командном зачёте. Но вот вопрос: а зачем стремиться дальше и выше? Зачем пытаться занять пьедестал?

81 Кажется, что, кроме подпитки ЧСВ и нескольких тысяч долларов, это не даёт практически ничего. Зато у среднего олимпиадника, который, помимо алгоритмов, силён в смежных дисциплинах, в том же ML, куда больше карьерных возможностей.

82 Сейчас я думаю, что занятия спортивным программированием не прошли даром, хоть когда-то и разочаровался в нём. Ещё в начале карьеры в "Яндексе" я задумался о том, что, помимо алгоритмов, надо было заниматься ещё чем-то, уделять больше времени университету и изучению технологий…

83 Но какое-то время спустя я всё же пришёл к выводу, что опыт попадания в топ придал мне уверенности в том, что я могу решить почти любую задачу. На чемпионате мира я конкурировал с сильнейшими программистами из разных стран, сразился с ними в честной борьбе, где решают не деньги и связи, а интеллект. Эта уверенность определённо стоила пяти лет активных занятий спортивным программированием.

84 Пожалуй, самая крупная звезда - белорусский программист<a>Геннадий Короткевич</a>(выступает под ником tourist). В 2020 году он занимал первое место в рейтингах<a>Topcoder</a>и <a>Codeforces</a>.

85 Ещё одна знаменитость -<a>Пётр Митричев</a>. Он также одержал победу в невообразимом количестве соревнований.

86 Среди стран, если считать по общему количеству побед в индивидуальных, студенческих и школьных соревнованиях, лидируют Польша, Россия, Беларусь, Китай, Япония и США. Особенно в последнее время выросла российская команда: за 15 лет мы выиграли около 10 мировых чемпионатов.

87 В этой статье мы обсудили классическое спортивное программирование, но прогресс не стоит на месте и понятие "классика" весьма эфемерно. Организаторы чемпионатов следят за трендами и постоянно экспериментируют с направлениями и форматами.

88 Выше я уже упомянул оптимизационные задачи, приближенные к тем, что каждый день решают инженеры в BigTech-компаниях вроде "Яндекса", Amazon и Netflix. Недавно Google устраивал соревнования по программированию распределённых систем, задачи на которых по условиям напоминают реальные. И конечно, куда без соревнований по машинному обучению, которые уже регулярно проводятся в разных странах.

89 Уверен, через 5-10 лет спортивное программирование изменится до неузнаваемости. Может быть, промпт-инжиниринг станет одной из флагманских дисциплин и мы напишем новую статью о "классическом" спортивном программировании.

90 <a>Бесплатный курс по Python ➞Мини-курс для новичков и для опытных кодеров. 4 крутых проекта в портфолио, живое общение со спикером. Кликните и узнайте, чему можно научиться на курсе. Смотреть программу</a>