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