Привет, Codeforces! Я, как и многие из вас, периодически читаю блоги. В последнее время мое внимание стали привлекать блоги от пользователей с низким рейтингом, которые спрашивают, как им поднять свой рейтинг. Хочу немного рассказать о своем мнении по поводу этих блогов.
Итак, что же их себя представляют эти блоги? Обычно это блог с заголовком что-то вроде "Срочно нужна помощь!" или "Как улучшить рейтинг, помогите!" Когда открываешь этот блог, то видишь максимально подробное описание проблемы, например, такое: "я решил уже 500 задач, а улучшения все нет и нет." или "я решил уже 100 задач с рейтингом >= 1500, а мой рейтинг не увеличивается". А в комментариях им обычно пишут "ты недостаточно решал, решай больше" ну или "решай более сложные задачи". На мой взгляд, это неверно, и вводит таких пользователей в заблуждение. Позвольте объяснить, что я имею в виду.
Итак, представьте, что вы вообще ничего не знаете ни о спортивном программировнии, ни даже об основах олимпиадной математики. Вы в лучшем случае (поскольку многие не делают даже этого) выучили язык программирования на базовом уровне (действительно, кому нужны шаблоны и классы) уровне, например, С++. И вот, вы решили стать спортивным программистом, чтобы пройти собеседование получить удовольствие от решения интересных задач. Представьте себя таким человеком. Представили? Нет, представьте пожалуйста, это важно.
Когда вы представили это, представьте теперь, что у вас вообще нет друзей, которые бы знали, что такое программирование. "Программирование, а? А это съедобное?" Ну я шучу, конечно, но такое вполне может быть, что никто из окружения не увлекается программированием. Итак, теперь вопрос. Как совершенствоваться? "Что за глупый вопрос?" — спросите вы, "конечно же, просто идти и решать задачи!" Просто все подряд, а может быть, и какой-то там ladder (про который я, увы, ничего особо не знаю). Так вот, заявляю: на мой взгляд, это очень вредный совет, который только навредит тому, кто начинает свой путь в спортивном программировании. Вот вы же представили себя новичком? А теперь подумайте: если вы знаете только школьную математику, сможете ли вы решить D2A? Если вам кажется, что сможете, я вам открою секрет: если вы не прирожденный гений спортивного программирования, то едва ли.
Расскажу немного о том, почему. Как может быть видно из моего профиля, я из Беларуси, из города Могилева. В этом славном городе есть славная гимназия номер два, в которой преподает мой замечательный учитель EIK. У нее много олимпиадников, как начинающих, так и весьма опытных, вроде Dmi34, а также куча выпускников, среди которых, например, я, а также еще один международный мастер и международный гроссмейстер. И могу вам сказать: если сейчас взять ее начинающих, то я не уверен, что они сразу за первый год смогли бы решить даже D2A. Объясню, почему.
Все дело в том, что подходить даже к D2A на самом деле надо постепенно (если, конечно, у вас нет опыта в олимпиадах по математике, скажем — тогда решать D2A в целом идея неплохая). Вернемся к нашему мысленному эксперименту — возьмем любую случайную D2A за последние два года.
Абсолютно случайным образом был выбран раунд 672 и задачу А из него (1420A - Сортировка кубов). Подумайте: насколько легко человеку, знающему только школьную математику, решить эту задачу? Например, у нас в университете на факультете проходят небольшой раздел (на одну-две лекции), посвященный перестановкам, и из этих знаний легко решить эту задачу. А вот если вы знаете только школьную математику (и у вас обычная, ничем не примечательная школа), то решить такую задачу будет явно не так уж и просто. На самом деле, понять, что неотсортированный массив может быть отсортирован пузырьком за n * (n-1) / 2 операции не так уж и сложно, если рассуждать логически. Как мне кажется, сложнее показать, что для неотсортированного массива это не выполняется.
Или вот раунд 697, задача А (1475A - Нечетный делитель). Конечно, эту задачу можно решить, просто выписывая на листочке все числа, и найдя закономерность. Но тут уже надо знать, что такое разложение числа на простые множители, знать, что оно единственно и так далее. Вспоминая жадные алгоритмы, могу отметить задачу из раунда 765, задачу А (опять выбрана случайным образом) (1625A - Древняя цивилизация).
Это я все к чему. Для спортивного программирования необходимо знать математику. А вот теперь представьте себе: человек прорешал, скажем, 100 задач А. Учитывайте, что большинство из них не содержат вообще никаких новых и интересных идей, а просто, как принято говорить, ad-hoc. Что же он узнает из этих задач? Я не уверен, но мне кажется, что просто ничего! Он запомнит двадцать идей, но двадцать первая все равно будет другой. Возвращаясь к нашему воображаемому новичку: ему не у кого спросить, некого попросить объяснить. Некому объяснить стандартные идеи и подходы. Ну вот и что остается ему делать, кроме как читерить писать блоги?
А с задачами B, C и D ситуация еще хуже. Чтобы решать их, обычно требуется уже знание стандартных идей. Проблема в том, что для того, чтобы отработать эти стандартные идеи, нужно решать задачи на эти стандартные идеи, а не сразу D2C — D2D. Представьте себе, если бы вы учили дерево отрезков сразу по задаче сложностью 3000. Это не очень хорошо.
Завершая первую часть блога: Codeforces — это точно не место для практики новичков. Если более опытные пользователи могут тренироваться тут, то для новичков это вряд ли подходит. Что делать, я не знаю, а почему не знаю, поясню позже.
Теперь переходим ко второй части. Теперь я хочу объяснить, почему, на мой взгляд, подход решения задач по сложности на Codeforces это плохая идея.
Давайте посмотрим на несколько (опять же, совершенно точно случайно выбранных задач). Сразу скажу: тут будет мое субъективное мнение. Посмотрим на задачи 858B (858B - Какой этаж?) и (996B - Чемпионат мира). Первую я считаю очень простой для своей сложности, а вторую — ну очень уж сложной. Обе задачи я решал довольно давно, но помню лишь, что когда я был специалистом, первую я решил, хоть и с трудом, а вот когда я был кандидатом в мастера, вторая доставила мне серьезных трудностей -- я даже не помню, решил я ее или нет!
Это уже не говоря о том, что система тэгов на Codeforces не очень хороша, и часто сбивает с толку. Например, в теме ДП может попасться задача на префикс-сумму, а во многих задачах тэги ставятся по принципу "вот задача на ДО/ДП/битовые операции. Но ее можно решить потоками. Поставим-ка теги: графы, потоки. О! Еще и тернарный поиск применить можно! Так и поставим!" Так что тэги реально далеко не всегда отражают тему задачи.
Это я все к чему. Тренироваться надо по темам, а не по сложностям. Особенно когда вы еще не так высоко. Не стоит бояться того, что у вас не получаются ad-hoc задачи — главное, чтобы было хорошо со стандартными идеями.
Многие комментаторы, которые пишут "решай больше задач", на мой взгляд, просто (и это нормально) подзабыли, каково это быть серым или зеленым. И это нормально: я тоже не помню, как я решал, будучи внизу. Но, глядя на то, как мой преподаватель год или два дает исключительно стандартные задачи и подходы, я начинаю понимать, что она скорее всего делает все правильно.
Возвращаясь к нашему примеру — откуда такому человеку знать, какие темы стандартные и какие нет? Он максимум может только узнать названия тем. И кстати, видимо, это и объясняется такое количество серых, которые учат декартово дерево и алгоритм Мо — они не совсем понимают, какие вещи нужны на каком уровне. А почему не понимают? На мой взгляд просто потому, что некому объяснить. Поэтому, если ты новичок / ученик и читаешь это, знай — надо изучать подходы, а не алгоритмы. А алгоритмы лучше не учить, а понимать. Наверное, стоит изучить алгоритм тогда, когда хотя бы один/два раза встретится задача, в которой ты можешь довести решение до конца, полностью и самостоятельно, если бы кто-то за тебя написал этот алгоритм. То есть ты придумал все шаги, всю математику, свел задачу к хорошо известному алгоритму — тогда можешь открыть его и попытаться понять. Кстати, если не получается понять, можно пока и выучить — как мне кажется, это нормально. Позже можно вернуться для понимания (когда будет больше опыта). Когда я был специалистом, я не понимал дерево отрезков (правда, я тогда был школьником, причем даже не старшим).
Поэтому, плавно переходя к главной идее этого блога — я не представляю, как можно заниматься без тренера. Конечно, когда все основные идеи изучены, и алгоритмы отточены, двигаться без тренера можно. Но, скажем, до эксперта или даже до кандидата в мастера без тренера будет гораздо тяжелее. Я знаю, что есть много людей, которые занимались сами, и достигли высот. Мне кажется, что вы — это скорее исключение из правила, чем правило. Я очень рад, что у вас все получилось. Но лично я понимаю, что без тренера мой прогресс был бы куда медленнее.
Я знаю, что если люди, которые пришли сюда тренироваться для собеседований. Ребята, это вообще не место для такого. Для этого придумали LeetCode — там есть куча прекрасных задач для подготовки, сам прорешал десяток-другой.
Напоследок: на мой взгляд, Codeforces стоит определиться: он все-таки должен быть тренировочной площадкой для новичков, или он должен быть тренировочным только для более старших званий? Потому что, если он должен быть тренировочной площадкой и для серых/зеленых, то, кажется, это не так. Потому что Educational раунды совсем не Educational, это обычные Div. 2 раунды, которые лишь немного более стандартные в плане идей и подходов. Даже Div. 3 раунды, которые предназначены для серых и зеленых, и то в последнее время опять начали содержать ad-hoc, а не стандартные задачи. Я понимаю, что это сделано для консистентности рейтинга. Но пусть бы действительно были простые задачи для новчиков. В разделе Edu есть задачи на стандартные алгоритмы — поверьте, изучение этих алгоритмов не принесет особой пользы серому или зеленому.
Поэтому, если хочется создать более благоприятную среду для начинающих, сделать отдельные, возможно, нерейтинговые, тренировочные раунды. Я понимаю, что в каждый раунд Codeforces вложены огромные усилия авторов, координаторов и организаторов (сам автор двух раундов и соавтор еще одного). Быть может, поэтому, скорее всего, Codeforces останется таким, какой он и есть. И знаете что? Я буду только рад. Наверняка (но я не знаю точно), есть куча мест, где могут тренироваться новички. Пусть Codeforces остается таким же прекрасным, какой он есть сейчас, с задачами ad-hoc. На мой взгляд, это и делает раунды такими интересными и захватывающими (только пожалуйста, не надо делать все задачи на одну тему. Примеры приводить не буду, но такие есть. Поверьте, это не круто).
Спасибо Codeforces за то, что ты есть!