Мне было лень наполнять этот блог по 1 истории в день. Итак, это будет рассказ о трех днях обучения.

Это было соревнование на Codeforces 3 июля. Это было не очень удачно, но результат был спуск, потому что я был достаточно быстр. Задачи A, B, C были приняты, и я получил +91 к рейтингу.

Задачу D к концу конкурса решили не более 400 человек, но я понятия не имел. Проблема в том, что у вас есть последовательность A из - и +x. Вы перебираете все подпоследовательности B из A и подсчитываете их сумму. Сумма B подсчитывается путем прохождения B слева направо и сохранения мультимножества. Если вы видите -, вы удаляете наименьший элемент из B, если он не пустой, иначе вы добавляете элемент x в B. Сумма B — это сумма элементов результирующего мультимножества. На конкурсе я пытался исправить элемент x и -, что удалит его из мультимножества, но это тупиковая идея. Также пытался исправить что-то еще. Но ключевая идея заключалась в том, чтобы зафиксировать положение одного элемента pos с помощью element + x, пометить все элементы, которые меньше, с помощью S и все, что больше, с помощью G. Равные элементы называются S, если их позиция ≤ pos и G в противном случае. Итак, вы поддерживаете dp[prefix][число S] — количество способов выбрать B таким образом, чтобы оно содержало pos и имело фиксированное количество элементов, помеченных как S. Таким образом, ответом является сумма dp[n][s] для всех s ≥ 1. dp[prefix › pos][0] = 0, потому что вы уже потеряли свой элемент x.

Вывод: ПОПРОБУЙТЕ ИСПРАВИТЬ НЕКОТОРЫЙ ПАРАМЕТР ТАК, ЧТОБЫ МАКСИМАЛЬНО УПРОСТИТЬ ПРОБЛЕМУ. ОСОБЕННО В ПРОБЛЕМАХ DP.

Также я сделал очень глупый баг в этой задаче. Я потратил много времени, пытаясь найти ошибку в переходах DP, но вот:

Я обнаружил этот баг только на следующий день после второго конкурса Умника.

Вывод: СНАЧАЛА ПОПРОБУЙТЕ ИСПРАВИТЬ НЕКОТОРЫЕ ГЛУПЫЕ ОШИБКИ, А ЗАТЕМ НАЙДИТЕ ЛОГИЧЕСКИЕ ОШИБКИ. ЕСЛИ НЕ МОЖЕТЕ ИСПРАВИТЬ СЕЙЧАС, ПОПРОБУЙТЕ ПОЗЖЕ!!!

4 и 5 июля я собирал Е1 и Е2 из этого конкурса. Это тоже проблема ДП. Вам нужно посчитать количество пар (p, q) p, q — таких перестановок, что p ‹ q (lex) и inv(p) › inv(q). В E1 n ≤ 50, в E2 n ≤ 500. Вот и все. Идея показана на картинке ниже:

Поэтому мне нужно подсчитать количество пар (p’, q’) фиксированной длины n, таких, что разница их инверсий больше, чем фиксированное k. Пусть это число равно f(n, k). В E1 достаточно посчитать dp[n][k] — количество перестановок длины n с ровно k инверсиями. f(n, k) считается через dp[n][k]. Это приведет к решению O(n⁵). В E2 вы считаете f[n][k] напрямую и получаете решение O(n³). Детали не важны, но чтобы получить переходы к обоим DP, у вас схожая идея. Как посчитать что-то для перестановки длины n, если у вас есть все ответы для длины n -1? Посмотрите на картинку:

Вывод: ПОСМОТРИТЕ НА ОПРЕДЕЛЕНИЕ LEX!!!

Я также нашел интересную повторяющуюся идею в задачах на перестановки. Вы можете увидеть это в заданиях J из 2-го дня Умника и этом задании. Эта идея состоит в том, чтобы представить перестановки в виде графа i->p[i]. Так что этот граф состоит только из направленных циклов! Эта идея значительно упрощает дальнейшие рассуждения по проблеме. Например, любую операцию перестановки или подобную ей можно представить как объединение или разъединение некоторых циклов. И с помощью этих циклов можно подсчитать какую-то полезную характеристику всей перестановки.

Вывод: ЕСЛИ ВЫ ВИДИТЕ ЗАДАЧУ НА ПЕРЕСТАНОВКУ И НУЖНО ЕЕ КАК-ТО ИЗМЕНИТЬ, ПОМНИТЕ О ПРЕДСТАВЛЕНИИ ПЕРЕСТАНОВКИ В ВИДЕ ГРАФИКА I →P[I]

Что опять с ошибками? Это может быть одним из лучших примеров моей небрежности:

Пример: заявки на задачу H из Умника День 2. Эта задача была решена с помощью тернарного поиска. Я получил AC, но я должен проверить нормальное решение в анализе позже!

БИНАРНЫЙ ПОИСК! Запомни эти слова навсегда! Многие задачи намного проще, чем кажется, если попробовать это применить.

Эта проблема — это пример использования жестов и реклам на дереве для поддержки некоторой структуры данных, такой как дерево сегментов или Fenwick, для ответа на некоторые запросы. Основная идея состоит в том, чтобы проверить, является ли u предком v.

tin[u] ≤ tin[v] и tout[v] ≤ tout[u]. тогда u является предком v

Запросы в этой задаче:

Давайте сохраним 2 дерева сегментов (минимум — 'mn' и максимум — 'mx' по диапазону с обновлением в точке) с tin[v] индексом(точкой) и его значением будет tout[v], если эта вершина добавлена ​​в структуру или ∞(-∞) соответственно.

2. Добавьте v в «mn»

  1. Пока вы запрашиваете минимум в диапазоне [tin[v], ∞) в дереве mn и находите вершину u с tout[u] ≤ tout[v], удалите ее из mn. Если нашелся хотя бы один u — поставить p[v] в ‘mn’

3. Запросить максимум в диапазоне (-∞, tin[v]] в дереве 'mx'. Если какое-то u с tout[u] ≥ tout[v] найдено, то v заполнено. Но тогда запросить минимум в диапазоне [tin [v], ∞). Если найдётся такое u, что tout[u] ≤ tout[v], это означает, что ЭТА ВЕРШИНА U ОЧИСТИЛА ВЕРШИНУ V И ПОТОМ ЕЁ НИКТО НЕ ЗАПОЛНИЛ.

Вывод: ВЫ МОЖЕТЕ ЗАПРОСИТЬ ЧТО-ТО В ДИАПАЗОНАХ ТИПА [TIN[V], TOUT[V]] В ДЕРЕВЬЯХ. ВЫ МОЖЕТЕ ПОСТАВИТЬ ВЕРШИНУ В СТРУКТУРУ, А ТАКЖЕ УДАЛИТЬ ЕЕ

Последней идеей, о которой я хочу упомянуть, является идея с потоками в задаче А из конкурса Умник День 2. В этой задаче вы можете добавить k дополнительных мощностей на каждом краю сети, чтобы получить максимально возможный поток. Итак, давайте добавим дубликаты для каждого ребра. Этот дубликат будет иметь бесконечную емкость и стоимость 1. Исходные ребра будут иметь стоимость 0. Теперь вам нужно найти максимальный поток со стоимостью ≤ k! Удивительное сокращение задач!