Разбор Кубков НИЯУ МИФИ - Algocourse/info GitHub Wiki

A. Симуляция

Для решения задачи достаточно в момент определения значения $b_i$ знать, встречалось ли соответствующее $a_i$ до этого. Это можно сделать, используя хеш таблицу или древовидную структуру, например $std::set$.

B. Исследование

Рассмотрим первый элемент массива $a$, пусть это $x$. После выполнения операций он превратился в некоторый префикс массива $b$, из которого можно получить $x$, выполняя обратные операции (из двух подряд идущих $y$ получить один $y-1$).

Для того чтобы проверить, подходит ли какой-то префикс массива $b$, будем перебирать его элементы с начала и класть их в отдельный массив $c$. После каждого добавления будем производить обратную операцию, пока возможно (пока в конце массива $c$ есть 2 одинаковых элемента) - тогда в массиве $c$ не будет подряд идущих одинаковых элементов, а значит, таким образом мы выполняем максимально возможное количество обратных операций. Если $x$ действительно был преобразован в некоторый префикс, то в некоторый момент массив $c$ будет состоять из единственного элемента $x$, поскольку данный алгоритм выполняет максимально возможное количество обратных операций.

Таким образом, можно по очереди проверить все элементы массива $a$, убирая из рассмотрения очередные элементы $b$. Каждый элемент массива $b$ рассматривается 1 раз, а также всего может быть максимум $m - n$ обратных операций - поэтому сложность решения $\mathcal{O}(n + m)$.

C. Настольный теннис

Если игра закончилась после раунда $x$, то значит одно из условий для победы, связанных с $n$ или $k$, только что стало выполняться, при этом второе также выполняется.

Пусть у победившего $a$ очков, а у проигравшего - $b$, тогда $a + b = x$.

Если после раунда $x$ стал выполняться критерий на $k$, то мы получаем второе уравнение $a - b = k$. Решая уравнения и проверяя, что $0 \le b$, можно проверить этот случай. Это действительно означает, что игра могла закончиться после раунда $x$ - например, игроки получали +1 по очереди до $b$, а затем один из них получил $k$ подряд. Однако при $k = 1$ этот вариант не рассматривается, так как $k = 1$ означает, что игра идёт до получения $n$ очков одним из игроков.

Второй случай - стал выполняться критерий по $n$, то есть $a = n$. Остаётся посчитать $b$ и проверить, что $0 \le b \le a - k$.

D. Строковый автомат

Для начала найдём все достижимые вершины из вершины $1$ обходом графа, а также все вершины, из которых можно попасть в терминальные, обходом транспонированного графа из терминальных вершин.

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

Иначе пройдёмся по $попрядку$ от конца к началу и посчитаем максимальную достижимую длину $dp[x]$ для каждой конкретной вершины $x$. Тогда $dp[1]$ - максимальная длина строки.

Для нахождения строки заведём массив текущего слоя. Изначально в нём только вершина $1$. На каждом шаге рассматриваем все переходы в вершины, из которых можно достичь длины в точности на $1$ меньше, чем длина для текущего слоя, и выбираем наиболее выгодный переход - это и будет очередная буква ответа. Новый слой создаём из всех вершин, в которые можно перейти из текущего по наиболее выгодной букве, при этом уменьшив максимальную длину ровно на $1$. Поскольку у каждой вершины фиксированная максимальная длина, то в этом процессе она сможет побывать не более 1 раза.

Асимптотика решения $\mathcal{O}(n+m)$ или $\mathcal{O}(n + mlog m)$ в зависимости от реализации.

E. Лист

Оказывается, для решения задачи достаточно делать запросы с $S = T$. Если мы сделаем такой запрос, то получим число рёбер в подграфе из вершин множества $S$. Кроме того, оказывается, что можно узнать степени всех вершин, чего достаточно для решения задачи.

Первым запросом получим общее число рёбер, сделав запрос с множеством из всех вершин. Далее для $n-1$ вершины сделаем запросы с множеством, в которое входят все вершины, кроме данной вершины $x$. Тогда мы получим число рёбер, не соединённых с вершиной $x$, из чего можно рассчитать степень вершины $x$. Степень последней вершины можно рассчитать, зная суммарное число рёбер.

F. Скобочные последовательности

