Спустя 5 лет я снова пишу Всеросс — часть 2

Привет, Хабр! На связи финалист ICPC и гроссмейстер Codeforces MachineSolution. Также напомню, что я продолжаю рассказывать о своей подготовке и соревнованиях в Telegram-канале Machine Solution. Иногда я также беру учеников на индивидуальные занятия. Если вам понравились мои статьи и хочется прокачаться в спортивном программировании — пишите мне, обсудим.

Это вторая часть истории о том, как спустя пять лет после своего школьного Всеросса я решил написать зеркало заключительного этапа ВсОШ по информатике 2026 года. Первую часть можно прочитать здесь. Там я подробнее рассказал о формате олимпиады, стратегии набора баллов и о том, как прошёл мой первый день.

Что было после первого дня

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

В первой части я предлагал примерно такие ориентиры на один день:

100 + 70 + 40 + 15 — хороший темп для борьбы за диплом призёра.

100 + 100 + 60 + 35 — ориентир уже на диплом победителя.

Почему именно такие числа и откуда они взялись, я подробно разбирал в первой части.

Перед первым днём моей целью было понять, способен ли я сейчас написать Всеросс на уровень призёра. Но получилось гораздо лучше, чем я ожидал: я набрал 295 баллов, а если наложить этот результат на реальный рейтинг первого дня, то занимал бы примерно 8-е место.

Поэтому ко второму дню настрой был уже совсем другим. Если первый тур я начинал с мыслью «хочу проверить, тяну ли я на призёра», то теперь хотелось понять: а могу ли я действительно написать весь Всеросс на диплом победителя?

С этой мыслью я и открыл задачи второго дня. И вот что произошло.

Ход второго дня

0:31 — 100 баллов по A

За первые полчаса я решил первую задачу, но сдал её не с первого раза. Пришлось немного помучиться, чтобы получить решение без логарифма и проявить некоторую технику, что слегка сбило меня с победной колеи. Всё-таки я считал, что первую задачу нужно закрывать быстрее. Но смотреть на подзадачи здесь не было смысла — нужно было просто полностью написать верное решение, с чем я в итоге справился. В 0:31 — первый Accepted на 100 баллов.

0:59 — 85 баллов по B

Дальше я прочитал задачу B и уже посмотрел, какие там есть подзадачи. Увидел, что последние две подзадачи стоят суммарно 15 баллов, и сначала даже не понял, почему они так важны.

Я придумал решение и думал, что напишу на 100 баллов, но в 0:59 увидел в тестирующей системе 85. Тут-то и стало понятно, почему последние две подзадачи действительно являются существенным усложнением.

Но на этот раз я не расстроился и решил пока эти 15 баллов оставить. Логика была очень простая: их я, скорее всего, смогу взять позже, когда захочу. Пока же, следуя своей стратегии, лучше открыть другие задачи, порешать их и набрать там какие-то баллы — это, скорее всего, будет продуктивнее, чем прямо сейчас биться за эти 15. Тем более заранее я не мог понять, насколько они там простые или сложные.

Задача C

Здесь уже был другой, стандартный паттерн по набору баллов. Я смотрел на подзадачи не как в B — с конца, на последние ограничения, — а сначала. И увидел, что первые три подзадачи дают довольно жёсткие ограничения на входные данные. Поэтому что? Поэтому пишем наивное решение, которое работает за какое-то время, пускай и очень неоптимальное.

1:16 — 35 баллов по C

В 1:16 у меня уже было 35 баллов по задаче C, что очень даже здорово. Обычно такие наивные решения легко получить, и здесь я как раз-таки относительно обрадовался, что наивное решение очень простое и даёт достаточно много баллов.

1:22 — 48 баллов по C

Я решил подумать ещё над следующей подзадачей. Для неё придумал совсем другое, отдельное решение и в 1:22 получил ещё 13 баллов — итого 48 по C. Но дальше я не очень понимал, как объединять эти две идеи. Более того, ретроспективно могу сказать, что эти идеи и не объединялись.

Поэтому я ещё немножечко подумал, решил оставить 48 баллов в C-шке и пойти открыть последнюю задачу с нулём — задачу D.

Задача D. Хорошие раскраски – 8

Уже по названию, да и по условию, задача изначально выглядела как какой-то лютый ужас и вообще невозможность нормально её порешать. Если вы не знали, задача «Хорошие раскраски» известна своим замечательным авторским решением и народной версией. Кто писал региональный этап в 2021 году, тот вспомнит.

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

1:33 — 6 баллов по D

В 1:33 я получил 6 баллов за подзадачу, опять же с наивным решением, и тут решил немного отклониться от стратегии. Я понимал, что, скорее всего, задача D самую малость недорешана по сравнению с другими задачами, но она мне и меньше всех нравилась, поэтому решил вернуться к ней чуть позже. Сейчас были более простые баллы, которые стоило получать.

Поэтому я переключился обратно на задачу B.

Возвращение к B

