Сегодня написал финал ИОИПа за 2021 год (https://codeforces.com/gym/103031). Задачи мне очень понравились, а еще больше понравился мой результат - 451/500 баллов при пороге 377/500 на победителя. Теперь по задачам:
А) Простая реализация, для удобства я её сдал на питоне через split
B) Задача на матешу. Сначала я рассмотрел несколько случаев, решил за линию. Далее можно заметить что нам нужно по сути найти пересечение двух монотонных функций, одна из которых возрастает а другая убывает. Написал бинопоиск и получил 100 баллов.
C) Просто считаем кол-во циферок в каждом разряде за линию, а потом за O(1) обновляем. Итоговая сложность O(n * 6 * 10).

D) Гроб, возможно эвристический. Видно что по времени тут все хорошо идет и пихать надо в кол-во запросов. Придумал за n * log2(h) - 0 баллов, стал думать. Где-то час сидел, потом до меня дошло что n,h,q мы считываем только 1 раз и получил 20 баллов. Потом стал думать как использовать запросы 2-го типа. Пришла идея этими запросами посортить вершины и запустить разделяйку. На удивление сработало и сразу получил 51 балл, мне очень понравилось)))
(разделяйка в среднем уменьшает кол-во запросов тут в 2 раза, но обычно даже еще лучше)
E) Довольно простая идея за квадрат - считаем для начальных строк хеши, записываем их в мапу. Важно заметить что для составления новых строк мы можем использовать только префиксы начальных строк длиной gcd(длины начальных строк, кол-ва символов для удалений). (чуть ниже распишу почему так, пока просто поверьте). Далее за квадрат пишется очевидная динамика - dp[i] - можем ли собрать префикс длины i в текущей строке (dp[0]=1 всегда). Далее немножко кукарек - если идти не с начала, а с конца, то мы можем считать динамику за линию, а не за квадрат (тут получаем 100 баллов).
Теперь распишу подробнее фишки Ешки и как тут сделать так чтобы коллизий в хешах (конкретно в этой задаче ) было поменьше

Теперь по поводу Ешки:
1) почему мы можем использовать только префиксы длины кратной gcd:
Заметим что не можем использовать абсолютно любые подстроки из-за таких условий, но во первых мы всегда можем добавить lcm(длины удалений) текущую строку и потом сделать gcd * k удалений (k - просто натуральное число любое). Аналогично и с длинами имеющихся строк - они также могут влиять на кратность длин. Отсюда получаем что каждую строку можно разбить на len / gcd частей и использовать любой префикс этих частей
2) как квадрат переписываем в линию:
изначально нам приходится перебирать за квадрат, так как если можно собрать префикс длины i текущей строки, то он может достигаться из любого другого (необязательно последнего) собранного префикса, как так мы его собираем их префиксов других строк - за счет этого если K собираем из I, то необязательно что K собираем из J (I<J<K) и наоборот. Но тут можно заметить фишку - что если рассматривать с конца и собирать суффиксы - то если суффикс длины K достижим из суффикса длины J, то он достижим и из суффикса длины I ( I<J<K), так как подстрока K-I (являющаяся префиксом одной из начальных строк) будет также префиксом подстроки K-J. Поэтому нам достаточно хранить последний собранный суффикс (важно - собираем суффикс мы из префиксов начальных строк)
3) коллизии:
мы просто можем сделать не обычный сет хешей, а мапу длина-массив хешей, за счет этого на случайных строках коллизий будет во много раз меньше

Удачи всем на иоипе!!!

ИОИП закончился, я жестко слил.
A и B были изи задачками, сдал за 15 минут.
Далее прочитал С, ничего не понял, решил попробовать Д.
3 часа пихал ДО, запихал только на 19. затем перечитал С и сразу сдал кукарек на 62.
Ешку прочитал, понял что гроб, не стал даже трогать.
Итого 281/500 баллов 100/340 место.
Последняя надежда на МОШ... (ну если что по гранту поступлю, но хочется все равно по олимпе)

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

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

Удачи всем на технокубке!

К сожалению, @dmitry10005 оказался ближе всех по предмету моего места(

Пришло время моему мнения насчет финала технача.
ABD, 2200 баллов, 560 место - слил всухую
А) сумма двух максимумов
B) удаляем первый символ пока он есть в остальной строке
C) считаем сумму и пишем из нее дфс:
если нашли имеющийся элемент - прекращаем эту ветку
пришли в единичку - прекращаем эту ветку
и не забываем делать отсечение на общее кол-во действий (n)
D) тут есть несколько общих схожих способов решения. Многие писали переливайку
Я же факторизовал предподсчетом 2е5 чисел за n*ln(n), считал произведение по модулю всех числителей а потом дфсом искал гцд по множителям мапой, параллельно считая числа в вершинах
Е) говорят корнячка заходит, но мне кажется что это лажа

Итого тильт, слитый технач (64 место (по сути побед) - чисто ABCD, значит можно было с ABCD взять победа).
Не то чтобы я мог стать победом, я не рассчитывал даже, но слив иоипа, говно таски на обоих финалах - довольно серьезно дизморалят. Остается одна надежда: МОШ.

Писать дальше посты про олпрогу и подготовку или разбавить немного решением каггла?

Прошу любить и жаловать, @ValeroN01. Валера будет делать посты про DS/ML и подобное

Итого по предиктору только +12 будет,но если бы я не затупил и переделал свою лажу, было бы +112 )))) 🤡

Как говорится, "задача успешно провалена".
В целом раунд получился не самым плохим.
A - проверка на квадрат
B - жадник
C - говорят можно указателями, но я писал хеши 🤡
D - чуть более интересная задача. Посмотрим внимательно на ограничения, поймем мы можем победить монстра i только если Hp * Dp * k > Hm * Dm. Далее за O(ClogC) делаем предподсчет - максимальное k * Dp * Hp при стоимости Сi. Моей ошибкой было то что я не предусмотрел что могут быть юниты одной стоимости - из-за этого и тл (слабые претесты были пройдены с 390мс). Жалко конечно, но некритично. Далее считаем префиксные максимумы и делаем по ним бинпоиск. Итого O((C+M)logC)
E - какое-то дп на комбу, не придумал
F - не читал

Учитывая все мои сливы олимпиад, решил посмотреть сайт ИТМО (туда уже есть бви), не такой уж и плохой вуз оказывается....
Военная кафедра есть, общаги есть, дешёвые даже, стипы неплохие.... И самое главное - НЕТ ФИЗИКИ!!!))

Открыта регистрация на очный тур олимпиады для 10-11 классов
https://reg.olimpiada.ru/register/mosh-iikt-2022-1011
Участникам заключительного этапа всероссийской олимпиады рекомендуем регистрироваться 28 марта. Окончание регистрации - 29 марта. Напоминаем, что олимпиада проводится только очно. Площадки перечислены в регистрационной анкете.

Появились резы СПбГУ по всем предметам с критериями!

Инфа - 71
Физика - 55
Математика - 55

Забавно, мне 1/600 балла не хватило до призерства 🤡

Хороший мем, позитивный

Выложили резы ВП, я в 66-й, 100% призер. (Жалко что минуты на Дшку не хватило....)
https://olymp44.hse.ru/OLYMPREPORTS/MMO/SecondStage/Results/5229753737.pdf