Мы тут с Таней сделали гайд по тому, как хорошо выступить на региональном этапе всероссийской олимпиады школьников по информатике. Учитывая, что до региона осталось совсем немного времени, рекомендуем прочитать и почерпнуть что-то новое. Если вы и так готовы к региону, то все равно прочитайте, потому что почти все эти же советы применимы и к заключительному этапу, и к Открытой олимпиаде по программированию.
Содержание
- Для кого пост?
- О чем пост?
- Что стоит знать из алгоритмов?
- Какие цели ставить перед туром?
- Что делать на туре?
- Что делать перед туром?
- Что делать между турами?
- Заключение
Блин блинский, до региона неделя
Для кого пост?
Этот текст актуален, если вы в подвешенном состоянии — с одной стороны вы знаете, что ваших знаний точно хватает, чтобы выйти на всерос, но с другой стороны вы не уверены в том, что это произойдет. То есть, я представляю себе целевую аудиторию как-то так:
- Не был на всеросе (или был, но с очень нерезультативным выступлением, <= 400 баллов
- Учился где-нибудь в параллели уровня B ЛКШ
- Рейтинг на codeforces порядка 1600-1900 (в зависимости от того, насколько активно зависал там)
- Пытался ботать как черт последние несколько месяцев
- Прямо сейчас в состоянии “ААААААА”
О чем пост?
Если вы подходите под описание, то я могу сказать следующее — начиная с этого момента ваше выступление на регионе практически не зависит от того, что вы заботаете за оставшуюся неделю. Поботать надо, но нет абсолютно никакого смысла в том, чтобы за неделю попытаться выучить все то, что не удалось за предыдущее время. Зато есть возможность подготовиться альтернативными методами: порешать старые регионы, определить свою стратегию на тур, подорешивать с таймером. Вот про это и пойдет речь. Скажу сразу, что это все следует только из моего личного опыта (очень хорошего!). В общем-то, этот текст сделан так, чтобы я мог его показать самому себе перед регионом 17-18 года (моим первым регионом).
Что стоит знать из алгоритмов?
Вообще я не разделяю всеобщую панику насчет того, что надо выучить стотыщ сложных алгоритмов, а иначе на туре все будет плохо. Что, имхо, стоит знать перед туром региона:
- Бинпоиск. Вообще не факт, что он пригодится, но зато вы его гарантированно знаете.
- STL и остальные прелести плюсов. Если вы пишете не на C++, то мне вас искренне жаль (это не повод переучиваться прямо сейчас, но повод переучиваться потом. Прямо сейчас лучше задуматься о том, что вы можете сделать со своим ЯП). Если вы пишете на C++, то сделайте так, чтобы точно знать все основные штуки из STL. Если вы нарешивали много задач, то вы и так уже все должны уметь, но просто проверьте, что знаете, как сделать кастомный компаратор, отключить синхронизацию ввода или настроить себе freopen’ы.
- Динамика. В том или ином виде пригодится обязательно.
- Basic графы a.k.a бфс, дфс, дейкстра, лца.
- Basic структуры данных. Зубрить Фенвика не обязательно. Знать ДО и ДД стоит.
- Строки. Если не знаете ничего, то это все еще не страшно. Если умеете работать с хэшами, то все уже хорошо.
- Геометрия. Если вы не трогаете геометрию из-за неконтролируемой ненависти, то этот пункт не для вас. Остальным могу сказать, что стоит уметь в геометрические примитивы, скалярное и векторное произведение. Это нужно в большей степени для того, чтобы не получить ноль по задаче на геометрию. А если вы умеете построить выпуклую оболочку, то можно спокойно выдохнуть.
Можно заметить, что тут нет ничего такого, что выпускник параллели B ЛКШ назвал бы сложной темой. Rocket science, во всяком случае для выхода на заключительный этап, не требуется. Кто-то скажет, что этого недостаточно, что когда-то была задача на поиск мостов, а год назад была задача на потоки. Это правда, но тут есть две важные вещи:
Все алгоритмы все равно не выучишь.
Если вы не знаете алгоритм, который хотят авторы конкретной задачи, вы все еще можете получить относительно высокий балл за нее.
Если вы не знаете что-то из тем выше, то не надо паниковать. Во-первых, на эту тему могут и не дать задач. Во-вторых, вы все еще можете получить хороший балл, если знаете ~60% из моего списка выше. В-третьих, если у вас действительно недостаток знаний, то вам на этом региональном этапе, простите, не светит. Зато он является хорошей тренировкой перед другими олимпиадами (и регионом следующего года, кстати!). Поэтому смиритесь с тем, что какие-то задачи вам будут не по зубам и сделайте все то, что вам сейчас по силам. Это вам очень поможет. Пожалуйста, не надо пропускать регион, потому что ботаете к следующему региону!
Этот мужик умный, будьте как он
Какие цели ставить перед туром?
Я хочу сказать одну вещь, которую никогда не говорят, но которая мне очень помогла в свое время:
“Вам не нужно прыгать выше головы или решить все задачи. Вам нужно пройти на всерос.” (с)
Школьные олимпиады отличаются своим форматом. Вы решаете задачи не стандартным ACM-способом (решил/не решил), а в несколько заходов, и необязательно на полный балл. Какие тезисы будут вашими бро:
- Мне надо оказаться в топ-Х школьников страны, чтобы отобраться.
- Участники ранжируются по баллам.
- Мне нужно набрать балл, достаточный для того, чтобы оказаться в топ-Х школьников.
Максимальный балл не нужен. Гораздо важнее не облажаться. Поэтому максимизируйте свой минимальный балл по окончанию тура. Иначе говоря, если тур для вас закончится прямо сейчас, вы все равно уйдете, не оглядываясь на взрыв.
Что делать во время тура?
Баллы, баллы, баллы. Забейте на задачи, набирайте баллы.
Отказывайтесь от сложных баллов в пользу простых. Сделать 40 -> 100 в С скорее всего вам будет гораздо сложнее, чем 0 -> 20 в D. Если в такой ситуации сесть за С, то есть два исхода:
- Вы закопались в дебаге, начали нервничать, и так и просидели весь тур. +0 баллов.
- Вы закопались в дебаге, начали нервничать, и так и просидели почти весь тур. Вам повезло, и вы сдаете задачу в последние 5 минут. +60 баллов.
Я не говорю про ситуации, когда вы точно знаете, что решение верное, а писать его десять минут. Тогда пишите на здоровье. Но если бы персонаж из примера получил +20 по D, то он бы точно не ушел с +0. Более того, он и +60 скорее всего бы тоже успел.
Как написать задачу быстрее всего?
Тестируйте, если умеете. Если вы умеете в стресс-тесты, то не бойтесь их применять. Стрессы пишутся 10 минут, и моментально находят баги в вашем решении на 100 баллов до того момента, пока вы не исправите все, что только можно. Только напишите сначала тупняк на 20 баллов, и готово. [Прим. автора — если вдруг стрессы не помогают, то проверьте, что у вас нормально работает на макстестах — не переполняется int32, достаточный maxn, и остальные сопутствующие штуки]. Однажды я лично сдал задачу, решения которой до сих пор не понял до конца. Там надо было сделать какую-то стремную рекурсивную функцию, и я просто со стрессами перебирал ±1 в разных местах до тех пор, пока решение не зашло на ОК.
В любой критической ситуации забейте.
Если не решается какая-то задача, то переключитесь на остальные. Серьезно, проходные баллы по итогам региона обычно таковы, что если вы набрали 50 по А, то вы все еще абсолютно легко можете пройти, если хорошо порешаете остальные задачи. Иначе говоря, пусть ваша А сдана на 50 баллов, у вас не получается ее быстро дорешать. Если вы упретесь в нее (и будете перебирать формулы до посинения), то потратите время, нервы, и реально можете слиться, потому что вам не хватит времени на что-то еще. Не пошло — ну и ладно, что-то другое решится. Получив все баллы, для которых не нужно было делать ничего идейного, вы скорее всего обеспечите себе нормальный результат. И уже после этого можно хвататься за всякие сложные задачи, чтобы за 5 минут до конца тура сдать их на +много баллов.
Не уверен — не берись.
После прочтения задач иногда сразу хочется написать полное решение, не распыляясь на подгруппы. Пример: вы прочитали задачу, там нужно написать спуск по неявному декартовому дереву. Если вы пишете ДД за 10 минут, то пишите себе полное решение на здоровье. Но, если нет, то напишите тупняк на подгруппы. Почему это бывает полезно:
- Ваше решение — лажа. Не хочется час писать код, чтобы потом с этим столкнуться.
- Вы не поняли условие задачи.
- Вы можете тестировать решение на 100 своим тупняком.
- Вы можете не успеть написать решение на 100, но уйдете не с пустыми руками.
Можно искусственно ухудшать свое решение — сначала вместо ДД написать обычный массив. Мотивация такая же, и это реально помогает. Собирать по кусочкам проще, чем сделать с нуля.
Не надо думать о вашем результате.
Помните, что вы конкурируете не с составителями задач, а с такими же школьниками, как и вы сами. То есть, если в задачу С дадут гроб, то С решат не 150 человек, как обычно, а 20. И если вы не попадете в эти 20, то ничего страшного. Узнаете вы это только после тура. Поэтому возможно, что если у вас во время тура мало баллов, то мало баллов не только у вас, и на самом деле все норм. Не делайте выводов до конца тура.
Обеспечьте себе максимальный комфорт на туре.
Комфортно вам не будет, в конце-концов олимпиада — это в любом случае стресс. Но вы можете сделать так, чтобы ваш мозг не занесло. Регулярно прерывайтесь на попить-поесть (возьмите еду и воду с собой) [Прим. автора — аккуратнее с газировкой, потому что она может полезть из горлышка и залить все вокруг, у меня такое случалось. откройте бутылку заранее, пока тур не начался]. Не бойтесь потерять время на выход в туалет. Умойтесь. Все средства, что перезагружают ваш мозг, хороши. Если вы теряете контроль и уходите в нервозность, то просто посидите за рабочим местом, втыкая в потолок. Если вы до тура можете болтать с соседом и с чего-нибудь смеяться, то это тоже хорошо расслабляет. Некоторые контесты я писал с плюшевым розовым дельфином.
Смотрите, какой милашка
Следите за временем.
Это тупой совет, которому не следует никто. Если вы не смотрите на часы регулярно, то в один момент вы сядете за задачу, а очнетесь на трехсотой минуте. Поэтому следите за вашим временем и прикидывайте, сколько у вас уйдет на то или иное действие. 5 часов — это много, если нормально распределить силы. Помните, что под конец тура у вас будет больше разных идей по задачам, но меньше сил, чтобы это написать.
Что делать до тура?
- Все то, что вы могли вложить в свою голову до региона, вы уже вложили. За неделю вы не подготовитесь с нуля.
- Посмотрите старые туры регионов. Концентрируйте свое внимание не на задачах, а на подгруппах. Попытайтесь решить несколько задач А на 100 баллов за минимальное время. Сделайте то же самое с задачей D на 20 баллов (ну или на максимальное число очевидных для вас баллов). И то, и то вам почти гарантированно понадобится.
- Отрешайте какой-нибудь архивный тур в режиме олимпиады. Вы лучше поймете, что и как стоит делать во время контеста.
- Составьте себе стратегию на тур. Запишите ее (на листок бумаги или в заметки). Примерно прикиньте, как вы хотите раскидать силы. Посчитайте тайминги. Каждый делает это индивидуально, но общие рекомендации — как можно раньше получить ненулевые баллы по всем задачам, не залипать в одну задачу надолго, и оставить сколько-то времени про запас. Гарантирую, что этот план не поможет на самом регионе, потому что все пойдет по-другому, но вы будете готовы принимать страегические решения на ходу. Вот, например, моя стратегия на заключительный этап 2017-2018 года:
“0.00-0.10 - я настраиваю среду
0.10-0.20 - я читаю условия
0.20-1.20 - я написал банальные группы
1.20-1.30 - пишу стресс
1.30 - 3.00 - сдаю А и Б на фулл
3.00 - 4.00 - набираю баллы по С и Д
4.00-5.00 - играю в тетрис, время для подстраховки, добить сложные подгруппы“
• За денек перестаньте судорожно ботать. Лучше погуляйте или продуктивно отдохните (скроллить ленту не считается!). • Проверьте, что вы помните, как работать в вашей IDE, знаете шаблонные строчки, и все такое. Пройдитесь по регламенту проведения. • На пробном туре проверьте, что вы можете написать работоспособную программу и стресс-тесты. По возможности накидайте себе шаблонов.
Что делать между турами?
- Перезагрузить мозг, потому что туры независимые. Если вы написали первый тур плохо, то у вас есть все шансы на втором. Точно так же можно слить все свое преимущество. Поэтому просто забейте.
- Проанализировать первый тур с точки зрения задач. Посмотрите, на сколько вы могли написать, на сколько написали, и каких тем вам не хватило. На втором туре это не поможет, но поможет в дальнейшем.
- Проанализировать первый тур с точки зрения своих и чужих баллов. Вы увидите, что некоторые знакомые написали лучше, чем вы, а некоторые хуже. Скорее всего, вы увидите, что баллы у всех примерно одинаковые, и ваш балл тоже в стандартном диапазоне. После этого можно расслабиться и готовиться ко второму туру.
- Проанализировать первый тур с точки зрения стратегии и таймингов. Мне нравится идея письменного разбора, хотя ее и мало кто придерживается. Суть такая — вы открываете список своих посылок, и смотрите по ним, в какой момент времени решалась та или иная задача. Делаете для себя письменные выводы. Получится такой лог-формат, вот моя выдержка с прошлого региона:
“0.35.43 - A 100, сдал формулу
0.45.49 - B 61, сдал подгруппу на положительные числа и преподсчет для отрицательных
0.56.57 - B 100, очень долго, но написал k -> abs(k). До этого зачем-то пытался упихнуть преподсчет”
Это реально помогает, потому что вы можете увидеть, где вы серьезнее всего облажались. Возможно, ваша проблема окажется в том, что вы писали задачу А 35 минут, а возможно в том, что вы дебажили задачу С два с половиной часа. А может быть, что проблем вообще нет, и у вас все хорошо.
Когда регион закончится, посмотрите на свои окончательные баллы на фоне знакомых. Если вы находитесь на границе, то по умолчанию считайте, что вам надо готовиться к заключительному этапу. Если вы в итоге не отберетесь, то вы зато будете готовы к открытой олимпиаде.
Заключение
Помните, что олимпиады должны приносить вам удовольствие от решения задач и спортивного азарта. Поэтому придите на контест, получите свой максимальный балл, и отберитесь на всерос, чтобы повторить свой успех.
Всем удачи!