Конспект

Всем удачи завтра на регионе!

Что ж, завтра уже 2й тур региона. 1й я люто слил (256=100+100+10+46). D должна была на 62 зайти, но почему-то не зашла за O(nmlogn) при n=500, m=1e5.
Шансов у меня конечно мало, но вроде ненулевые. Всем завтра удачи на туре!

UPD: завтра после тура постараюсь написать свое итоговое мнение по регу. Пока 1й тур очень неприятный, посмотрим что будет дальше

Итак, мои руки дошли до этого поста. 2й тур я слил (265=100+63+69+33), так что со всеросом пролетаю. Впрочем, остаётся ещё несколько олимпиад, затащить которые есть шанс.
Мое мнение по задачам этого региона:
А1) простая, даже, на мой взгляд, проще чем надо. Решалось просто запоминанием суммарного циклического сдвига (сдал на 100)
B1) норм, решалось или за линию через суффиксные максимумы префиксных сумм, или через ДО, или ещё как-то (были разные способы) (сдал на 100)
С1) геома.. уже много лет на регионах не было геомы, и тут они вдруг решили ее добавить, да ещё и такую противную в плане точности. Оказывается, что нужно решать через углы и обязательно через acos/atan2 (и то приходилось подбирать eps), в противном случае точность падала оч сильно и решение вместо 100 набирало 15-55. Если же углы правильные, но неправильный eps, то 40+. При правильном eps - 100
(Сдал на 10)
Д1) оказывается, довольно простая задача, если знать что сумма хешей = хеш суммы. Бинарный поиск по ответу + хеши заходили на 100 (сдал на 46)

А2) математика, мне не понравилось, долго выводил формулу (сдал на 100)
B2) задача на бинарный поиск по ответу. Я сдал все подгруппы кроме финальной, придумал решение за O(nqlogn), но подумал что не зайдет, так как не увидел ограничение n*q<=1e5. Очень тупо здесь потерял 37 баллов (сдал на 63 балла)
C2) изи жадник на 66, заифал подгруппу ещё на 3 балла. На 100 динамика по поддеревьям, не придумал на туре, но люди говорят, что эта задача баян (сдал на 69).
Д2) уже интересная задача, но там на 100 некоторые пихали квадрат и неправильное решение набирало 100 баллов. То есть задача хорошая, но тесты оч слабые (сдал на 33, хотя если бы я написал ту лажу (была такая идея, но придумал контртест), то получил бы 100 из-за слабых тестов)

Итог:
Регион позорно слит (521 балл, хотя мог и 700 набрать), всероса мне не видать. Остаются технокубок, мош, открытка, вп и иоип.

Регион я конечно слил, но жизнь всё-таки продолжается. Немного дорешаю длинный тур открытки (чтобы наверняка пройти), потом напишу свое мнение (оно очень даже положительное на данный момент). В ближайшие 2 недели на codeforces будет куча контестов, планирую написать каждый из них. Также возможно начну решать что-нибудь на каггле.

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

Отборы:
✅МОШ (информатика) - 320/500 проход
✅ ИОИП - 197 баллов по первому отбору и 116 баллов по второму отбору

Финалы:
✅ 1)Высшая проба (информатика) - 6 февраля (воскресенье) в 9:30, тур длится 3 часа (материалы https://codeforces.com/group/6Saz5idq0O)
✅ 2) СПбГУ - 13 февраля (воскресенье)
❌3)Всесиб (информатика) - 27 февраля (воскресенье)
✅4)НТО ИИ - 28 февраля - 5 марта
✅5)Открытка - 5-6 марта
✅6)ИОИП - 19 марта
✅7)Технокубок - 20 марта (воскресенье)
8)МОШ - 3 апреля

В планах:
получить бви либо на ПМИ МФТИ, либо на ПМИ ВШЭ (ну или хотя бы ПИ ВШЭ)
то есть или стать призером открытки, или победить в любой другой олимпиаде из списка