Определим, когда массив $b_1, b_2, \ldots, b_m$ является $хорошим$. Для того чтобы из него можно было сделать сбалансированную скобочную последовательность, его сумма должна быть равна 0. Для того чтобы среди двух подряд идущих чисел было отрицательное, положительных чисел должно быть не больше, чем отрицательных(положительное число не может быть в конце, так как сбалансированная последовательность завершается скобкой $)$, поэтому после каждого положительного числа стоит отрицательное).

Этого достаточно для того, чтобы массив $b$ был хорошим. В качестве примера сбалансированной последовательности можно сделать чередование положительных и отрицательных чисел (пока положительные не кончатся), причём брать положительные в порядке убывания, а отрицательные в порядке возрастания модуля. Этот пример корректен, поскольку для массивов с одинаковой суммой сумма $x$ максимумов в одном из них не меньше, чем сумма $x$ минимальных чисел в другом.

Используем этот критерий для решения задачи. Для начала посчитаем префиксные суммы по массиву $a$ и рассмотрим некоторое значение этих префиксных сумм. Пусть $i_1, i_2, \ldots, i_m$ - индексы, где достигается одинаковая префиксная сумма. Для того чтобы сумма на отрезке равнялась 0, можно брать отрезки с границами в индексах с одинаковой префиксной суммой - поэтому рассмотрим эти индексы отдельно.

Создадим массив $c$, где $c_i = 1$, если $0 < a_i$, в противном случае $c_i = -1$. Построив префиксный массив на нём, можно быстро найти все суммы этого массива между подряд идущими индексами $i_1, i_2, \ldots, i_m$. Теперь для второго условия нужно найти все пары индексов, между которыми сумма по массиву $c$ не больше $0$.

Будем поддерживать набор текущих сумм по массиву $c$, начиная с $i_1$ и до текущего $i_{j-1}$. При добавлении в рассмотрение $i_j$ увеличим ответ на количество чисел в наборе не больше $-x$, где $x$ - сумма по массиву $c$ от $i_{j-1}$ до $i_j$. Затем добавим $x$ ко всем числам набора и добавим число $0$ в набор.

Структуру, поддерживающую добавление элемента, прибавление числа ко всем элементам и поиск числа элементов, не превышающих данный, можно реализовать через декартово дерево или $ordered$ $set$. Тогда итоговая асимптотика - $\mathcal{O}(nlog n)$

G. Серия побед

Зафиксируем $x = l$ - число выигранных раундов, которые выиграл Андрей, тогда $p = l / g$ - вероятность, что Андрей выиграет раунд, а $q = 1 - p$, что проиграет.

Пусть $dp[i][j]$ это вероятность попадания в ситуацию(для всех возможных ситуаций), когда счёт игры $i$ у Андрея, $j$ у Саши и последний раунд (если он был) Андрей не выиграл, причём Андрей ещё ни разу не выигрывал $s$ раундов подряд. Если посчитать такую динамику, для ответа на задачу остаётся рассмотреть все ситуации перед выполнением $s$ побед подряд, то есть все позиции $dp$, где $i + s \le n$ или $|i + s - j| \le k$, просуммировать их вероятности(т.к. мы не можем попасть в 2 разные такие позиции в одной игре перед выполнением $k$ побед и при этом эти варианты являются всевозможными). Данную сумму нужно умножить на $p^{s}$ - вероятность $s$ побед подряд. Это и будет ответ.

Однако из-за условия на разницу в не более $k$ побед эта динамика имеет бесконечное число состояний. Для начала рассмотрим те из них, где $i,j < n$.

Для подсчёта динамики рассмотрим $dp[i][j]$. До этого Андрей проиграл раунд, а перед этим выиграл от $0$ до $s - 1$ раундов. Значит $dp[i][j]$ = $\sum_{m = max(i-s+1,0)}^i p^{i-m} q dp[m][j-1]$. Считая динамику таким образом, можно решить эту часть задачи за $O(n^2s)$.

Оптимизируем этот подсчёт. Будем итерироваться по $j$, а затем по $i$, пусть $cur$ это $dp[i - 1][j]$. Можно заметить, что в нём неким образом учтены почти все переходы для $dp[i][j]$, чтобы получить $dp[i][j]$, вычтем из $cur$ переход из $dp[i - s][j]$, если он есть, умножим $cur$ на $p$, и наконец учтём переход из $dp[i][j - 1]$. Теперь динамика пересчитывается за $O(1)$ и работает за $O(n^2)$.

