Сегодня вечером решил открыть МОШ 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 часа. Всем удачи!

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

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

Мои личные предикты такие (если вдруг кому-то интересно):
360 призер
420 побед

Если кто-то написал меньше 360 и уже расстраивается - не расстраивайтесь, многие говорят что у меня тут слишком высокие предикты

Пока живём

Итог: 411/600
Жаль на Е баллы потерял, Б не придумал на фулл и в Д не заслал кукарек

Вообще, если смотреть на прошлый год (самый лёгкий, по словам некоторых в этот раз было заметно сложнее), то в этом году вполне может быть и 380/600 на победа.

Я посчитал:
На площадках МОШа было зарегистрировано более 600 человек (приглашено было ~770)

Есть инсайдерская инфа что баллы будут чуть повыше, чем эти. Надеюсь мне врут или тот человек ошибается

Вообще странно что так долго нет резов, такое чувство словно реально банят кучу народу

Если так будет, то есть шанс что забанят реально много кого. Тогда баллы на победа/призера непредсказуемы практически. Могут как повысится, так и понизится

Короче ждём резов и молимся

Ввиду того, что кажется я проебал мош, вот мой первый пост про ЕГЭ:
На прошлой неделе писал пробники, набрал так:
96 математика (затупил в очевидном параметре)
88 информатика (не умею читать условия)
69 русский (потерял кучу баллов в лёгких заданиях тестовой части, 6 баллов на структуре сочинения (переписал бы чуть иначе 2 предложения - не потерял бы), 1 балл на орфографии (боитЬся) и 1 на пунктуации (тире между подлежащим и сказуемым))
Это 96+88+69=253/300 баллов
Но давайте представим реальную ситуацию: призером ВП я инфу превращаю в сотку и добавляем 10 баллов ид с других олимп.
Итого: 96+100+69+10=275/310
Впринципе если хотя бы проверять русский, то можно будет спокойно подавать на грант в физтех

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