Результаты:
☑️1) Высшая проба - 358/500 - призёр - не хватило 19 баллов до победа
❌2) СПбГУ - 418/600 - слил - не хватило 1 балла до призера
❌3) Всесиб - не писал
☑️4) ИИ НТО - призер - слил
❌5) Открытка - 339/800 - слил - не хватило ~140 баллов до призера
❌6) ИОИП - 281/500 - слил
❌7) Технокубок 560/800 место - слив
☑️8) МОШ - 411/600, 50/505 место - призер

Как и обещал, рассказываю как решал открытку:

(Задачи: https://www.olympiads.ru/zaoch/2021-22/zaoch/zaoch_long_20211231.pdf)
UPD: тут разбор A,B,D,G (ну и впринципе Е)

А (сдал на 100)) Ищем за линию первое вхождение нужное подпоследовательности, затем от первого ее элемента идём назад и пытаемся аккуратно оптимизировать нужную подпоследовательность (если встретили элемент из последовательности - смотрим по индексам можем ли мы взять его, вместо старого, если можем - хорошо, берём, иначе ничего не делаем)
B сдал на 69(+31)) я решал сетом+мапой
Поддерживал сет начал непрерывных отрезков и мапу самих отрезков (ответ - ищем наибольшее начало отрезка, меньшее X; обновление - аккуратно добавляем и заметим, что в случае переливания у нас от текущего отрезка добавиться 1 элемент слева и 1 справа, а так же элемент right-(X-left) занулится
C) подумал что гроб и сдал квадрат на 23
D (сдал на 100)) Предподсчитаем факториалы и кол-во неотрицательных чисел. Попробуем найти ответ для a[I]>=0 в некоторой вершине.
Очевидно, что это C(pol,k)*fact(k)*fact(n-k-1)*a[I] :
Выберем k неотрицательных чисел для "префикса" (фактически это глубина вершины), соответственно можем выложить эти k и остальные n-k-1 чисел (факториал способов). А что нам мешает считать не для 1 числа, а сразу для всех? 1 раз пройдемся dfs'ом и посчитаем число способов, потом домножим на сумму чисел
Е) аккуратное хитрое ДО. Я сначала делал в тупую (хранил множество запросов в вершине), где-то 20 баллов вроде получал (ML), потом оптимизировал, получил 60. Вроде придумал как сдать на 100 (битмаски в вершинах или очень аккуратно пушить), но лень было писать.
F) пробовал по приколу отправить рандом, получил 0
G) сначала долго тупил, не мог придумать. Потом пришла идея: переведём исходную строку в формат (a[I], cnt[I]). Затем, если длина именно такого подотрезка четная, то добавляем cnt[start]*cnt[end]. Но есть ещё интересные случаи: существует тройка a[I], a[I+1], a[I+2], где a[I]=a[I+2] и (i-start)%2==0. То есть мы можем либо разделять старым образом, либо взять сразу 3 элемента, чтобы изменить нужную четность. Ещё у нас может быть cnt[I]>1 и (i-l)%2==1, то есть разделить 1 блок на 2 (четность расстояния появляется из утверждения, что при четном отрезке все ок). Пишем решение за квадрат, получаем баллы, думаем как оптимизировать. Заметим, что достаточно просто знать первый "хороший" элемент. Тогда просто идём и за линию считаем (сначала находим по хорошему элементу для каждой четности, затем если 1 из них остаётся позади, ищем следующий ближайший). Получаем 100.