Далее рассмотрим вторую часть "лесенку", которая появляется из-за условия на $k$ и уходит в бесконечность. Её рассмотрение можно начать, например, с слоя, где $j = n-1$ и $n-k \le i \le n+k-2$ - эти индексы мы также не учитываем в первой части решения, так как учтём в этой.

На каждом слое с постоянным $j$ количество состояний по $i$ равно $m = 2k - 1$. Рассмотрим переход от $j$ к $j+1$. Его можно полностью описать матрицей $T$, где $t_{ik}$ это коэффициент, с которым происходит переход от $i$ позиции из слоя $j$ в позицию $k$ слоя $j+1$ - они считаются аналогично динамике в первом случае.

Пусть $\vec{x_0}$ это набор значений $dp$ в первом слое(в данном случае при $j = n-1$), $\vec{x_1}$ в следующем и так далее. Для решения задачи необходимо из каждого слоя взять все позиции, из которых можно сделать серию из $s$ побед - для их нахождения найдём, к чему стремится $\sum_{i = 0}^{\infty} \vec{x_i}$.

$\vec{x_i} = \vec{x_0} * T^{i}$. Поэтому для решения задачи остаётся посчитать $\sum_{i = 0}^{\infty} T^{i}$. Эта сумма равна $(E - T)^{-1}$. Таким образом задача решается за $\mathcal{O}(n^2 + k^3)$.

В действительных числах обратная матрица всегда существует, поскольку сходятся соответствующие вероятности. Однако по модулю её может не существовать, если определитель матрицы делится на $998244353$.

Оценим вероятность этого - $p,q$ линейно зависят от выбранного $x$, а в переходах они могут умножаться не более $2k-1$ раз. Поэтому если рассмотреть определитель как функцию от $x$, то это будет многочлен степени не более $2\cdot300\cdot300$. У него не более $2\cdot300\cdot300$ корней по модулю, а значит вероятность того, что для данного $x$ обратной матрицы не существует, не превосходит $2\cdot300\cdot300 / 998244353 < 2\cdot10^{-4}$. Вероятность того, что для всех 14 возможных $x$ обратной матрицы не будет существовать менее $10^{-50}$ - эта вероятность достаточно мала.

A. Загадочный массив

При применении любой операции мы получаем возможность добавить единицу к любому элементу с большим индексом - после выполнения каждой операции будем добавлять 1 единицу, которую мы можем прибавить далее в некоторый счётчик. Рассмотрим элементы с начала до конца и будем хранить число единиц, которое мы можем добавить к любому элементу далее. Если очередной элемент больше $1$, то будем вычитать из него $2$, пока можем (и для последующих операций запомним, сколько раз мы сможем добавить единицу за счёт этого). Это является оптимальным, так как далее мы не сможем использовать этот элемент никак. Если он после этого равен 1 и мы можем добавить к нему 1, добавим и выполним ещё операцию - это также выгодно, так как мы получаем то же 1 прибавление назад и выполняем дополнительную операцию. Теперь рассмотрим случай, когда элемент равен 0, но мы можем добавить ещё 2 единицы, чтобы выполнить операцию. Оказывается, что в этом случае добавление 2 единиц является оптимальным.

Рассмотрим все единицы, которые мы будем куда-либо добавлять. Они либо не принесут никаких операций, либо принесут 1 операцию, комбинируясь с единичкой, первоначально находившейся в некотором месте, либо принесут 1 операцию, комбинируясь с другой прибавленной единичкой. Однако второй из этих случаев возможен лишь тогда, когда мы, рассматривая новую позицию в нашем алгоритме, рассматриваем нечётное число и при этом у нас есть хотя бы 1 единица, которую можно применить. Все остальные добавления единиц должны комбинироваться между собой - при этом мы тратим 2 операции прибавления и получаем одну, а значит, вне зависимости от того, когда мы будем тратить единицы таким образом, мы не будем никак влиять на возможность потратить единицы способом 2. Тогда выгоднее тратить их как можно раньше, так как полученные прибавления при этом можно будет применить на больший участок массива.

Таким образом, алгоритм, описанный выше, является корректным.

B. Сокровище

Пусть кладоискатели остановятся в городе $i$, тогда наибольшая прибыль, которую они получат, это сумма $k$ максимумов префикса массива $a$ до $i$ включительно минус сумма массива $c$ до $i$ не включительно. Ответом будет наибольший ответ среди этих случаев. Тогда для решения достаточно поддерживать $k$ максимумов на префиксе, что можно сделать, используя структуры, поддерживающие поиск минимума, добавление и удаление ($std::multiset$ в C++). Такое решение будет работать за $\mathcal{O}(n \log n)$.

