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

Привет, Хабр! На связи финалист ICPC и гроссмейстер codeforces MachineSolution. В прошлой своей статье я писал о том, как подготовиться к соревнованию. Но что делать, если время подготовки прошло, как писать саму олимпиаду? “Просто бери и решай задачи” - скажет кто-то, но будет прав лишь отчасти. У некоторых соревнований есть свои особенности и, как следствие, особые стратегии написания. И заключительный этап всероссийской олимпиады школьников по информатике не лишён своих отличительных черт.

Всероссийская олимпиада школьников по праву считается мерилом олимпиадных способностей школьников и, хотя взять диплом даже регионального этапа ВсОШ дано не каждому, всероссом называют именно заключительный этап и готовятся к нему. Мало кто из сильных олимпиадников не хочет “взять всеросс” - то есть выиграть диплом призёра заключительного этапа. Помимо поступления в любой ВУЗ без экзаменов он сам по себе является ценной наградой и подтверждением своих способностей и признания результата долгих тренировок. Более того, не так много людей стремятся к диплому победителя - настолько сложно и почётно в этой олимпиаде стать хотя бы призёром! Заветные дипломы по информатике каждый год получают всего 200-300 человек из миллионов школьников. Моя история с этой олимпиадой не самая сказочная - в свои школьные годы я пожертвовал подготовкой к информатике ради подготовки к математике. Да, в итоге я занял 7 место на финале математики и почти стал победителем, но на информатике выступил, мягко говоря, ужасно - даже не близко к призёрам. Поэтому мне стало интересно написать зеркало ВсОШ по информатике за 2026 год, чтобы проверить, как сильно я вырос в олимпиадах и на что способен.

В этой статье я поделюсь своими советами - к чему готовиться на этом всероссе, какой стратегии придерживаться в зависимости от целей, почему на всероссе не нужно решать задачи и с чем можно встретиться на туре. А также разберу сам тур финала 2026 года и расскажу, что мне самому удалось решить.

Стратегия

Главное, что определяет стратегию на всероссе – это система оценки задач. Дело в том, что каждое задание оценивается в баллах от 0 до 100, а не “решил / не решил”. Каждая задача состоит из подзадач с разными ограничениями - как на размер входных данных, так и более сложные и зачастую интересные условия, и за каждую подзадачу баллы начисляются по-отдельности. Тут-то и начинается парадокс - на этой олимпиаде нужно не решать задачи, а набирать баллы. Так, получить за каждую задачу по 70 баллов, но так и не решить до конца ни одну выгоднее, чем решить первую и вторую на 100, а за оставшиеся получить 0. На смене ко всероссу в Сириусе нас учили этой идее, порой даже радикально - на тренировочных контестах тех, кто получил хотя бы за одну задачу 0 баллов, даже если суммарно результат вышел хороший, не награждали. Среди таких “счастливчиков” был и автор, хотя я знал про это правило и пытался получить баллы по последней задаче, но ничего не вышло. В общем, запомните правило - нужно набирать баллы в каждой задаче.

Но вот вопрос: а сколько баллов нужно набирать в каждой из задач? Наверняка баллы в задаче D набираются тяжелее, чем в задаче A, потому что она сложнее? И у меня есть ответ на этот вопрос. Я проанализировал Баллы призёра и победителя всеросса по информатике с 2011 года - когда олимпиада стала состоять из 8 задач - и увидел, что из 16 лет проведения всего 3 раза балл призёра был выше 450, а балл победителя выше 590, поэтому я предлагаю ориентироваться на эти баллы. Да, вообще-то если Вы наберёте их, это ещё не гарантирует диплом. Да и гарантия - вещь очень редкая. Думаю, что действительно гарантировать диплом Вы можете только написав на 800 баллов. Я хочу сказать, что я описываю ориентиры, а не чёткие правила, верные в 100% случаев и в конечном счёте важно то, насколько лучше вы выступили относительно остальных участников, а не сколько баллов в абсолютном выражении набрали