Вчера решал финал высшей пробы 2016-2017 года. Было 5 задач на 3 часа.
я набрал 74/100 баллов (20+20+0+20+14). По меркам 2017 это победитель (с форой аж целых 3 балла!!!!)
https://codeforces.com/group/6Saz5idq0O/contest/315337/standings/groupmates/true
А) простая задача на формулки. НО! Сначала писал на плюсах, получал 18/20 баллов, потом решил что проблема в том что иногда мы можем уйти в минус, переписал на питон (там остаток по модулю нормально берется), 20/20
B)тоже простая задача - уровень воды в i-й клетке равен минимуму из максимума слева и максимума справа (их можно предподсчитать). Соответсвенно сама воды в i-м блоке это max(0, min(left_max, right_max)-s[i]), а ответ - сумма таких значений
C) как то думал и не придумал, пытался дпшкой сделать но не вышло
D) прикольная задача, сначала я посмотрел что будет если решать в лоб (очевидно тл). Далее вспомнил всем известную идею с расстояниями до объектов - можно не проверять каждый раз расстояние от объекта i до множества других объектов, можно просто "расширить" каждый элемент из множества объектов. Теперь мы можем объединить все пересекающиеся объекты и получить множество непересекающихся объектов (тут используем снм). Теперь понятно, что мы можем проплыть слева направо при условии что нет объекта, который занимает и 1 и последнюю строку (чтобы обойти объект - его надо объехать или сверху или снизу, а тут ни так ни так не получится)
Теперь пишем простой бинпоиск по ответу - итоговая сложность O(k^2*logk*logn)
E) как говорили многие люди, геому решать маму не уважать геома это плохо. Я довольно быстро придумал что нужно просто проверить пересечение двух выпуклых оболочек (для объектов каждого класса строим выпуклую оболочку). Далее проверял пересечение отрезков этих оболочек, получил за это 8 баллов, стал думать. Понял что многоугольник может лежать внутри, добавил эту проверку, получил еще 6 баллов. Ну а дальше видимо где то набагал или что то не рассмотрел .
В целом норм контест, похож по сложности +- на div2 codeforces

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

Только что закончил писать тур финала вп 2018 года.

https://codeforces.com/group/6Saz5idq0O/contest/315127

Написал норм (20+20+20+17+20=97 при пороге 96 на победа в 2018).
A) простая задача на поиск первого элемента с максимальным кол-вом вхождений
B) дано множество отрезков, нужно выделить из них такие отрезки (в т.ч. обрезать имеющиеся) чтобы итоговая длина отрезков была максимальна и в каждой точке было не более 1 отрезка. Сначала долго тупил, но потом все-таки написал сканлайн
С) долго думал, начал писать мосты, понял что лажа, начал нервничать, решил загонять квадрат. Загнал 🤡
D) хорошая задача, сначала тоже тупил и не мог ничего придумать, затем написать разделяйку - ищем минимум в текущем отрезке, добавляем к текущему ответу длину отрезка * минимум, разделяем по минимумам, запускаемся от новых отрезков (в лучшем случае работает nlogn, в худшем n^2) Это + ифание дало 17/20 баллов. Только после конца заметил что минимум для подсчета ответа мы можем брать через ДО, а сами отрезки разделять по заранее выписанным индексам для каждого числа. После тура сдал на 20/20
Е) довольно очевидно сводится к штуке наподобие эйлерова цикла: идем дфс'ом, запоминаем фактически какая вершина раньше какая позже. В ответе - ориентируем ребра так, чтобы они шли из "ранних" в "поздние" вершины
Итого за сегодня сдал всё на фулл (но жалко в D тупил, не успел полностью сдать)

Прошу любить и жаловать, @Vovanm88, наш новый математик. Он будет периодически выкладывать посты по олимпиадной математике.

Всем привет, ребят!
На самом деле, поскольку я буду начинать скорее с азов, я буду(а может и нет, хехе, напишите в комментариях, повторятся или нет) во многом повторятся в одной замечательной книгой, "Как решаются нестандартные задачи", авторы Канель-Белов и Ковальджи. И если вы хотите поглотить все базовые принципы самостоятельно - рекомендую прочитать ее.

А вот и она

Первый пост можно сказать по олпроге. Советую всем подучить плюсы, так как код я буду писать на них.
Вот кстати неплохой курс для старта https://stepik.org/course/80538