Медали для всех, даром, и пусть никто не уйдет обыгранным!

Добрый день, уважаемые друзья!

Глядя на нижеследующие ссылки (2011, 2012, 2013, 2014 — следует нажать ссылочку Standings), многие современники не спрашивают у меня, как прийти к подобным результатам. А зря.

К сожалению, сам по себе ритуал еженедельного посещения кружка умелых информационных ручек с опцией прорешивания особо приглянувшихся задач способен перевести Вас лет за 5 из состояния «сдаю на OCPC-18 три задачи» в состояние «сдаю на OCPC-23 семь задач». Цели и задачи факультатива не могут выходить за пределы предоставления Вам базовых олимпиадных знаний и навыков, а также развития способности самостоятельно ориентироваться в джунглях алгоритмов и языков программирования. Поэтому, воспользовавшись лицензией GNU (то есть, бесплатно), хочу распространить методику превращения обычной команды в призера полуфинала чемпионата Мира.

Данный подход зиждится на трех китах и одной черепахе:
1) Практика
2) Дорешивание
3) Теория
4) Собственно, черепаха

1) Практика. Состоит из личной и командной подготовки.
а) Личная тренировка заключается в ежедневном прорешивании по 1-5 задач в течение нескольких лет. Для этого на начальном этапе неплохо подойдет сайт acm.timus.ru, поскольку там, в отличие от е-олимпа, нет тысяч задач уровня а+б и задач с битыми тестами и поломанными чекерами. Через какое-то время после начала Ваших тренировок на тимусе Вы неизбежно столкнетесь с необходимостью овладения новыми алгоритмами, что и требуется. Также крайне рекомендуется решать личные контесты на codeforces.com и topcoder.com каждый раз, когда они начинаются не в 4 утра.
б) Командная тренировка заключается в еженедельном совместном с командой решении 5-часового контеста, соответствующего Вашему текущему уровню. Для этого отлично подойдет субботний кружок. Здесь Вы отрабатываете командную тактику, опыт взаимодействия, одновременное придумывание одной задачи, написание второй и дебага третьей за одним и тем же компьютером. Для этой цели может подойти, например, codeforces.com — там много соревнований самого разного уровня с очень хорошими тестами и возможностью соревноваться с другими участниками этого контеста.
Если закончился контест, а у Вас еще 2 недодебаженные задачи и 3 — с придуманными решениями, но Вы не успеваете их сдать, это верный признак того, что нужно поднажать на личные тренировки с целью довести до блеска известные Вам методы решения.

2) Дорешивание. Задачи, не решенные во время личной или командной тренировки, необходимо дорешать после разбора. На контесте Вы учитесь сдавать задачи, которые Вы умеете решать. На дорешивании — учитесь сдавать задачи, которые решать до сих пор не умели. Это основа любого роста, который состоит из двух частей — вширь и вглубь. Недорешенная задача может преследовать Вас годами из Полуфинала в Полуфинал, пока Вы не избавитесь от нее, как нерешенной, либо она — от Вас, как участника. Второе наступает всегда в силу возрастных ограничений для ACM ICPC.

3) Теория. Однажды наступает такой момент, когда прошла половина контеста, у Вас 5 задач, сданных с плюса, и еще 5, с которыми Вы понятия не имеете, что делать. Скорее всего, это означает, что настало время изучать новые алгоритмы. Для этих целей служит книга Кормена и др. «Алгоритмы. Построение и анализ», а также сайт e-maxx.ru/algo. В первую очередь стоит изучать те алгоритмы, которые чаще других упоминаются на разборе нерешенных Вами задач.

В команде для каждого «разлоченного» алгоритма должен быть один человек, который пишет его за известное время и со строго ограниченным сверху количеством ошибок и еще 2 человека должны иметь представление, что этот алгоритм делает, чтобы узнавать на него задачи. Для более простых/распространенных алгоритмов важно, чтобы их хорошо писали все трое. Чтобы изучить новый алгоритм, нужно прочитать и понять соответствующую статью, написать соответствующий рабочий код, а затем прорешать все доступные по теме задачи (их можно найти на тимусе и кодфорсе). Очень важно не заниматься копипастом, а писать решение каждый раз заново. Более того, желательно одну и ту же задачу сдавать по несколько раз, засекая время. В идеале, Вы должны тратить на реализацию от 5 до 15 минут (и знать заранее, сколько именно).
Где-то раз в пару месяцев нужно делать пересдачу хотя бы одной задачи по каждому изученному алгоритму, дабы навыки находились в тонусе. В целом, это касается более редких алгоритмов, поскольку часто встречающиеся и так будут попадаться Вам каждую неделю.
Кстати, важная составляющая теории — знание того языка программирования, на котором Вы пишете. Для C++ могу порекомендовать книгу Аммерааля по STL — в ней довольно неплохо описаны структуры данных и алгоритмы, реализованные в стандартной библиотеке.

4) Черепаха, на которой все и стоит, — осознание того, что никто не научит Вас решать задачи. Ни ув. преподаватели ОНУ, ни я, ни ув. Андрей Лопатин с ув. Андреем Станкевичем не проделают за Вас когнитивную работу по утрамбовыванию алгоритмов и методов решения задач в Ваш персональный мозг. Только Ваши усилия и Ваша инициатива способны перевести Вашу команду из аутсайдеров в лидеры. И всякое творчество приветствуется: читайте участникам кружка лекции по изученным Вами алгоритмам, придумывайте свои задачи и проводите по ним контесты (благо, сервер у нас есть), ездите на школы и сборы, общайтесь с единомышленниками. Искренняя заинтересованность и упорный труд свернут горы!

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

Завершить хочу мотивирующей ссылкой (ищем слово Odessa). С целью не повторения, но преодоления, разумеется.

FAQ или диалоги с умным человеком.

  1. Q: Ну выиграю я этот ваш Финал и что дальше?
    A: Ничего особенного.

  2. Q: Ваша команда возникла не на пустом месте. В ней было два призера школьных Всеукров по математике, не считая вашего основного кодера, который может работать по 16 часов в сутки. Мы не такие талантливые/трудоспособные.
    A: В команде ONU_Antananarivu не было ни одного призера Всеукра, однако до 2013 года они тренировались где-то на 70-80% мощности от ONU 1 2/3 и смогли решить достаточное для выхода в Финал количество задач. Их остановило только правило «один ВУЗ — одна команда». В то же время, к 2015-му году они почти перестали тренироваться, а победителем стала команда, занявшая 13-е место двумя годами ранее, а в 2012-м вообще не вышедшая в Полуфинал. Тем не менее, все участницы означенной команды сегодня работают в Корпорации Добра.

Олег Петров

Software Engineer at Snap Inc.
Los Angeles, California