Если это решение — бинпоиск по y с моделированием за mlogn, то в нём можно моделирование делать за O(m + n). Вместо одной очереди с приоритетами просто делаем две обычные очереди. В первую складываем отсортированный массив, на котором хотим запустить моделирование. Далее m раз достаём минимум из двух очередей и кладём (его значение + x) во вторую. Элементы в обеих очередях всегда будут идти по возрастанию, и всё работает корректно.

Первое утверждение: если наш маг получает A раз по x, а всего бонусов раздается B, то две раздачи N бонусов эквивалетны — 1 раздаем всем, каждый раз самому бедному, 2 — раздаем N- A, всем кроме первого, потом A раз нашему первому.

Отсюла условие что мы можем получить A x бонусов, (A-1)* x + начальное кол-во у первого < самый бедный ребенок из оставшихся после раздачи N-A, т.е. перед последней раздачей наш самый бедный и A бонус уходит ему.

Величина разности может быть прибавлена к ответу (min(y, (самый бедный ребенок из оставшихся после раздачи N-A) — (A-1)* x + начальное кол-во у первого), , т.е. итерируемся по раздаче, каждый раз пытаемся ему дать столько бонусов, выбираем максимум. Перед следующей итерации берем самого бедного и суем ему x конфет.

Надо выеснить, какими могли быть столбики: пересматриваем их: если там есть и точки и крестики, то данные некорр.(-1), если одно из двух, то столбик назавем этим, а если только вопросики, то назавем вопросиком. Далее можем смотреть на пометки столбиков как на строку. Если в строке в подряд 2 одинаковых символа (. или Х), то это — широкий сигнал, иначе — узкий. Так как неясно что за вопросиками, то надо постепенно вычислять. Если все вопросики вычислили, то идем к ответу, иначе -1 как неоднозначнасть.

А дп писал кто-то после упрощения до строки из "?.X" dp[n][a][b]. кол-во вариантов составить строку на префиксе где последний символ "a" и предпоследний символ "b"?

А как это сделать быстрее чем за ?

Можно перебрать все пары ai, aj, их мало: aj^2 делится на ai, поэтому перебираем ai, а для них — aj решетообразным процессом.

Есть аналогичное и полностью линейное решение. Нужно лишь пользоваться фактом, что если мы хотим сравнять первого пацана с каким-то другим пацаном, нужно делать это как можно позже. А если выписать для каждого пацана номера ходов, на которых происходило добавление к его кучке конфет, можно однозначно восстановить номера позиций первого пацана, если бы он был приравнен к выбранному. Получается, что за количество прибавлений к выбранному пацану мы узнаем, сколько прибавлений произошло бы к первому — сумма всех этих количеств равна m.

Нужно найти максимальный остов.

Считаем по magic столбцов и строк по краям, дальше всё вырождается в win[i][j] = win[i — 1][j — 1]

Можно заметить, что если x < y и 3 ≤ x, то ответ для (x, y) равен ответу для (x - 1, y - 1). Аналогично для x > y

J — перебираем биты от старших к младшим. Если чисел с данным битом нечётное число, то мы обязаны взять его в ответ. Иначе поддерживаем множество позиций, где можно ставить перегородки так, чтобы слева и справа было чётное число чисел с заданным битом. Пересекаем множества перегородок по всем битам, которые можно не брать в ответ. Код

J: перебираем биты в ответе с самого старшего. Смотрим в скольких числах этот бит есть, если их количество нечетное, то мы ничего не сможем сделать, в ответе этот бит в любом случае будет. Если же количество этого бита в числах четное — то мы можем убрать его из ответа, если объединим в одну группу первое и второе число (а так же все числа между ними), где встречается этот бит. Аналогично объединяем 3 и 4, 5 и 6 и т.д. Если в итоге у нас получилось меньше, чем m групп, то так объединить числа не получится, а значит и убрать этот бит из ответа. Если же групп не менее m, то можем заменить исходный набор данных и продолжить перебирать биты ответа. Код

H:

Найдем центр дерева и подвесим дерево за него. Постараемся разбить его поддеревья на две примерно равные половины. Теперь найдем расстояния от корня до всех вершин. В одной половине дерева поставим первую координату вектора  - dist, в другой —  + dist. Далее запустимся рекурсивно от половинок. При сливании ответов нужно не забыть отнормировать координаты так, чтобы в вершине они совпали.

Поймём, что мы получили валидный ответ. Рассмотрим пару вершин. Максимальная по модулю координата их разности — это та, которую мы поставили в тот момент, когда отнесли две эти вершины в разные половинки. А разность этих координат — это как раз расстояние между этими вершинами.

Теперь почему координат не очень много. Тут не совсем понятно. Если бы мы делили каждый раз пополам, то было бы не больше log₂1000 = 10 координат. Но мы делим хуже. Точно правда, что координат не больше log_3 / 21000 = 17. Но, может быть, плохого теста не существует.

По G ничего не пишут, расскажу то, что мы придумали. На контесте WA 23, в дорешке TL 63.
Дисклеймер: Возможно, это решение неправильное/долгое. А может просто у нас руки кривые :)

