Сегодня порешал финал МОШа за 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

Сегодня вечером решил открыть МОШ 2020 года. Порешал не особо много, накапливаю силы для предстоящего финала. В целом МОШ 2020 был прикольным.
А - обычный жадник, ничего интересного, 100/100.
B - коммивояжер с ограничениями, обычная генетика дала 96/100.
C - большое условие, не читал
D - выглядит прикольно, но это обычный алгоритмический перебор, который неприятно писать, но решение придумывается просто:
Давайте сначала подумаем какая высота будет оптимальной для некоторого набора высот. Во-первых эта высота должна содержаться в имеющихся высотах, так как только значения имеющихся высот могут являться "перегибами" (более правильно - точками экстремума). Далее допустим что у нас есть ответ для некоторой высоты. Также K1 высот меньше и K2 больше этого значения. Тогда при уменьшении текущей высоты на 1ответ изменится на DOWN_COST * K2 - UP_COST * K1, а при увеличении UP_COST * K1 - DOWN_COST * K2. Получается это практически производная функции, являющейся параболой.

Продолжение:
В данном случае вершина будет в точке, для которой UP_COST * K1 = DOWN_COST * K2 <=> DOWN_COST / UP_COST = K2 / K1, Иначе говоря отношение кол-ва вершин большей оптимальной высоты должно относится к кол-ву вершин с меньшей высотой как DOWN_COST / UP_COST. Но так как вряд ли это число будет целым, то можно посчитать для двух высот - с индексом округленным вниз и индексом, округленным вверх. Получается для набора значений мы уже можем за O(1) находить оптимальную высоту. Давайте будем не каждый раз делать массив, а поддерживать этот набор - будем просто в лоб переносить наш прямоугольник сначала по столбцам, потом по строкам. Тогда будет сложность O(n*m*min(n,m) * log(n*m)) (можно в декартаче поддерживать текущий набор, или в pbds_tree), Впринципе для n=m=5000 это терпимо чтобы локально посчитать. Можно конечно построить какое нибудь двумерное персистентное ДО чтобы на каждый из n^2 запросов отвечать за log^2|log^3, но мне кажется это уже слишком.

Итак, уже завтра будет финал МОШа. Для меня это будет последний шанс получить бви в МФТИ/ВШЭ (мне нужно именно победить). Я посмотрел МОШ за 2020 и за 2021 года. Мне они показались решаемыми, на победа балл набирается довольно легко (если учесть что МОШ длится 4 часа), Но я и старые года ИОИПа легко писал на победа, а в итоге на этом финале больше 3 часов убил на задачу, в которой вообще надо было писать другой алгоритм и не стал даже призером. Очень надеюсь что на МОШе тупить не стану и всё-таки смогу стать победом. В этом году вроде даже будет особенно много участников на финале => будет больше победителей.
Хочу пожелать удачи всем, кто пишет и тоже взять победов (но меня не обгонять!). Писать я кстати буду в вышке, если кому-то интересно.
Кстати, а после МОШа будут еще какие-то олимпиады идти, или со следующей недели уже можно будет с чистой совестью писать посты про ЕГЭ и каггл?

Регистрация на МОШ уже через 2 часа. Всем удачи!

Мош закончился, чуть позже напишу свое впечатление. Пока кажется есть даже шансы на победа