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

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

Сегодня решил написать финал высшей пробы за 2019 год.
(ссылка https://codeforces.com/group/6Saz5idq0O/contest/314982)

Задачи меня разочаровали, они оказались оч простыми.
А) считаем факториал в лоб, пока (если) он не станет нулем
B) заметим xor-штуку: либо все числа счастливые, либо ни одно число не является счастливым. Это происходит за счет того, что если xor массива без одного числа равен этому числу, то xor массива равен 0 (a xor a = 0) . Просто поддерживаем xor и размер массива
C) Я сначала прошелся dfs'ом и посчитал кол-во интересных вершин в поддереве, а потом жадно обошел это дерево только до интересных вершин. Ответ - кол-во посещенных таким образом вершин
D) Тут пришлось чуть-чуть подумать. Заметим, что сумма с i=1 по i=n-1 abs(a[i] - a[i-1]) равна a[n-1] -a[0] (если массив отсортирован). Сначала пробовал жадно через указатели искать оптимальную последовательность, не заходило, решил добавить еще пару случаев, не заходило. Потом до меня дошло, что я рассматриваю только случай, когда наименьший элемент из 1-го массива. Взял все элементы в отдельный массив и прошелся по нему двумя указателями, поддерживая кол-во уникальных чисел на отрезке - зашло.
E) Безыдейное ДО (можно наверно еще корнячку но в я в нее не умею). Просто аккуратно инвертируем элементы на отрезке и поддерживаем кол-во единиц на четных и нечетных позициях. Но так как набагал, зашло только с 5-й попытки.


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

RuCLIP tiny - быстрее, чем вы думаете 🔥

Спустя около месяца с начала разработки, мы готовы представить вам самую свежую нашу работу - модель для связывания текста и изображения - RuCLIP tiny.

Что в ней такого примечательного? Как минимум её размер на диске 146Мб(!), занимаемый объем ~800Мб в памяти видеокарты, а также кол-во параметров 38М. И все это в fp32.

А что ещё? Конечно же скорость работы, а именно ~16мс на батче размером 64(!). Мы также протестировали нашу разработку на датасете CIFAR100 и получили 46.62% top1 и 73.18% top5 zero-shot accuracy.

Помимо всего прочего мы не забыли сделать удобный интерфейс и ноутбуки для наших пользователей.

Почитать поподробнее можно в нашей статье на хабре
Саму разработку вы можете найти на нашем гитхабе

Сегодня написал финал ВП 2020 года
https://codeforces.com/group/6Saz5idq0O/contest/314675
Набрал 20+20+20+1+13=74 балла (призер от 63, побед от 90)
Задачи оказались гораздо интереснее и сложнее
А) простой жадник: если сумма нечетная - выводим все плюсы
иначе ищем первое нечетное число и после него ставим умножение
B) жадник на указателях: сначала сортируем массив, затем жадно собираем для каждого случая сначала максимум элементов, потом минимум
C) довольно интересное дп. Сначала посортил значения и придумал за O(n^3) - dp[i][j] - ответ, где i - текущая позиция, j - откуда пришли (переход - dp[i][j] = max(dp[j][k]+1 для k от 0 до j-1, при условии, что a[j] - a[k] > a[i] - a[j]), написал - получил баллы, понял что идея рабочая (10/20 баллов). Заметим, что это означает, что длина каждого нового прыжка строго меньше предыдущего, а так как высоты башен уже посорчены, мы можем найти бинпоиском последнее подходящее k и взять максимум на отрезке. Это уже работает за O(n^2 * logn), но набирает 16/20 баллов. Еще можно заметить, что при увеличении j, последнее подходящее k уменьшается, поэтому предподсчитаем эти k за n^2. Далее чуть-чуть попихал и получил 20 баллов
D) не придумал, заслал кукарек и получил 1 балл
E) долго думал, потом решил попробовать идею выделения меньших элементов (если существует k подходящих подотрезков, то существует k "центральных" элементов (которые как раз медианы), следовательно ответ это длина отрезка минус удвоенное кол-во элементов, меньших m). Получил 13 баллов, очень удивился. Стал писать merge sort tree, но не успел отдебагать и поэтому только 13 баллов.

Впринципе неплохо, но мог и лучше написать

Сегодня написал финал вп за 2021 год
20+20+20+0+9=69 = призер 3й степени
В общем слил. А в добавок в этому еще и приболел (пока 37.8 температура).
Ну и конечно же половину тура у меня голова болела так, что я тупо смотрел в экран и не мог думать.
Еще полчаса читал условие Ешки, пытался понять что вообще происходит в задаче.
А) простая математика (я писал бинпоиск)
B) простая математика (перебор до корня)
C) довольно сложное (для меня) дп по подотрезкам, долго думал и писал
D) придумал вроде рабочее дп по поддеревьям, но так и не отдебагал (квадрат по сложности)
Е) как выше писал - полчаса тупил не мог понять что вообще происходит, далее придумал решение за O(nm), написал, получил 9 баллов. Как оптимизировать не придумал, но судя по подтаскам, либо дд, либо корневая.

Что могу сказать по задачам финалов ВП. Поначалу (до 2019 включительно) это были относительно простые, но идейные задачи на разные темы. А вот финал за 2020 и 2021 год - это простая математика + динамика + до/корневая. Будет забавно, если на финале 2022 выдадут также первые 2 таски на математику, потом 1 на динамику, потом 1 но что-нибудь и еще одну на до/корневую.

Всем, кто пишет, завтра удачи на высшей пробе по информатике!

Сегодня слил закл ВП. Очень обидно, так как не успел заслать D (скорее всего на фулл). Ну и не придумал простую идею в Eшке на +17.
В целом задачи вроде норм, но слабоваты тесты.
A) математика
B) бинпоиск + 2 указателя
C) перебор (у меня фактически квадрат, но работает за 0.59)
D) сначала заслал лажу за O(n^2*logn), получил 36, потом пытался сортить строки и от порядка искать ближайших, но wa получал (как оказалось некоторые такое на 100 сдали, так что у меня руки кривые). Далее пытался сортить по префиксу и суффиксы и от них искать ближайших, но чуть чуть не успел отладить. Возможно потерял на этом 64 балла
E) гроб. На 22 - квадрат, на 39 - счетчик элементов в мапе

Жалко конечно, но призера кажется возьму. А это хотя бы бви в питерскую вышку (по словам знакомых норм место, но поизучаю получше, но в крайнем случае можно будет проще перевестить в мск вышку, чем из другого вуза)

Интересный факт:
1) финал спбгу по информатике будет 13 февраля в 10:00-15:00
2) 2-й отбор на иоип будет 13 февраля в 14:00-19:00
Я попробую поучаствовать в обоих (да, закончу спбгу на час раньше)