Всем доброго времени суток! На этот пост меня вдохновил Wind_Eagle своим постом.

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

Для начала подведу итоги челленджа. Он оказался скорее неуспешным, чем успешным. Единственное, что я получил от него — опыт, который будет полезен в будущем. Итак, итоги:

• Взять диплом на республике. Не выполнил, остался без диплома. Нарешал очень плохо, наконец понял, что главная проблема не столько даже лежит в программировании, сколько в психологии. Заметил очень нехорошую особенность: пришёл как на первый, так и на второй тур, все 5 часов не мог сосредоточиться, чего-то боялся (сам не знаю, чего). Из-за этого я фактически не думал, а скорее просто выписывал на листочке что-то и пытался просто реализовать то, что всё-таки смог заметить. Получил 302.65 баллов, когда на диплом надо было 385. Эта проблема была всегда у меня, но я как-то не обращал на неё внимания, просто потому что считал её несерьёзной. Также ещё одна из возможных причин кроется в названии поста, далее поясню, что я имею под этим ввиду.

• Выиграть олимпиаду первого уровня. Ещё нет результатов по олимпиаде ИТМО, но это последний шанс. Ближе всего я был к диплому на высшей пробе (опять же по глупости получил по B задаче 19 вместо 100, потому что использовал ДО на максимум вместо префиксных максимумов) и Технокубке, на котором просто не успел заслать D задачу.

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

Теперь к основной части. Так почему же вам скорее не помогут сложные темы?

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

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

Теперь перейдём к изучению тем. Для школьных олимпиад (по карйней мере в Беларуси) не требуется знания каких-то сложных тем, как потоки, декартово дерево, Segment Tree Beats (Анимешное ДО). Ошибкой стало их изучение, тем более за полтора месяца до олимпиады. Далее привожу темы, которых, по моему мнению, достаточно, чтобы взять призёра олимпиады первого уровня перечня РСОШ или какой-то олимпиады уровня республиканской в Беларуси:

• первое и главное: умение решать "в лоб"

• умение писать задачи на реализацию (все таски которые вы знаете как решать, но вам лень реализовывать)

• бинарный поиск, в том числе по ответу

• тернарный поиск

• префиксные суммы / минимумы / максимумы

• встроенные в stl структуры данных: map / set / multiset

• встроенные в g++ структуры данных: ordered set / ordered multiset, их особенности и баги

• простая теория чисел (алгоритм Евклида, решение линейных диофантовых уравнений, операции по модулю, решето Эратосфена, в том числе умение находить простые делители для всех чисел до $$$n$$$ за $$$O(n \log \log{n})$$$)

• простая комбинаторика: сочетания, перестановки, "количество способов"

• методы решения задачи в оффлайн: алгоритм Мо, сканирующая прямая

• оптимизации при помощи bitset

• дерево отрезков, в том числе с отложенными операциями и на указателях

• разреженная таблица

• система непересекающихся множеств

• знание стандартных жадных алгоритмов, умение "поподбирать компаратор"

• <метод отжига для решения задач с открытыми тестами>

• основы теории игр

• знание графов/деревьев и основных алгоритмов по ним: BFS, DFS, Дейкстра, алгоритм Прима, LCA

• строки: полиномиальное хеширование, <префикс-функция, Манакер>

• ну и конечно, знание и понимание стандартных приёмов динамического программирования

• <очередь с поддержкой минимума>

<> я пометил опциональность

UPD: По поводу психологии на туре очень интересно было почитать статью и посмотреть лекцию тут.