### Problem A. Long-Term Mail Storage.↵
↵
The probelm asked to simply simulate the process. One can keep yet unread mails in any data structure (array, deque, set, whatever) and iterate through time. For any moment of time $x$ we first check whether there is a new incoming letter and add it to the structure if that is the case. Now, check if the ``feeling guilty'' condition is satisfied. If so, compute $k$ and remove $k$ oldest letter from the structure. Doing all this in the most straightforward way would result in $O(nT)$ complexity. ↵
↵
↵
Excercise: solve the problem in $O(n)$ time.↵
↵
### Problem B. Lassies Versus Machine.↵
↵
First of all, note that if Dusya and Lusia split $n$ in $x$ and $n - x$ they would get exactly the same set of banknotes as a change as if they split in $x + 5000$ and $n - x - 5000$. That means, we only have to check all possibilities to split from $a$ to $min(a + 5000, n - a)$. For each possibility we compute the change in $O(1)$ time. If some girl wants to pay $y$ the change will be $(5000k - y)~mod~500$, where $k = \lceil \frac{y}{5000} \rceil$.↵
↵
Excercise: prove that it's enough to check only values from $a$ to $min(a + 499, n - a)$.↵
↵
### Problem C. Effecient Management Returns.↵
↵
There are many different approaches for this problem and almost all solutions one can imagine will work as the size of the answer will never exceed $\sqrt{2m}$ (excersise: prove). This editorial contains only one possible linear time solution.↵
↵
Proceed vertices one by one. After we have processed first $i - 1$ vertices ($v_1, v_2, \ldots, v_{i - 1}$) we would like to keep a way to dirstibute them among $k_i$ teams $T_1, T_2, \ldots, T_{k_i}$ that will satisfy all the requirements. When we add a new node $v_i$ we should find any component $T_j$, such that there is no node $u \in T_j$ and $(v_i, u) \in E(G)$. Assuming $k_i \leq \sqrt{2m}$ this can be done in $O(\sqrt{2m} + deg(v_i))$ time by simply making an array of boolean marks and traversing the list of all neighbours. If there is no such $T_j$, we consider $k_{i + 1} = k_i + 1$, i.e. we create a new set for this vertex. However, we actually do not need this $O(\sqrt{2m})$ time to set up the boolean array, as we can use only one array and mark it with a number of iteration instead of a simple \emph{true}. Thus, we set marks in $O(deg(v_i))$ time and then simply consider all sets one by one till we find first valid. Obviously, we will skip no more then $deg(v_i)$ sets till we find first possible match, thus the running time will be $O(deg(v_i))$ and the total running time is $O(n + m)$.↵
↵
### Problem D. The Sting.↵
↵
First of all we would like to slightly change how we treat a bet. Define $c_i = a_i + b_i$. Now, if we accept the $i$-th bet we immediately take $b_i$ and then pay back $c_i$ in case this bet plays. Define as $A$ some subset of bets, $S(A) = \sum_{i \in A} b_i$, i.e. the total profit we get from subset $A$. Define as $L(A)$ the total amount we will have to pay in case the game result will be "team looses", i.e. $L(A) = \sum_{i \in A, t_i = `L'} c_i$. Similarly we introduce $D(A)$ and $W(A)$. Now, the profit of Ostap if he accepts subset $A$ is $S(A) - max(L(A), D(A), W(A))$.↵
↵
In this form it's not clear how to solve the problem as we simultaneously want to maximize $S(A)$ from the one hand, but minimize maximum from the other hand. If we fix the value $max(L(A), D(A), W(A)) = k$ the problem will be, what is the maximum possible sum of $b_i$ if we pick some subset of "loose" ("draw", "win") bets with the sum of $c_i$ not exceeding $k$. Such values $dp(type, sum) \rightarrow profit$ can be computed for each outcome independetly using knapsack dynamic programming. The complexity of such solution is $O(nL)$, where $L = \sum a_i + b_i$.↵
↵
### Problem E. Random Value of Mode.↵
↵
To start with consider $O(n^2)$ dynamic programming solution. Let $dpleft(i, j)$ be the optimum expected value if Gleb has visited all shops on segment from $i$ to $j$ inclusive and is now standing near the shop $i$. In the same way $dpright(i, j)$ as the optimum expected value if segment from $i$ to $j$ was visited and Gleb stands near shop $j$.↵
↵
We are not going to consider all the formulas there, but here is how we compute $dpleft(i, j)$, picking the minimum of two possibilities go left or go right:↵
$$dpleft(i, j) = min(1 + t_{i - 1} + p_{i - 1} \cdot |i - 1 - x| + dpleft(i - 1, j) \cdot (1 - p_{i - 1})$$, $$(j + 1 - i) + t_{j + 1} + p_{j + 1} \cdot |j + 1 - x| + dpright(i, j + 1) \cdot (1 - p{j + 1}))$$↵
↵
To move forward we should have a guess that if there are no $p_i = 0$ we are going to visit many shops with a really small probability. Indeed, the smallest possible positive probability is one percent, that is $0.01$ which is pretty large. The probability to visit $k$ shops with $p_i > 0$ and not find a proper coat is $0.99^k$, that for $k = 5000$ is about $1.5 \cdot 10^{-22}$. Assuming $t_i \leq 1000$ and $n \leq 300\,000$ the time required to visit the whole mall is not greater than $10^9$, thus for $k = 5000$ it will affect the answer by less than $10^{-12}$. Actually, assuming we only need relative error $k = 3000$ will be sufficient.↵
↵
Now, we find no more than $k$ shops with $p_i > 0$ and $i < x$ and no more than $k$ shops with $p_i > 0$ and $i > x$. Compress shops with $p_i = 0$ between them and compute quaratic dynamic programming. The overall running time will be $O(n + k^2)$.↵
↵
### Problem F. Measure Twice, Divide Once.↵
↵
We need to assign each vertex a single positive integer $x_v$~--- the number of the process iteration when this vertex will be deleted. For the reason that will be clear soon we will consider $x_v = 0$ to stand for the last iteration, i.e. the greater value of $x$ correspond to the earlier iterations of the process. One can prove that an assignment of positive integers $x_v$ is correct if and only if for any two vertices $u$ and $v$ such that $x_u = x_v$ the maximum value of $x_w$ for all $w$ on the path in the tree from $u$ to $v$ is greater than $x_u$. That is necessary and sufficient condition for any two vertices removed during one iteration to be in different components.↵
↵
Pick any node as a root of the tree. Denote as $C(v)$ the set of direct children of $v$ and as $S(v)$~--- the subtree of node $v$. Now, after we set values of $x$ in a subtree $v$ we only care about different values of $x_u$, $u \in S(v)$ that are not "closed", i.e. there is no value greater between the corresponding node and the root of a subtree (node $v$). Denote as $d(v, mask)$ boolean value whether it's possible to set values of $x$ in a subtree of node $v$ to have values $mask$ unclosed. Because of centroid decomposition we know there is no need to use values of $x$ greater than $\log n$, thus there are no more than $O(2^{\log n})$ different values of mask, i.e. $O(n)$. $d(v, mask)$ can be recomputed if we know $d(u, mask)$ for all $u \in C(v)$ in $O(n^3)$ time. Indeed, if one child $u_i$ uses mask $m_i$ we know:- ↵
↵
1. We have to set $x_v$ greater than any $i$ that occurs in more than one mask.↵
2. We can set $x_v$ to any $i$ that doesn't occur in any $m_i$.↵
3. If we set $x_v = i$, all $j < i$ are set to $0$ in $m$.↵
↵
Now, one can notices that according to the following process if mask $m_1$ is a submask of $m_2$ it is always better lexicographically smaller than mask $m_2$ it always affects the result in a better way. Now, we claim that if for some subtree $v$ we consider the minimum possible $m$, such that $d(v, m)$ is true, for each $m_1 > m$ there exists $m_2$ submask of $m_1$ such that $d(v, m_2)$ is true. Indeed, consider the first (highest) bit $i$ where $m$ and $m_1$ differ. Because $m_1$ is greater than $m$ it will have $1$ at this position, while $m$ will have $0$. If there is no $1$ in $m$ anymore it is itself a submask of $m_1$, otherwise, this means $x_v < i$. We can set $x_v = i$ and obtain a submask of $m_1$.↵
↵
The above means we should only care about obtaining a lexicographically smallest mask for each subtree $S(v)$. To do this we use the above rules to merge the results in all $u \in C(v)$. This can be easily done in $O(n \log n)$ or in $O(n)$ if one uses a lot of bitwise operationsЗадача A. Письма долгого хранения.↵
↵
В данной задаче требовалось просто просимулировать описанный в условии процесс. Например, можно в любой структуре данных (массив, очередь, дерево) поддерживать множество ещё не обработанных писем и по очереди рассматривать все моменты времени. При рассмотрении момент времени $x$ сначала проверяем, есть ли новое входящее письмо, и, если да, то добавляем его в структуру. Далее проверяем, не наступило ли хотя бы одно из условий, при которых Бомбослава разбирает почту. Для симулирования разбора почты вычисляем число $k$ и последовательно вынимаем $k$ наиболее старых писем из структуры. Даже самая простая реализация этого процесса будет работать за время $O(nT)$.↵
↵
Упражнение: решите задачу за время $O(n)$.↵
↵
### Задача B. Девчата против автомата.↵
↵
Для начала заметим, что если Дуся и Люся поделят число $n$ на $x$ и $n - x$, то они получат в качестве сдачи ровно такой же набор банкнот, как если поделят $n$ на $x + 5000$ и $n - x - 5000$. Таким образом, достаточно будет только проверить всем способы разбиения, где $x$ проходит диапазон от $a$ до $min(a + 5000, n - a)$. Для каждого способа вычислим сдачу за время $O(1)$ по следующей формуле: если какая-либо из девушек хочет заплатить величину $y$, то размер полезной сдачи будет $(5000k - y)~mod~500$, где $k = \lceil \frac{y}{5000} \rceil$.↵
↵
Упражнение: докажите, что достаточно перебрать значения $x$ в диапазоне от $a$ до $min(a + 499, n - a)$ включительно.↵
↵
### Задача C. Эффективный менеджмент возвращается.↵
↵
Существует множество различных решений данной задачи, и почти любое из них уложится в ограничение по времени, поскольку в ответе будет использовано не более $\sqrt{2m}$ команд (упражнение: доказать это утверждение). Данный разбор будет содержать описание одного из возможных линейных решений.↵
↵
Будем добавлять вершины графа по одной. После рассмотрения первых $i - 1$ вершин ($v_1, v_2, \ldots, v_{i - 1}$) мы будем поддерживать распределение их между $k_i$ командами $T_1, T_2, \ldots, T_{k_i}$, так что все указанные в условии задачи ограничения выполнены. При добавлении вершины $v_i$ найдём любую команду $T_j$, такую что не существует вершины $u \in T_j$ and $(v_i, u) \in E(G)$. Полагая $k_i \leq \sqrt{2m}$ это может быть легко реализовано за время $O(\sqrt{2m} + deg(v_i))$ просто с использованием массива булевых пометок и проходом по списку соседей вершины. Если подходящего $T_j$ не существует, то положим $k_{i + 1} = k_i + 1$, то есть создадим для данной вершины отдельную команду. На самом деле, нам не требуется использовать факт про то, что количество команд есть $O(\sqrt{2m})$, поскольку вместо обнуления булевого массива мы можем использовать массив специальных пометок. За время $O(deg(v_i))$ расставим пометки всем соединённым с данной вершиной командам, а потом просто пройдём по массиву до тех пор, пока не найдём непомеченную команду. Разумеется, при выполнении этой части будет просмотрено не более $deg(v_i) + 1$ элементов массива и вообще при добавлении вершины будет сделано $O(deg(v_i))$ действий. Таким образом, суммарное время работы есть $O(n + m)$.↵
↵
### Задача D. Афера.↵
↵
Для начала будем несколько иначе воспринимать все ставки. Определим $c_i = a_i + b_i$, тогда принимая ставку $i$ мы можем считать, что получаем доход $b_i$ и должны будем выплатить $c_i$ в случае наступления соответствующего исхода. Определим $A$ как некоторое подмножество ставок, $S(A) = \sum_{i \in A} b_i$, то есть итоговый доход с данного подмножества без учёта возможных выплат. $L(A)$ положим равному суммарным выплатам, если команда проиграет, то есть $L(A) = \sum_{i \in A, t_i = `L'} c_i$. Аналогично введём величины $D(A)$ и $W(A)$, тогда гарантированный доход Остапа с подмножества $A$ равен $S(A) - max(L(A), D(A), W(A))$.↵
↵
В данном виде пока ещё непонятно как решать задачу, поскольку требуется с одной стороны увеличивать $S(A)$, и минимизировать максимум с другой стороны. Зафиксируем $max(L(A), D(A), W(A)) = k$, тогда задача звучит как: какова максимальная стоимость по $b_i$ подмножества ставок с исходом "поражение" ("ничья", "победа"), которое можно принять так чтобы сумма их $c_i$ не превосходила $k$. Соответствующие значения $dp(type, sum) \rightarrow profit$ можно независимо посчитать для каждого исхода с помощью динамического программирования решающего задачу о рюкзаке. Сложность такого решения будет $O(nL)$, где $L = \sum a_i + b_i$.↵
↵
### Задача E. Случайная величина моды.↵
↵
Сперва рассмотрим решение задачи за время $O(n^2)$ с помощью динамического программирования. Положим $dpleft(i, j)$ равным оптимальному ожидаемому времени в торговом центре, если Глеб уже обошёл все магазины с $i$ по $j$ включительно и сейчас стоит рядом с магазином $i$. Аналогично положим $dpright(i, j)$ равным оптимальному ответу если Глеб обошёл магазины с $i$ по $j$ и стоит около магазина $j$.↵
↵
Мы не будем приводить всех формул в данном разборе, но, например, $dpleft(i, j)$ может быть вычислено как минимум из двух возможных переходов (в $i - 1$ или $j + 1$) следующим образом:↵
$$dpleft(i, j) = min(1 + t_{i - 1} + p_{i - 1} \cdot |i - 1 - x| + dpleft(i - 1, j) \cdot (1 - p_{i - 1})$$, $$(j + 1 - i) + t_{j + 1} + p_{j + 1} \cdot |j + 1 - x| + dpright(i, j + 1) \cdot (1 - p{j + 1}))$$↵
↵
Для ускорения решения задачи заметим, что если не существует магазинов с $p_i = 0$, то мы посетим большое количество магазинов с очень маленькой вероятностью, поскольку уже вероятность в один процент, то есть $0.01$ является достаточно большой. Вероятность посетить $k$ магазинов с $p_i > 0$ и всё ещё не найти подходящий плащ составляет $0.99^k$, что для $k = 5000$ составит порядка $1.5 \cdot 10^{-22}$. используя что $t_i \leq 1000$ и $n \leq 300\,000$ получаем, что на посещение всего торгового центра потребуется не более $10^9$ секунд, то есть уже при $k = 5000$ влияние на ответ составит не более $10^{-12}$. На самом деле, учитывая, что нам разрешается допустить относительную ошибку $10^{-6}$ достаточно будет $k = 3000$.↵
↵
Теперь найдём не более $k$ магазинов с $p_i > 0$ и $i < x$ и не более $k$ магазинов с $p_i > 0$ и $i > x$ (то есть слева и справа от стартового). Далее сожмём магазины с $p_i = 0$ и применим квадратичную динамику. Итоговое время работы составит $O(n + k^2)$.↵
↵
### Задача F. Семь раз отмерь, один раз раздели.↵
↵
Каждой вершине требуется назначить неотрицательное целое число $x_v$ равное номеру итерации описанного в условии процесса, на которой данная вершина будет удалена. По причинам, которые станут понятны читателю в дальнейшем, мы будем считать, что $x_v = 0$ означает удаление на самой последней итерации, то есть б**о**льшие значение $x$ будут соответствовать более ранним итерациям процесса. Можно показать, что фиксированные значения $x_v$ корректно описывают процесс, если и только если для любых двух вершин $u$ и $v$, таких что $x_u = x_v$ максимальное значение $x_w$ по всем $w$ лежащим на пути от $u$ до $v$ больше $x_u$. Другими словами, наличие на любом пути между двумя одинаковыми значениями другого значения, которое больше их обоих, означает, что любые две вершины, удаляемые на одном шаге, будут к этому моменту находиться в разных компонентах.↵
↵
Выберем любую вершину в качестве корня дерева. Обозначим через $C(v)$ множество непосредственных детей вершины $v$, а через $S(v)$~--- поддерево вершины $v$. Теперь, если в поддереве $v$ уже зафиксирована некоторая корректная расстановка значений $x$, то нас интересуют только те $x_u$, $u \in S(v)$, которые ещё никем не перекрыты, то есть на пути от $u$ до вершины корня поддерева (вершины $v$) нет значения больше $x_u$. Через $d(v, mask)$ обозначим булево значение, возможно ли так расставить $x$ в поддереве вершины $v$, чтобы незакрытыми оставались только значения из множества $mask$. Поскольку благодаря центроидной декомпозиции мы знаем, что величина ответа не превзойдёт $\log n$, то интересных значений $mask$ не более $2^{\log n}$, то есть $O(n)$. Значения $d(v, mask)$ можно вычислить если известны $d(u, mask)$ для всех $u \in C(v)$ за время $O(n^3)$ используя следующие соображения (обозначим через $u_1, u_2, \ldots$ детей из $C(v)$, а через $m_1, m_2, \ldots$ рассматриваемые в них значения динамики):↵
↵
1. Значение $x_v$ должно быть больше любого $i$, которое встречается более чем в одной маске $m_i$.↵
2. Значение $x_v$ должно быть равно какому-нибудь $i$, которое не встречается ни в одной $m_i$.↵
3. Если мы положим $x_v = i$, то все $j < i$ будут равны $0$ в $m$.↵
↵
Заметим, что согласно описанному выше процессу если маска $m_1$ является подмаской $m_2$, то она всегда лучше влияет на ответ, чем $m_2$. Теперь мы утверждаем, что если рассмотреть минимальное $m$, такое что $d(v, m) = true$, то для любой $m_1 > m$ найдётся $m_2$ подмаска $m_1$, такая что $d(v, m_2) = true$. В самом деле, рассмотрим первый (старший) бит $i$, в котором $m$ и $m_1$ отличаются. Поскольку $m_1$ больше $m$, то в этой позиции у неё будет записано $1$, а у $m$ будет записан $0$. Если после этого в $m$ вообще нет $1$, то она сама является подмаской $m_1$, в противном случае это означает, что $x_v < i$. Выставим $x_v = i$ и получим подмаску $m_1$.↵
↵
Доказанное выше означает, что достаточно только рассмотреть лексикографически минимальную маску, которую можно получить в каждом из поддеревьев $S(v)$. Для этого будем объединять ответы по всем $u \in C(v)$ используя вышеописанную процедуру. Такое решение может быть легко реализовано за время $O(n \log n)$ или даже $O(n)$ при эффективном использовании битовых операций.↵
↵
The probelm asked to simply simulate the process. One can keep yet unread mails in any data structure (array, deque, set, whatever) and iterate through time. For any moment of time $x$ we first check whether there is a new incoming letter and add it to the structure if that is the case. Now, check if the ``feeling guilty'' condition is satisfied. If so, compute $k$ and remove $k$ oldest letter from the structure. Doing all this in the most straightforward way would result in $O(nT)$ complexity. ↵
↵
↵
Excercise: solve the problem in $O(n)$ time.↵
↵
### Problem B. Lassies Versus Machine.↵
↵
First of all, note that if Dusya and Lusia split $n$ in $x$ and $n - x$ they would get exactly the same set of banknotes as a change as if they split in $x + 5000$ and $n - x - 5000$. That means, we only have to check all possibilities to split from $a$ to $min(a + 5000, n - a)$. For each possibility we compute the change in $O(1)$ time. If some girl wants to pay $y$ the change will be $(5000k - y)~mod~500$, where $k = \lceil \frac{y}{5000} \rceil$.↵
↵
Excercise: prove that it's enough to check only values from $a$ to $min(a + 499, n - a)$.↵
↵
### Problem C. Effecient Management Returns.↵
↵
There are many different approaches for this problem and almost all solutions one can imagine will work as the size of the answer will never exceed $\sqrt{2m}$ (excersise: prove). This editorial contains only one possible linear time solution.↵
↵
Proceed vertices one by one. After we have processed first $i - 1$ vertices ($v_1, v_2, \ldots, v_{i - 1}$) we would like to keep a way to dirstibute them among $k_i$ teams $T_1, T_2, \ldots, T_{k_i}$ that will satisfy all the requirements. When we add a new node $v_i$ we should find any component $T_j$, such that there is no node $u \in T_j$ and $(v_i, u) \in E(G)$. Assuming $k_i \leq \sqrt{2m}$ this can be done in $O(\sqrt{2m} + deg(v_i))$ time by simply making an array of boolean marks and traversing the list of all neighbours. If there is no such $T_j$, we consider $k_{i + 1} = k_i + 1$, i.e. we create a new set for this vertex. However, we actually do not need this $O(\sqrt{2m})$ time to set up the boolean array, as we can use only one array and mark it with a number of iteration instead of a simple \emph{true}. Thus, we set marks in $O(deg(v_i))$ time and then simply consider all sets one by one till we find first valid. Obviously, we will skip no more then $deg(v_i)$ sets till we find first possible match, thus the running time will be $O(deg(v_i))$ and the total running time is $O(n + m)$.↵
↵
### Problem D. The Sting.↵
↵
First of all we would like to slightly change how we treat a bet. Define $c_i = a_i + b_i$. Now, if we accept the $i$-th bet we immediately take $b_i$ and then pay back $c_i$ in case this bet plays. Define as $A$ some subset of bets, $S(A) = \sum_{i \in A} b_i$, i.e. the total profit we get from subset $A$. Define as $L(A)$ the total amount we will have to pay in case the game result will be "team looses", i.e. $L(A) = \sum_{i \in A, t_i = `L'} c_i$. Similarly we introduce $D(A)$ and $W(A)$. Now, the profit of Ostap if he accepts subset $A$ is $S(A) - max(L(A), D(A), W(A))$.↵
↵
In this form it's not clear how to solve the problem as we simultaneously want to maximize $S(A)$ from the one hand, but minimize maximum from the other hand. If we fix the value $max(L(A), D(A), W(A)) = k$ the problem will be, what is the maximum possible sum of $b_i$ if we pick some subset of "loose" ("draw", "win") bets with the sum of $c_i$ not exceeding $k$. Such values $dp(type, sum) \rightarrow profit$ can be computed for each outcome independetly using knapsack dynamic programming. The complexity of such solution is $O(nL)$, where $L = \sum a_i + b_i$.↵
↵
### Problem E. Random Value of Mode.↵
↵
To start with consider $O(n^2)$ dynamic programming solution. Let $dpleft(i, j)$ be the optimum expected value if Gleb has visited all shops on segment from $i$ to $j$ inclusive and is now standing near the shop $i$. In the same way $dpright(i, j)$ as the optimum expected value if segment from $i$ to $j$ was visited and Gleb stands near shop $j$.↵
↵
We are not going to consider all the formulas there, but here is how we compute $dpleft(i, j)$, picking the minimum of two possibilities go left or go right:↵
$$dpleft(i, j) = min(1 + t_{i - 1} + p_{i - 1} \cdot |i - 1 - x| + dpleft(i - 1, j) \cdot (1 - p_{i - 1})$$, $$(j + 1 - i) + t_{j + 1} + p_{j + 1} \cdot |j + 1 - x| + dpright(i, j + 1) \cdot (1 - p{j + 1}))$$↵
↵
To move forward we should have a guess that if there are no $p_i = 0$ we are going to visit many shops with a really small probability. Indeed, the smallest possible positive probability is one percent, that is $0.01$ which is pretty large. The probability to visit $k$ shops with $p_i > 0$ and not find a proper coat is $0.99^k$, that for $k = 5000$ is about $1.5 \cdot 10^{-22}$. Assuming $t_i \leq 1000$ and $n \leq 300\,000$ the time required to visit the whole mall is not greater than $10^9$, thus for $k = 5000$ it will affect the answer by less than $10^{-12}$. Actually, assuming we only need relative error $k = 3000$ will be sufficient.↵
↵
Now, we find no more than $k$ shops with $p_i > 0$ and $i < x$ and no more than $k$ shops with $p_i > 0$ and $i > x$. Compress shops with $p_i = 0$ between them and compute quaratic dynamic programming. The overall running time will be $O(n + k^2)$.↵
↵
### Problem F. Measure Twice, Divide Once.↵
↵
We need to assign each vertex a single positive integer $x_v$~--- the number of the process iteration when this vertex will be deleted. For the reason that will be clear soon we will consider $x_v = 0$ to stand for the last iteration, i.e. the greater value of $x$ correspond to the earlier iterations of the process. One can prove that an assignment of positive integers $x_v$ is correct if and only if for any two vertices $u$ and $v$ such that $x_u = x_v$ the maximum value of $x_w$ for all $w$ on the path in the tree from $u$ to $v$ is greater than $x_u$. That is necessary and sufficient condition for any two vertices removed during one iteration to be in different components.↵
↵
Pick any node as a root of the tree. Denote as $C(v)$ the set of direct children of $v$ and as $S(v)$~--- the subtree of node $v$. Now, after we set values of $x$ in a subtree $v$ we only care about different values of $x_u$, $u \in S(v)$ that are not "closed", i.e. there is no value greater between the corresponding node and the root of a subtree (node $v$). Denote as $d(v, mask)$ boolean value whether it's possible to set values of $x$ in a subtree of node $v$ to have values $mask$ unclosed. Because of centroid decomposition we know there is no need to use values of $x$ greater than $\log n$, thus there are no more than $O(2^{\log n})$ different values of mask, i.e. $O(n)$. $d(v, mask)$ can be recomputed if we know $d(u, mask)$ for all $u \in C(v)$ in $O(n^3)$ time. Indeed, if one child $u_i$ uses mask $m_i$ we know:- ↵
↵
1. We have to set $x_v$ greater than any $i$ that occurs in more than one mask.↵
2. We can set $x_v$ to any $i$ that doesn't occur in any $m_i$.↵
3. If we set $x_v = i$, all $j < i$ are set to $0$ in $m$.↵
↵
Now, one can notices that according to the following process if mask $m_1$ is a submask of $m_2$ it is always better lexicographically smaller than mask $m_2$ it always affects the result in a better way. Now, we claim that if for some subtree $v$ we consider the minimum possible $m$, such that $d(v, m)$ is true, for each $m_1 > m$ there exists $m_2$ submask of $m_1$ such that $d(v, m_2)$ is true. Indeed, consider the first (highest) bit $i$ where $m$ and $m_1$ differ. Because $m_1$ is greater than $m$ it will have $1$ at this position, while $m$ will have $0$. If there is no $1$ in $m$ anymore it is itself a submask of $m_1$, otherwise, this means $x_v < i$. We can set $x_v = i$ and obtain a submask of $m_1$.↵
↵
The above means we should only care about obtaining a lexicographically smallest mask for each subtree $S(v)$. To do this we use the above rules to merge the results in all $u \in C(v)$. This can be easily done in $O(n \log n)$ or in $O(n)$ if one uses a lot of bitwise operations
↵
В данной задаче требовалось просто просимулировать описанный в условии процесс. Например, можно в любой структуре данных (массив, очередь, дерево) поддерживать множество ещё не обработанных писем и по очереди рассматривать все моменты времени. При рассмотрении момент времени $x$ сначала проверяем, есть ли новое входящее письмо, и, если да, то добавляем его в структуру. Далее проверяем, не наступило ли хотя бы одно из условий, при которых Бомбослава разбирает почту. Для симулирования разбора почты вычисляем число $k$ и последовательно вынимаем $k$ наиболее старых писем из структуры. Даже самая простая реализация этого процесса будет работать за время $O(nT)$.↵
↵
Упражнение: решите задачу за время $O(n)$.↵
↵
### Задача B. Девчата против автомата.↵
↵
Для начала заметим, что если Дуся и Люся поделят число $n$ на $x$ и $n - x$, то они получат в качестве сдачи ровно такой же набор банкнот, как если поделят $n$ на $x + 5000$ и $n - x - 5000$. Таким образом, достаточно будет только проверить всем способы разбиения, где $x$ проходит диапазон от $a$ до $min(a + 5000, n - a)$. Для каждого способа вычислим сдачу за время $O(1)$ по следующей формуле: если какая-либо из девушек хочет заплатить величину $y$, то размер полезной сдачи будет $(5000k - y)~mod~500$, где $k = \lceil \frac{y}{5000} \rceil$.↵
↵
Упражнение: докажите, что достаточно перебрать значения $x$ в диапазоне от $a$ до $min(a + 499, n - a)$ включительно.↵
↵
### Задача C. Эффективный менеджмент возвращается.↵
↵
Существует множество различных решений данной задачи, и почти любое из них уложится в ограничение по времени, поскольку в ответе будет использовано не более $\sqrt{2m}$ команд (упражнение: доказать это утверждение). Данный разбор будет содержать описание одного из возможных линейных решений.↵
↵
Будем добавлять вершины графа по одной. После рассмотрения первых $i - 1$ вершин ($v_1, v_2, \ldots, v_{i - 1}$) мы будем поддерживать распределение их между $k_i$ командами $T_1, T_2, \ldots, T_{k_i}$, так что все указанные в условии задачи ограничения выполнены. При добавлении вершины $v_i$ найдём любую команду $T_j$, такую что не существует вершины $u \in T_j$ and $(v_i, u) \in E(G)$. Полагая $k_i \leq \sqrt{2m}$ это может быть легко реализовано за время $O(\sqrt{2m} + deg(v_i))$ просто с использованием массива булевых пометок и проходом по списку соседей вершины. Если подходящего $T_j$ не существует, то положим $k_{i + 1} = k_i + 1$, то есть создадим для данной вершины отдельную команду. На самом деле, нам не требуется использовать факт про то, что количество команд есть $O(\sqrt{2m})$, поскольку вместо обнуления булевого массива мы можем использовать массив специальных пометок. За время $O(deg(v_i))$ расставим пометки всем соединённым с данной вершиной командам, а потом просто пройдём по массиву до тех пор, пока не найдём непомеченную команду. Разумеется, при выполнении этой части будет просмотрено не более $deg(v_i) + 1$ элементов массива и вообще при добавлении вершины будет сделано $O(deg(v_i))$ действий. Таким образом, суммарное время работы есть $O(n + m)$.↵
↵
### Задача D. Афера.↵
↵
Для начала будем несколько иначе воспринимать все ставки. Определим $c_i = a_i + b_i$, тогда принимая ставку $i$ мы можем считать, что получаем доход $b_i$ и должны будем выплатить $c_i$ в случае наступления соответствующего исхода. Определим $A$ как некоторое подмножество ставок, $S(A) = \sum_{i \in A} b_i$, то есть итоговый доход с данного подмножества без учёта возможных выплат. $L(A)$ положим равному суммарным выплатам, если команда проиграет, то есть $L(A) = \sum_{i \in A, t_i = `L'} c_i$. Аналогично введём величины $D(A)$ и $W(A)$, тогда гарантированный доход Остапа с подмножества $A$ равен $S(A) - max(L(A), D(A), W(A))$.↵
↵
В данном виде пока ещё непонятно как решать задачу, поскольку требуется с одной стороны увеличивать $S(A)$, и минимизировать максимум с другой стороны. Зафиксируем $max(L(A), D(A), W(A)) = k$, тогда задача звучит как: какова максимальная стоимость по $b_i$ подмножества ставок с исходом "поражение" ("ничья", "победа"), которое можно принять так чтобы сумма их $c_i$ не превосходила $k$. Соответствующие значения $dp(type, sum) \rightarrow profit$ можно независимо посчитать для каждого исхода с помощью динамического программирования решающего задачу о рюкзаке. Сложность такого решения будет $O(nL)$, где $L = \sum a_i + b_i$.↵
↵
### Задача E. Случайная величина моды.↵
↵
Сперва рассмотрим решение задачи за время $O(n^2)$ с помощью динамического программирования. Положим $dpleft(i, j)$ равным оптимальному ожидаемому времени в торговом центре, если Глеб уже обошёл все магазины с $i$ по $j$ включительно и сейчас стоит рядом с магазином $i$. Аналогично положим $dpright(i, j)$ равным оптимальному ответу если Глеб обошёл магазины с $i$ по $j$ и стоит около магазина $j$.↵
↵
Мы не будем приводить всех формул в данном разборе, но, например, $dpleft(i, j)$ может быть вычислено как минимум из двух возможных переходов (в $i - 1$ или $j + 1$) следующим образом:↵
$$dpleft(i, j) = min(1 + t_{i - 1} + p_{i - 1} \cdot |i - 1 - x| + dpleft(i - 1, j) \cdot (1 - p_{i - 1})$$, $$(j + 1 - i) + t_{j + 1} + p_{j + 1} \cdot |j + 1 - x| + dpright(i, j + 1) \cdot (1 - p{j + 1}))$$↵
↵
Для ускорения решения задачи заметим, что если не существует магазинов с $p_i = 0$, то мы посетим большое количество магазинов с очень маленькой вероятностью, поскольку уже вероятность в один процент, то есть $0.01$ является достаточно большой. Вероятность посетить $k$ магазинов с $p_i > 0$ и всё ещё не найти подходящий плащ составляет $0.99^k$, что для $k = 5000$ составит порядка $1.5 \cdot 10^{-22}$. используя что $t_i \leq 1000$ и $n \leq 300\,000$ получаем, что на посещение всего торгового центра потребуется не более $10^9$ секунд, то есть уже при $k = 5000$ влияние на ответ составит не более $10^{-12}$. На самом деле, учитывая, что нам разрешается допустить относительную ошибку $10^{-6}$ достаточно будет $k = 3000$.↵
↵
Теперь найдём не более $k$ магазинов с $p_i > 0$ и $i < x$ и не более $k$ магазинов с $p_i > 0$ и $i > x$ (то есть слева и справа от стартового). Далее сожмём магазины с $p_i = 0$ и применим квадратичную динамику. Итоговое время работы составит $O(n + k^2)$.↵
↵
### Задача F. Семь раз отмерь, один раз раздели.↵
↵
Каждой вершине требуется назначить неотрицательное целое число $x_v$ равное номеру итерации описанного в условии процесса, на которой данная вершина будет удалена. По причинам, которые станут понятны читателю в дальнейшем, мы будем считать, что $x_v = 0$ означает удаление на самой последней итерации, то есть б**о**льшие значение $x$ будут соответствовать более ранним итерациям процесса. Можно показать, что фиксированные значения $x_v$ корректно описывают процесс, если и только если для любых двух вершин $u$ и $v$, таких что $x_u = x_v$ максимальное значение $x_w$ по всем $w$ лежащим на пути от $u$ до $v$ больше $x_u$. Другими словами, наличие на любом пути между двумя одинаковыми значениями другого значения, которое больше их обоих, означает, что любые две вершины, удаляемые на одном шаге, будут к этому моменту находиться в разных компонентах.↵
↵
Выберем любую вершину в качестве корня дерева. Обозначим через $C(v)$ множество непосредственных детей вершины $v$, а через $S(v)$~--- поддерево вершины $v$. Теперь, если в поддереве $v$ уже зафиксирована некоторая корректная расстановка значений $x$, то нас интересуют только те $x_u$, $u \in S(v)$, которые ещё никем не перекрыты, то есть на пути от $u$ до вершины корня поддерева (вершины $v$) нет значения больше $x_u$. Через $d(v, mask)$ обозначим булево значение, возможно ли так расставить $x$ в поддереве вершины $v$, чтобы незакрытыми оставались только значения из множества $mask$. Поскольку благодаря центроидной декомпозиции мы знаем, что величина ответа не превзойдёт $\log n$, то интересных значений $mask$ не более $2^{\log n}$, то есть $O(n)$. Значения $d(v, mask)$ можно вычислить если известны $d(u, mask)$ для всех $u \in C(v)$ за время $O(n^3)$ используя следующие соображения (обозначим через $u_1, u_2, \ldots$ детей из $C(v)$, а через $m_1, m_2, \ldots$ рассматриваемые в них значения динамики):↵
↵
1. Значение $x_v$ должно быть больше любого $i$, которое встречается более чем в одной маске $m_i$.↵
2. Значение $x_v$ должно быть равно какому-нибудь $i$, которое не встречается ни в одной $m_i$.↵
3. Если мы положим $x_v = i$, то все $j < i$ будут равны $0$ в $m$.↵
↵
Заметим, что согласно описанному выше процессу если маска $m_1$ является подмаской $m_2$, то она всегда лучше влияет на ответ, чем $m_2$. Теперь мы утверждаем, что если рассмотреть минимальное $m$, такое что $d(v, m) = true$, то для любой $m_1 > m$ найдётся $m_2$ подмаска $m_1$, такая что $d(v, m_2) = true$. В самом деле, рассмотрим первый (старший) бит $i$, в котором $m$ и $m_1$ отличаются. Поскольку $m_1$ больше $m$, то в этой позиции у неё будет записано $1$, а у $m$ будет записан $0$. Если после этого в $m$ вообще нет $1$, то она сама является подмаской $m_1$, в противном случае это означает, что $x_v < i$. Выставим $x_v = i$ и получим подмаску $m_1$.↵
↵
Доказанное выше означает, что достаточно только рассмотреть лексикографически минимальную маску, которую можно получить в каждом из поддеревьев $S(v)$. Для этого будем объединять ответы по всем $u \in C(v)$ используя вышеописанную процедуру. Такое решение может быть легко реализовано за время $O(n \log n)$ или даже $O(n)$ при эффективном использовании битовых операций.↵