C. Бугристый массив

Заметим, что если некоторый элемент строго больше своих соседей, то соседние элементы могут быть только строго меньше соответствующих им соседних элементов. Это означает, что если $a_1 < a_2$, то $a_2 > a_3$ и наоборот.

Для решения рассмотрим 2 случая сравнения $a_1$ и $a_2$ в итоговом массиве. Пусть $a_1 < a_2$ в итоговом массиве, тогда если это неравенство уже выполнено, не будем изменять $a_2$, иначе увеличим $a_2$ до значения $a_1 + 1$. Это является оптимальной стратегией, т.к. увеличение $a_2$ только $улучшает$ требуемое неравенство $a_2 > a_3$, а значит, если нам необходимо применить некоторое количество операций для достижения $a_1 < a_2$, выгодно применять их к $a_2$. После достижения $a_1 < a_2$ увеличение $a_2$ только $улучшает$ $a_2 > a_3$, однако уменьшение $a_3$ влияет на это неравенство также, но возможно $улучшает$ неравенство $a_3 < a_4$, а значит, если нужно выполнить $a_2 > a_3$, не хуже будет применять операции к $a_3$. Таким образом, это оптимальное количество операций, которые нужно применить к $a_2$.

Случай, когда $a_1 > a_2$, рассматривается аналогично. После применения операций к $a_2$ рассмотрим неравенство, связывающее $a_2$ и $a_3$, которое будет однозначно определено предыдущим. Выполним этот процесс всего $n - 1$ раз для каждого из двух вариантов сравнения $a_1$ и $a_2$. Получим 2 возможных ответа, из которых выбираем наименьший. Асимптотика решения: $\mathcal{O}(n)$.

D. Эксперимент

Рассмотрим случай, когда все частицы одного типа. Тогда для быстрого решения задачи можно хранить все энергии в множестве, которое поддерживает добавление, удаление и поиск минимума за $\mathcal{O}(\log n)$, и число $d$, показывающее, на сколько должны быть увеличены все элементы множества. Тогда операция 3 заключается в увеличении $d$. Для добавления $x$ нужно добавить $x - d$, и аналогично с удалением. Сумму можно поддерживать отдельно и пересчитывать после каждого запроса.

Тогда для решения задачи будем поддерживать такую структуру для каждого типа частицы, а также сумму всех элементов и множество минимумов. При выполнении операции только одна структура изменяется, значит, можно учитывать только её изменения для пересчёта суммы и множества минимумов. Таким образом, данное решение работает за $\mathcal{O}(q \log q)$.

E. Лабиринт времени

Если бы в задаче не было $k$ дополнительных добавлений времени, то задачу можно было бы решить обычным алгоритмом Дейкстры. Для того, чтобы учитывать дополнительные $k$ условий, будем использовать пары $(u, mask)$ для алгоритма Дейкстры. Такая пара будет означать минимальное расстояние до вершины $u$, если при этом мы посетили хотя бы 1 ребро из условия $i, 0 \le i \le k - 1$ для всех $i$ таких, что бит под номером $i$ в маске равен $1$. Тогда при переходе из такой пары нужно, как и в графе, перебрать исходящие из $u$ рёбра и соответствующие конечные вершины $v$. Если эти рёбра не участвуют в условиях, то переходим в $(v, mask)$. Если ребро участвует в условии, то нужно либо добавить $1$ в соответствующий бит маски, чтобы далее при возможном посещении второго ребра учесть дополнительное условие, либо, если там была единица, добавить к потраченному времени время из соответствующего условия.

В таком графе мы будем рассматривать $\mathcal{O}(m2^{k})$ переходов, а значит асимптотика решения будет $\mathcal{O}(m2^{k}(\log m + k))$.

F. ГПСЧ

Первым же запросом с $t = 0$ узнаем значение $b$. Затем сделаем запрос со значением $t = 1$ и получим $ans$ в качестве ответа.

Далее решение разбивается на 2 случая:

1. $ans < b$.