После этого я решил вернуться к задаче B и действительно довольно глубоко подумать — на самом деле чуть ли не впервые за тур. К этому моменту у меня уже было 100 + 85 + 48 + 6 = 239 баллов.

И вот здесь хорошо видно, насколько много на Всероссе можно набрать почти наивными решениями. Из этих 239 баллов единственной задачей, которую мне пришлось действительно закрывать полноценным решением, была A — самая простая задача тура. В B я пока оставил последние 15 баллов, в C набирал баллы на отдельных частичных решениях, а в D просто написал самый наивный вариант. То есть больше дневного ориентира на призёра у меня уже было почти на одних «халявках». Это довольно хорошо иллюстрирует мысль из первой части: на Всероссе важно не обязательно решать задачи целиком, а вовремя забирать доступные баллы.

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

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

1:57 — ещё 10 баллов по B

В 1:57 я получил ещё 10 баллов.

2:03 — 100 баллов по B

А в 2:03 — ещё +5 и сотку за задачу B, оставив две задачи позади. Это на самом деле меня очень сильно порадовало: в этот раз у меня оставалось целых три часа, чтобы порешать какие-то существенные подзадачи в C и D.

Возвращение к C

Итак, я возвращаюсь к задаче C, в которой заметил, что есть ещё одна подзадача с маленькими ограничениями, но только на одну из переменных.

2:28 — ещё 11 баллов по C

Уже через не очень большое время, в 2:28, я получил ещё 11 баллов за пятую подзадачу и, в общем-то, решил не уходить из этой задачи.

На следующую подзадачу я потратил действительно много времени. Самое сложное было забыть все предыдущие решения и придумать что-то совсем новое. Главной подсказкой для меня стали ограничения: в этой подзадаче k было не больше 16, а в следующей — уже 19. Я стал думать не от конструкции, а от асимптотики: что можно позволить себе при k = 16 такого, что уже не проходит при k = 19?

Если при k = 19 естественным ориентиром выглядит O(2^k), то при k = 16 уже можно попробовать O(3^k). Из специфики задачи я понял, что 3^k здесь получается через перебор подмасок каждой маски. И уже от этой идеи построил целиком новую конструкцию и получил свои заслуженные баллы. Без подсказки в виде этих двух ограничений я, скорее всего, вообще не стал бы думать в эту сторону — идея была совсем неочевидной.

3:51 — ещё 18 баллов по C

В итоге, получив ещё 18 баллов — суммарно 77 по C, — я понял, что по этой задаче уже выжал победительский максимум. Дальше стараться в неё не было смысла, особенно учитывая, что у меня грустила задача D с 6 баллами, а до конца оставался всего час.

Я очень сильно проседал в этой задаче. Несмотря на то, что она мне не нравилась, мне стоило к ней вернуться и подумать.

Возвращение к D

Ну и в этой задаче я опять же делал самые логичные и интересные действия и выбрал две подзадачи со специальными условиями — это подзадачи 2 и 3. Над ними пришлось, конечно, какое-то время подумать.

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

4:28 — ещё 19 баллов по D

К 4:28 я закрыл обе эти подзадачи и получил за них суммарно ещё 19 баллов. А вот после этого структурно простых подзадач уже не осталось.

4:58 — посылка с перебором

В подгруппах 4, 5 и 6 были просто маленькие ограничения на входные данные, поэтому дальше нужно было достаточно аккуратно писать полный перебор. Руки уже немного тряслись. Конечно же, отправлял всё без локального тестирования, на веру, и посылка в 4:58 получила 0 баллов. Оставалась буквально минута.

4:59 — Accepted

За эту минуту я успел исправить ошибку и отправить ещё одну посылку. В 4:59 она всё-таки получила Accepted на весь перебор. В последние секундочки я был очень рад: решение получилось, я успел его заслать и залутал все свои баллы за задачу D.

Итого по D — 34 балла.

Что я бы вынес из этого тура

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

На этом туре к 1:33 у меня уже было 239 баллов — 100 + 85 + 48 + 6. И почти всё это я получил без попыток сразу придумать полное решение сложных задач: в B оставил последние 15 баллов на потом, в C собирал отдельные подзадачи, а в D начал с самого наивного решения. 239 баллов — это уже больше дневного ориентира на призёра.

Итоги эксперимента

Забавно, что ровно те же 606 баллов набрал участник с фамилией Зайцев — только распределение по задачам у нас получилось совсем разным.

Результат получился очень высоким. Победителями в тот год стали около сорока участников, так что это был не пограничный диплом, а действительно сильный результат внутри победительской зоны.

Особенно меня радует, как именно прошёл второй день. В этот раз я не потерял много времени в начале тура и смог позволить себе действительно долго думать над C. Те самые последние 18 баллов вполне могли бы не появиться — и, как мне кажется, появились именно потому, что второй день я провёл лучше.

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

Помимо таких экспериментов со Всероссом, сейчас я готовлюсь к финалу ICPC и публикую свои тренировки, результаты и мысли о спортивном программировании в Telegram-канале Machine Solution. Если вам интересно наблюдать за подготовкой — подписывайтесь.

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