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

(Задачи: 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

Старые туры ИОИПа (насколько мне известно, тут есть люди, которые его пишут)

Пост №1 с полезными материалами для индивидуального тура НТИ.
Сегодня расскажу про немного полезную (а самое главное) штуку .
Допустим нам нужно посчитать в массиве кол-во значений, которые зависят от нескольких элементов/индексов (желательно от двух):
Например https://codeforces.com/contest/1520/problem/D (посчитать кол-во пар j-i=a[j]-a[i] | j > i
Решается подобное очень просто: нужно всего лишь изменить формулку и свести это к известной/простой задаче.

В данном случае можно сделать a[j]-j = a[i]-i. Теперь это можно посчитать очень просто - присвоим каждому элементу массива a[i] = a[i] - i
и посчитаем сколько раз встречается тот или иной индекс. Теперь ответ - это сумма cnt[i] * (cnt[i] - 1) / 2 (cnt[i] - кол-во элементов i в массиве).

Но иногда встречаются задачи и посложнее. Например я встречал почти такое же условие еще наверно в 3-5 задачах на codeforces позже в разных контестах. Также была интересная задача с подобной штукой в финале Технокубка 2021 (задача F). Но там это нужно было считать на графах + не такой тривиальный подсчет и нужно по-хитрее изменить формулу чтобы получить нужную асимптотику.
Для тренировки можете решить ту задачу сами и при желании поискать еще похожие задачи.

(Вот если интересно мой код на питоне (плюсов я тогда еще не знал) для этой задачи (https://codeforces.com/contest/1520/submission/120204431). )

Далее в планах расскать про префиксные/суффиксные штуки, виды бинарного и тернарного поиска, снм, дерево отрезков, немного о графах и комбе. Если кто то захочет по-подробнее узнать о чем-либо еще - пишите,

И раз уж на данный момент у меня особо нет времени заниматься data science'ом, хочу порекомендовать вам канал своего друга, который как раз пишет про свои разработки и интересные новости из мира ИИ https://t.iss.one/gradientdip

Раз уж большинство проголосовали за домашки, то держите ссылку на группу где я буду писать конспекты и добавлять тематические контесты (не забудьте выбрать роль "участник, если хотите решать задачи"): https://codeforces.com/group/a1W1cUWddJ

UPD: прошу строго не судить, я только пробую учить других людей. Если что-то не устраивает - можете смело писать например в лс

Всем кто пишет удачи сегодня на отборе иоипа!

Написал отбор на иоип, впринципе слил но не так критично (особенно если учитывать что это первый отбор):

Условия: https://neerc.ifmo.ru/school/io/archive/20220129/problems-20220129-individual.pdf
100+0+100+68
А) простая задача на префсуммы
Б) динамика за O(n*x*k) которую не придумал
С) Заметим, что если рассматривать группы, которые начинаются в i-м отрезке и заканчиваются в j-м, то функция F(i, j) не возрастает при увеличении j (F(i, j) - пересечение отрезков). Соответственно для текущего отрезка i бинпоиском находим первый и последний подходящий отрезок. Осталось быстро считать максимум начал на отрезков на отрезке и минимум концов на отрезке. Я сначала пытался ДО за O(n*log^2 n) запихнуть, но безуспешно, потом пытался спуском получать ответ, но набагал. Сдался и написал спарсы
Д) Решал сначала подгруппы, быстро понял что хлд, но было лень писать поэтому только подгруппы. (Оказывается можно было еще ДО на tin вершин сделать но что то не додумался)

107/470 место

UPD: завтра и послезавтра на codeforces будут контесты, надеюсь их не слить.
Ну и конечно советую всем их написать.