Это означает, что $ans = a + b - p$ - так как уменьшение ответа означает вычитание модуля. Предположим $x$ это наименьшее натуральное число, для которого при переходе от $t = x - 1$ к $t = x$ получаемое число увеличивается, т.е. не происходит вычитание модуля. Мы не вычитаем $p$ в первый раз, значит в качестве ответа для $t = x$ мы получим $ax + b - (x - 1)p$. Также значит, что это минимальный $x > 0$, для которого $ax + b - xp < 0$. Решая последнее неравенство с учётом выражения для $ans$, получим: $x > \frac{b}{b-ans}$. Учитывая, что $x$ минимальный, $x = \lfloor\frac{b}{b-ans}\rfloor + 1$. Сделав запрос для $t = x$, получим уравнение $ax + b - (x - 1)p = ans3$, используя выражение для $ans$, получаем систему из двух уравнений, решив которую, получим ответ. Итого в первом случае достаточно сделать всего 1 дополнительный запрос.

2. $ans > b$

Тогда $a = ans - b$. Остаётся узнать $p$. Сделаем запрос по числу $t = \lceil\frac{10^9-b}{a}\rceil$ - тогда в ответ получим $ans = at + b - kp$. Отсюда можно найти $kp$, причём это число не будет превышать $10^9$. У таких чисел не более $9$ простых делителей, каждый из них можно проверить на модуль - если для простого делителя $del$ ответ на запрос $t = del$ равен $b$, то $del$ это и есть искомый модуль. В этой части нам требуется максимум $10$ дополнительных запросов.

Замечание:

Во втором случае можно проверять сразу несколько простых чисел таким же образом, если делать запрос с $del$, равным произведению выбранных простых чисел. Вместо перебора $9$ чисел можно за запрос делить оставшиеся простые числа на две группы и узнавать, в какой из них есть искомый модуль. Тогда вместо $9$ запросов потребуется $4$, а всего потребуется $7$ запросов.

G. Ключевое слово

Введём обозначения $n = |S|$, $k = |A|$. Пусть $dp_i$ - математическое ожидание построченного времени при условии, что префикс длины $i$ уже набран. Тогда $dp_n = 0$, а $dp_0$ - искомое число.

Для каждого префикса длины от $0$ до $n - 1$ рассмотрим $dp_i$. При добавлении одного случайного символа текущий накопленный префикс $i$ переходит в один из префиксов $j$, где $j \le i + 1$. Определить все возможные переходы можно с помощью автомата Ахо-Корасик. Если из префикса длины $i$ можно перейти в префиксы длины $j_1, j_2 \ldots j_k$ для каждой из $k$ букв, то $dp_i = 1 + (dp_{j_1}+dp_{j_2}+\ldots+dp_{j_k}) / k$.

Тогда выразим все $dp_i$ в виде $a*dp_0 + b$. Это можно сделать последовательно, обрабатывая уравнения, так как в уравнении для $dp_i$ присутствуют $j \le i + 1$.

Тогда получим соотношение на $dp_n = 0$, используя которое, можно найти $dp_0$. Асимптотика решения $\mathcal{O}(nk)$

Замечание:

Данную задачу можно решить за $\mathcal{O}(n)$

A. Знак

Заметим, что ввод слишком большой, чтобы считать его в число. Для решения задачи достаточно считать только один символ

B. Уравнение

Что значит решить уравнение? Вспоминая школу, решить уравнение - это значит "Найти все такие $x$, что подставляя $x$ в уравнение, получится верное равенство. А также - показать, что никакие другие числа решением не являются." Нас просят найти все целые решения из интервала $[-1000; 1000]$. Давайте для каждого числа из этого интервала проверим, является ли равенство верным. Единственная ловушка для решающих не на питоне - переполнение. Проверяя $x = -1000$, слагаемое $a * x ^ 4$ при $a = 1000$ порядка $10^{15}$, в int же влазят числа не более $2 * 10^9$.

C. Наложение рисунков

Нужно перебрать все возможные положения рисунков относительно друг друга и выбрать наилучший вариант, удовлетворяющий условию. Итоговая сложность $O(n^4)$

D. Муки совести

Из условие необходимо было выделить следующие строки:

• "количество новостей перестало увеличиваться и осталось равным 10"
• "K одинаковых рекламных постов"
• "M неразличимых постов про учебу"
• "сколько различных последовательностей постов длины N он может сделать из ограниченного набора новостей, обязательно использовав M постов про учебу и К с рекламой"