Тем не менее, полезно держать в голове, что чтобы получить диплом призёра, нужно набрать примерно 450 баллов из 800, то есть по 225 в каждый из дней. Самый сбалансированный способ набрать такие баллы из 4 задач такой: 100 + 70 + 40 + 15. То есть первую задачу нам нужно решать полностью, за вторую получать примерно 70, за третью 40 и за четвёртую 15. Например, если у Вас в какой-то момент написания баллы по задачам выглядят как 100 + 50 + 40 + 20, то Вам следует обратить внимание на задачу B и подумать над ней подольше - скорее всего там скрываются самые простые баллы. Или, если Вы набрали всего 5 баллов за задачу D - потратьте на неё ещё время и поищите простые подзадачи

Если же Вы приехали на всеросс за дипломом победителя - придётся постараться сильнее и рекомендуемая разбалловка следующая: 100 + 100 + 60 + 35. Здесь нам уже нужно “дорешать” вторую задачу и получить более существенные продвижения по двум другим. Но стоит помнить, что в таком случае результат всё сильнее зависит от результата других участников, специфики и сложности задач на туре, чем от “средних" значений, потому что победителей очень мало. Тем не менее, такие ориентиры помогут заметить, в какой задаче прогресс хуже относительно других. А если по всем задачам он приблизительно одинаковый - выбирайте задачу, которая вам больше нравится - возможно, это Ваше конкурентное преимущество. Да и решать её будет приятнее

Ход первого дня

Условия задач вы можете найти по ссылке.

0:00 — Задача A. Распределённые системы

В этой задаче я даже не читал какие есть подзадачи, так как закрывать её желательно на 100 баллов. К счастью, задача состоит из одной идеи — как только я понял, что задача разбивается на независимые циклы — сразу же родилось решение за линию.

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

В 0:12 я получил 100 баллов по задаче с первой попытки и заметно обрадовался, так как тур начинался хорошо.

0:12 — Задача B. Расследование в Темерии

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

В 0:12 я прочитал задачу и стал думать. Я искал решение через квадратичное DP, даже не понимая очевидного — оно не может получить больше 43 баллов.

0:37 — переключение на C

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

Задача C. Скобки и деревья

А в этой задаче всё пошло штатно. Более того, я начал именно с прочтения условий на подзадачи, а не с глобальных ограничений задачи, так как 100 я тут вряд ли получил бы. Хотя один сюрприз всё же был — за задачу я получил больше баллов, чем должен был!

0:57–1:00 — первые 20 баллов по C

Первые свои баллы по этой задаче я получил в 0:57, а в 1:00 у меня их уже было 20 — я заслал две халявные подзадачи — эти 20 баллов были даже проще, чем в задаче B.

1:00 — возвращение к B

Тут, чтобы ситуация не выглядела безнадёжной — я написал кубическую DP-шку и получил 9 баллов в 1:11. Но этого было ой как мало! Я понимал, что это не решение задачи, но этим действием я помог себе сдвинуться с мёртвой точки.

1:55 — 20 баллов по B

Только в 1:55 у меня стало 20 баллов — я закрыл одну подзадачу и тут меня осенило: просто мне нельзя думать над динамикой, она не принесёт мне желаемых баллов.

Поэтому я задался вопросом: а как мне найти ответ для всех k сразу, при этом не считая такие же ответы для всех поддеревьев? Ответ прост — жадник!

2:17 — 67 баллов по B

Это меня так взбодрило, что уже в 2:17 у меня было 67 баллов за неоптимально написанный жадник. Но самое главное — он давал верный ответ. Я почувствовал облегчение и принялся его оптимизировать.

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

В итоге в 2:38 у меня было 100 баллов за эту задачу. Но как много времени прошло и как мало баллов было в С и D!!

После — Задача D. Спортивная тренировка

В этот момент моя разбалловка выглядела так: 100 + 100 + 20 + 0. Единственной задачей без единого балла оставалась D, поэтому выбор был очевиден.

