Примерно так я буду выглядеть, если возьму победа МОШа

Я обязательно выпущу пост…

Иван 9kin сделал чат для ботания МОШа (главное - он кидает ссылки на ЯК, где можно с нормальной системой прорешать прошлые года): https://t.iss.one/+Sref_hFAvfQ4MmYy

Вот ссылки на финалы:
2021
https://contest.yandex.ru/contest/36691
2020
https://contest.yandex.ru/contest/36846
2019
https://contest.yandex.ru/contest/17575
2018
https://contest.yandex.ru/contest/17576
2017
https://contest.yandex.ru/contest/17577

Но в чат тоже можно вступить, там люди возможно будут делится своими идеями и оптимизациями

Обновил: добавил за 2020 год

Сегодня порешал финал МОШа за 2021 год. В целом задачи прикольные, но я уже устал и 2ю половину времени не думал особо. Решал всего около 3 часов. Набрал 447 баллов (не дотягивает до победа), но там еще на питоне задача крутится, может зашлю чуть позже
А) простая реализация (100 баллов)
B) Представляем словарь слов в виде графа, а связи между ними как ребра в графе, считаем компоненты связности и их размеры (100 баллов)
C) Достаточно понять что размер поддерева вершины равен сумме размеров поддеревьев её детей минус 1. Тогда можно жадно перебирать детей (99 баллов)
D) 1й жадник - ответ это все уникальные цифры. Идея для оптимизации - пытаемся найти 2 идущих подряд числа. И если они встречаются только в такой "связке", то их можно заменить на эту связку. (69 баллов)
Е) Написал кукарек (причем нерабочий) (20 баллов)
F) Прикольная задача, но переполнение это больно(. Сумма легко раскладывается на 2 части, одна из которых монотонно растет, а другая имеет вид параболы вниз. Но суммарно оно в большинстве случаев просто возрастает, то есть функция монотонна. Значит мы можем бинарным поиском искать оптимальное значение. далее осталось быстро считать 2ю часть суммы. Для этого посортим, посчитаем префсуммы и будем каждый раз бинарить первое число, меньшее текущего. Сложность O(nlogn + qlog^2n). Можно еще добавить разделяйку по запросам, тогда будет просто O((n+q)logn), но мне лень (плюсы считают чуть дольше секунды, питон почему то до сих пор считает), Ну и самая главная проблема тут - это конечно переполнение на больших числах, которых тут много. (поэтому я и решил переписать на питон). (Пока 30/30 баллов на маленьких числах на питоне и 29/70 на больших числах на плюсах)
Впринципе, если бы это был реальный финал, то я просто заслал бы лажу какую нибудь в ласт задачу и стал бы победом, так что думаю норм порешал.

Что я использовал из алгоритмов и подобного:
1) дфс
2) рандом
3) бинпоиск

Завтра дорешаю E, может допишу разделяйку в F, подумаю над D и хотя бы прочитаю G

Обнаружил у себя баги в F, больше 60/100 к сожалению мое решение не набирает(
Прочитал G. Сначала подумал что достаточно тупо посчитать компоненты связности, потом понял что задача чуть интереснее. Сначала написал чистую генетику - получил 30/30 + 1.2/70 🤡. Далее придумал простой жадник - каждый раз итеративно берем вершину с максимальной степенью, затем все её ребра удаляем и повторяем. Это набирало 20/30 + 36/70. Далее я прикрутил это как жадную инициализацию к генетике и получил 30/30 + 40/70, вроде не так плохо. Над Ешкой сегодня думал, но что то не придумал, по D вроде и так не самое плохое решение в итоге.

Резюмирую: надо не думать, а писать. Часть задач решаются очень простой реализацией и дают халявные баллы. Часть задач уже интереснее, их можно либо решать алгоритмически если очень хорошо подумать, либо не думать и написать жадник на довольно большой балл. К особо сложным задачам можно прикрутить эвристики (например D) или генетику/отжиг (например G).

Далее прорешаю МОШ за 2020 и 2019 года. После продумаю тактику как действовать на финале. На данный момент она простая - если придумал решение, пишу и засылаю, иначе пишу бред, засылаю и перехожу к следующей задаче, если подробнее, то: придумал контртест - пишу его обработку или валидатор чтобы оценить себя хотя бы примерно. Понимаю что можно генетику - пишу её + жадную инициализацию (если возможно). Понимаю что эвристики - пишу простой жадник, смотрю как он работает, далее пишу очевидные штуки. Таким образом можно набрать неплохие баллы сразу по всем задачам примерно за 2 часа (МОШ длится 4 часа), скорее всего даже этого хватит на призера. Далее по ситуации надо стараться набирать баллы.
В целом задачи мне нравятся

Опубликовано расписание. https://mos-inf.olimpiada.ru/info_olymp10-11

Немного интересных чисел:
На МОШе 2021 было 8.87% победителей, 25.2% победителей+призеров и 372 участника
На МОШе 2020 было 7% победителей, 25.1% победителей+призеров и 282 участника
На финал МОШа 2022 приглашено ~770 человек (в прошлом году было приглашено вроде ~600 человек, так что думаю будет ~450-500 участников финала в этом году)

UPD: ссылка на список приглашенных в этом году
https://reg.olimpiada.ru/register/mosh-iikt-2022-1011-participants/olympiad-protocol-static