То есть используя только 10 объектов нам нужно создавать последовательности длины N, обязательно использовав M постов про учебу и K с рекламой. Также необходимо не забыть, что рекламные посты нельзя ставить в начало последовательности.

Одно из возможных решений:

1. На первом месте стоит учебная $\dfrac{(n - 1)! * 8^{n - (k + m)}}{(m - 1)! * k! * (n - (m + k))!}$ Поставим на первое место учебную и найдем количество всевозможных перестановок длины (n - 1). Умножим на 8 в степени равной количеству незанятых учебой и рекламой постов. И чтобы убрать повторения из-за неразличимости новостей необходимо поделить на количество перестановок (m - 1) учебных, k новостных и (m - (n + k)) оставшихся

2. На первом место стоит не учебная и не новостная $\dfrac{8 * (n - 1)! * 8^{n - 1 - (m + k)}}{m! * k! * (n - 1 - (m + k))}$

Если сложить оба этих варианта можно прийти к формуле: $\dfrac{(n - k) * (n - 1)! * 8^t}{m! * k! * t!}$, где $t = n - (m + k)$

Альтернативное решение:

Способов расположить рекламные посты равняется $C_{n-1}^k$, т.к. нельзя ставить в начало. Способов расположить посты про учебу равно $C_{n - k}^m$, т.к. рекламные посты мы расположили. А оставшиеся свободные места надо занять любым из 8 оставшихся возможных постов, т.е. еще $8^{n - m - k}$ вариантов. Итого ответ на задачу: $C_{n-1}^k \cdot C_{n - k}^m \cdot 8^{n - m - k}$.

E. Почти Фибоначчи

Тривиальное решение не пройдет по времени из-за ограничений на $n \le 10^9$. Заметим, что для перехода от $(F_1, F_2, F_3)$ к $(F_2, F_3, F_4)$ нужно умноженить первый вектор на матрицу

Для того чтобы получить вектор $(F_{n-2}, F_{n-1}, F_n)$ нужно изначальный вектор умножить на нашу матрицу $n-3$ раза. Однако если просто перемножать матрицы $n-3$ раза, то мы все еще не проходим по времени. Воспользуемся бинарным возведением в степень и получим решение с сложностью $O(m^3\log n)$, где $m$ - размер матрицы.

Также можно было воспользоваться техникой предподсчета.

В качестве более простого примера, можно ознакомиться с задачей быстрого поиска n-го числа Фибоначчи.

F. Поисковая строка

Можно было решить задачу, отвечая влоб на каждый вопрос. Для этого перебираем все строки из базы - и для каждой проверяем, является ли строка-запрос префиксом строки из базы. Это долго - $O(Lbase * Lask)$ где $Lbase$, $Lask$ - длина строк в базе и в запросах соответственно. Рассмотрим решение через бор.

Бор: давайте построим граф, который будет нам помогать отвечать на запросы очень быстро. Каждый символ - это переход по ребру из текущей вершины. Назначим некую вершину($0$) стартом. Если мы хотим вставить слово(или найти) в боре, поступаем так. Встаем в стартовую вершину. Смотрим на первый символ строки. Если из текущей вершины есть переход(ребро отвечающее за эту букву) - переходим по ребру. Если нет - создадим новую вершину и ребро. После чего перейдем по ребру. Теперь мы оказались в вершине, которая отвечает за строку из первой буквы строки. Повторим то же самое для второго символа - посмотрим, есть ли ребро, соответствующее 2 букве слова. Если есть, то переходим. Если нет, то создадим, затем перейдем. Пройдя всю строку - получим вершину, соответствующую концу данной строки.

Идея решения: Заметим, что все префиксы строки - это вершины на пути к концу данной строки. Тогда пройдя по строке-запросу в боре(дошли до вершины $V$), нам надо посчитать количество "концов" в поддереве $V$ - до скольких концов мы можем дойти двигаясь по ребрам из вершины $V$.

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

Также задачу можно решить хешами.

G. Cвоевременно

Данную задачу можно решить с помощью бинарного поиска по ответу. В качестве параметра для бинарного поиска будем искать ответ на задачу - максимальное количество коробок, которое мы можем провезти за данный промежуток времени.

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

Итоговая асимптотика алгоритма $O(log(w) * m * log(n))$

У всех задач существует несколько решений, которые подходят под ограничения. Также доступен код от armoking@