Задача была про изменение входных данных запросами и пересчитывание ответа. Я сразу стал примеряться — как быстро я смогу решить задачу для фиксированного набора данных и как много получу баллов, если буду просто считать ответ после каждого изменения. Оказалось, аж 21 балл!

3:20 — 21 балл по D

Этим я и занялся и в 3:20 уже этот 21 балл лежал у меня в кармане.

Дальше я смотрел на подзадачи с нестандартным ограничением — не «n до тысячи», а «Школьники добавляются в порядке возрастания номеров» — обычно по ним можно быстрее придумать решение. Я даже рассматривал это как полностью отдельную задачу.

3:27 — 31 балл по D

Так и вышло — ещё 7 минут и в 3:27 у меня уже был 31 балл по задаче D.

«Солидно», — подумал я и решил почти до конца контеста вернуться к C. По D программа минимум уже была выполнена, а вот в C у меня оставалось всего 20 баллов вместо желаемых 40.

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

Эта задача мне понравилась, у меня уже были какие-то баллы по D и я решил сосредоточиться на третьей подзадаче С — да, она давала сама по себе 6 баллов, но её решение приближало меня к баллам и в других подзадачах — я просто чувствовал, что для решения ключевым случаем является n=2.

4:26 — ещё 6 баллов по C

Я долго думал, но мои усилия наградились — в 4:26 я получил свои 6 баллов за подзадачу и большое продвижение в задаче в целом и стал писать общее решение для следующей подзадачи.

Она была организована хитро и в ней самой можно было получить частичный балл.

4:48 — неожиданные 34 балла

В 4:48 я отправил решение, ожидая увидеть +5 или в крайнем случае +15, но тут случилось невозможное — я увидел какие-то неправильные баллы — их было ну слишком много!

Я пошёл смотреть разбалловку по подзадачам и очень удивился. За 4-ю подзадачу их было аж 34!! То есть полная подзадача.

Впоследствии я так и не нашёл логичного тому объяснения — просто в задаче были слабые тесты. Моё решение не должно было получать больше +15.

Зато, моё настроение резко улучшилось — можно было уходить от этой задачи и писать полный перебор в задачу D, чтобы откусить 4 балла.

4:48 — возвращение к D

12 минут до конца и вот я, дрожащими ручками пишу полный перебор по подмаскам — я уже полностью включился в гонку, хоть всерос и был виртуален — эмоции всё же были реальны. 12 минут — это совсем немного. Я понимал, что могу банально не успеть набрать код, каким бы простым ни было решение.

Последние посылки

И пришло время делать посылки: 4:57 — WA, ранил! 4:58 — WA, ранил! сразу дублем — 4:59 и 4:59, последний шанс… и… +4 балла — подзадача зашла!

Да, может радоваться 4 баллам в виртуальном соревновании глупо, но я радовался тому, что получилось написать и заслать.

Оценка результатов тура

Изначально моей целью было понять, тяну ли я сейчас на диплом призёра. Когда я закончил тур, ощущения были хорошие: 295 баллов — это солидный результат для первого дня. Но любопытство взяло верх, и я полез сравнивать его с реальными результатами участников.

Оказалось, что с таким результатом я бы занимал 8-е место после первого дня и вполне мог бороться уже за диплом победителя.

Именно в этот момент мои цели резко изменились. Если до начала тура я ориентировался на условные 100 + 70 + 40 + 15, то теперь стало понятно, что во второй день придётся выступать намного агрессивнее и бороться уже не за призёра, а за победителя.

И, кстати, получилось забавное совпадение: я в точности набрал именно те 295 баллов, которые сам же приводил в качестве ориентира в разделе про стратегию. Конечно, это скорее следствие удачного распределения подзадач, чем каких-то невероятных способностей к предсказаниям, но совпадение получилось приятным.

Заключение

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

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

А если вы сами готовитесь к олимпиадам или просто хотите заглянуть за кулисы подготовки к финалу ICPC, подписывайтесь на мой Telegram-канал. Там я почти каждый день рассказываю о своих тренировках, разбираю интересные задачи и делюсь мыслями, которые обычно остаются за кадром соревнований.