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

Только что закончил писать тур финала вп 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 будут контесты, надеюсь их не слить.
Ну и конечно советую всем их написать.