Задача на математику. Основная формула, которую нужно знать - содержание одной жидкости (X мл) в другой (Y мл) вычисляется по формуле X / (X + Y). Все вычисления в задаче необходимо было делать в целых числах. Также необходимо было удостовериться, что смесь растворов помещается в ёмкость.

Видео.

Задача реализационная. Ограничения в задаче достаточно небольшие и можно было просто перебрать координаты в двойном цикле и вывести их. Геометрически все интересующие точки находятся на прямой, поэтому можно было перебрать только одну координату и проверить, что вторая - целочисленная.

Видео.

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

Видео.

Задача реализационная. Первым шагом надо было подсчитать количество вхождений каждой буквы исходного слова. Далее, для каждого слова из входных данных, также вычислить количество вхождений каждого символа и сравнить: если количество вхождений i-го символа исходного слова меньше количества вхождения i-го символа в j-ое слово, то такое слово не является ответом и выводить его не надо. Иначе - надо вывести j-ое слово.

Видео.

Задача на математику. Чётное количество делителей имеют все числа, которые не являются квадратами какого-либо числа. Решение - количество "квадратов" на интервале [A;B]. Количество квадратов можно вычислить по формуле sqrt(B) - sqrt(A). Нужно аккуратно следить за тем, в какую сторону округляются числа. Можно было перебрать все числа от 1 до X, пока X^2 не превысит B и подсчитать их количество на отрезке [A;B]. Также существует решение через решето Эратосфена, которое позволяет не задумываться о том, какие же числа имеют чётное число делителей.

Видео. Решение через решето Эратосфена.

Задача на реализацию. Надо перебрать все возможные координаты и запомнить количество различных точек с фиксированным расстоянием до "центра" - точки (x_0; y_0). Среди множества точек с фиксированным расстоянием (пусть их количество - M) существует M*(M-1)/2 пар. Надо для каждого фиксированного расстояния (максимальное - 2*N) вычислить количество пар и вывести.

Видео. Решение за O(N).

Задача на динамическое программирование.

Наивное решение, которое не учитывает ограчения по памяти: состояние динамики dp[i][j][k] хранит минимальное количество денег нужное, чтобы купить i единиц первого товара, j единиц второго товара, k единиц третьего товара в первые (i + j + k) дней. Изначально dp[0][0][0] = 0. Переходы: dp[i][j][k] -> {dp[i + 1][j][k] + cost(a_i); dp[i][j + 1][k] + cost(b_i); dp[i][j][k + 1] + cost(c_i)}, т.е. мы можем купить какой-то товар, увеличить его количество на 1 и прибавить его стоимость. Такое решение не удовлетворяет ограничениям по памяти.

Необходимо заметить, что (i + j + k) в точности равно количеству уже рассмотренных дней, поэтому можно хранить dp[i][j] для двух последних дней и тогда переходы будут такие: dp[i][j] -> {dp_next[i + 1][j] + cost(a_i); dp_next[i][j + 1] + cost(b_i); dp_next[i][j] + cost(c_i)}. Такое решение будет удовлетворять ограничениям по памяти.

Видео.

Задача на алгоритм Дейкстры. Отличия от оригинального: присутствуют веса у вершин. Для применения необходимо преобразовать граф. Каждую вершину представить в виде пары вершин (i, i + N); каждая такая пара должна быть связана ориентированным ребром e(i, i + N); все рёбра изначального графа должны вести из "второй копии" вершины в первую, т.е. ребро изначального графа e(u, v) должно быть преобразовано в e(u + N, v). В таком графе необходимо найти путь из вершины 1+N в вершину N.

Видео.

Задача на тему "Рюкзак". Единственное отличие от оригинала - вес не является целочисленным. Поэтому необходимо преобразовать веса к целым числам - умножить на 1000.

Видео.

Задача на тему построения выпуклой оболочки. В задаче надо было понять, что искомое пространство - выпуклая оболочка над множеством входных точек. Для подсчёта площади можно было воспользоваться формулой знаковой площади, вычисляемоей через векторное произведения векторов.

Видео.

Задача на дерево отрезков.

Операция изменения - стандартная операция над деревом отрезков.

На запросы второго типа можно было отвечать с помощью спуска в дереве или с помощью бинарного поиска (итоговая сложность O(Q * Log(N)^2). Сумма элементов массива неубывает => можно в бинарном поиске перебрать правую границу отрезка, сумма на котором меньше значения в запросе (левая граница - точка из запроса).

Видео.