Совсем глобально: будем искать MST Краскалом. Что у нас при этом происходит — склеиваются компоненты. Дак вот, будем для набора вершин хранить вероятность того, что такой набор вершин в ходе Краскала был компонентой связности, а также мат.ожидание веса этой самой компоненты.

Менее глобально: дп по маскам вершин. Состояние — вероятность события и мат.ожидание, помноженное на эту вероятность.
Теперь интересный момент: хранить эту штуку мы будем как функцию от некоторого x, где x — ограничение сверху на вес ребёр, входящих в MST на этих вершинках. Утверждается, что эта функция — это многочлен.
Тогда ответ — это значение ans[2ⁿ - 1] в точке x = 1.

Теперь как делать переход. Зафиксировали мы текущую маску вершин. Переберем, какие две подмаски вершин только что склеились (в нас). Этим мы заодно зафиксируем k — кол-во ребёр между этими двумя подмасками.


t — это вес ребра, которое мы только что добавили. Тогда все рёбра, которые уже были в компонентах, должны быть меньшего веса.

Из переходов также видно, что это действительно многочлены.

Опишу общие идеи G и I без особых подробностей.

G: Для начала: матожидание k-й порядковой статистики из m равномерно распределенных независимых случайных величин из отрезка [0, 1] равно . По линейности матожидания получаем, что ответ это . Искомую вероятность для всех ребер можно посчитать динамикой: состоянием будет разбиение графа на компоненты связности (их не более 4140). Пересчет динамики для разбиения происходит через меньшие разбиения. Итого решение за O(mK), где K — количество переходов в динамике.

I: Заменим все красные ребра на ребра с весом 0, все зеленые ребра на ребра с весом 1, все синие на ребра с весом n. Теперь вес остовного дерева однозначно определяет, сколько в нем ребер каждого цвета. Свели задачу к следующей: нужно для всех чисел от 0 до (n - 1)n сказать, сколько в графе остовных деревьев с таким весом. Используя обобщенную теорему Кирхгоффа, составим производящую функцию для такой последовательности (про это, например, здесь). После этого надо вычислить эту функцию в n² точках и восстановить коэффициенты полинома по значениям. Итоговое время: O(n³)·O(n²) + O(n⁴) = O(n⁵) (n² раз вычисляем определитель матрицы размера n и за O(n⁴) восстанавливаем коэффициенты по значениям).

+

В E надо ускорить стандартную квадратную динамику f(i, a) — количество правильных ответов среди первых i вопросов, если ответов А было ровно a штук.
Напишем переход такой динамики в случаи если i-ый вопрос был про кол-во вариантов ответа А сделанных ранее и варианты ответа — x_i, y_i:
f(i, A) = min(f(i - 1, A - 1) + (x_i =  = A - 1), f(i - 1, A) + (y_i =  = A))
Аналогично для вопросов про вариант B.
Можно нарисовать квадратную таблицу и обозначить переходы динамики стрелками с весом 1 или 0. При этом кол-во стрелок с 1 весом в каждой строке будет не более 2. Теперь можно переформулировать задачу — найти путь от верхнего левого угла таблицы в любую нижнюю точку, который проходит по максимальному числу стрелок с весом 1. Такую задачу можно решить за O(mlog(m)), где m это количество стрелок веса 1, используя какую-то СД.

Сожмём все позиции, где стоят одинаковые символы в компоненты. Между компонентами есть рёбра, обозначающие, что у соответствующих вершин разный цвет.

Теперь делаем следующее: в каждую вершину запишем число c, берём вершину максимальной степени, домножаем ответ на число, записанное в ней, делаем  - 1 всем соседям, удаляем вершину.

Если промоделировать вычисление префикс-функции, мы получим множество пар индексов (i, j), таких что s_i = s_j, или s_i ≠ s_j. Равные символы сразу объединяем в компоненты, которые сжимаем до вершин и получаем граф, где ребра проведены между вершинами с разными буквами. Этот граф нужно покрасить в c цветов. В нем будет вершина (первый символ) соединенная со всеми остальными. Ее можно удалить, тогда граф распадется на компоненты, в каждой из которых также будет вершина соединенная со всеми, и тд. В коде это будет выглядеть как сортировка вершин по количеству ребер и следующий проход по ним:

ans *= d[v];
for (int to : g[v]){
    d[to] = d[v]-1;
}

Есть еще такое решение:

Будем сами делать КМП. Если pi[idx] ≠ 0, то символ idx равен какому-то из предыдущих, а значит однозначно определен. Значит на ответ влияют только те символы, у которых pi[idx] = 0.

Выпишем теперь список всех символов, которые мы пройдем в ходе КМП для idx. idx должен быть неравен каждому из них. Проблема в том, что они-то могут быть равны друг другу. Но заметим, что когда мы считали КМП для каждого числа из списка, мы тоже шли по этому списку (до того, как воткнулись в символ, равный нашему). Зафиксируем некоторый символ c и посмотрим на все позиции из списка, в которых записан c. Несложно понять, что единственная из них с нулевым значением префикс-функции — это самая маленькая.

Таким образом, кол-во символов, запрещенных для позиции idx равно кол-ву пройденных позиций с нулевым значением префикс-функции.