Максимальный поток минимальной стоимости с алгоритмом Левита прошел вообще за 300 мс.

ссылка на посылку

Я прочитал условие. Там всё хорошо написано. Мне кажется, это один из важных навыков, которые дают эти соревнования — сесть, напрячься и прочитать технический текст формально и максимально естественно. Поверьте, и техническая документация к требования ПО бывает сложной и в computer science есть много текстов, которые надо суметь прочитать.

Допустим у нас есть массив (пусть изначально из нулей), и нам нужно обработать кучу запросов вида прибавить на подотрезке [l, r] величину x, и в конце вывести результирующий массив. Это можно сделать следующим образом: a[l] += x, a[r+1] -= x. Так обрабатываем каждый запрос, а в конце накапливаем префикс суммы a[i] += a[i-1]. В этой же задаче можно сделать аналогично, только вместо массива у нас будет стек дфса (в нем в каждый момент будут лежать все предки), и префикс суммы будем накапливать в обратную сторону.

Еще это можно переформулировать немного иначе: ответ в вершине V равен сумме ответов ее детей минус количество вершин, для которых вершина V — первый предок, который не получит +1. Таким образом мы для каждой вершины бинпоиском находим первого предка, который не получит +1, и делаем в его ответе -1.

Второе авторское было таким же) Вот

Но кода в нем получилось намного больше, и писал я его дольше, так что как основное авторское использовал решение с ДО.

You only store the (2^k)th ancestors of a node -> O(n*log n)

This is the binary search method that may not be the easiest, I recommend checking out zawini54's comment too!

A few observations could be made:

1. dist(v, u) = dist(root, u) - dist(root, v)
2. for any vertex v, and its ancestors a₁, a₂, ..., a_i,
   a₁ being the furtherest ancestor (root of the tree) and a_i the closest (immediate parent vertex),
   we can see that dist(root, a₁) < dist(root, a₂) < ... < dist(root, a_i) < dist(root, v), a sorted sequence that is binary searchable.
3. for each vertex v, we want to find the number of vertices u it controls, i.e.:
   dist(v, u) ≤ value(u) dist(root, u) - dist(root, v) ≤ value(u) dist(root, u) - value(u) ≤ dist(root, v)
4. with #2 and #3 in mind, let's try to think of this problem in another way: for each vertex u, which vertices v could control u?

Nice approach, btw are you making reference to the technique disscused at this post?

I considered merging set approach during contest, but couldn't find a way to count the number of elements <= d in O(logn) using std::set, now I know it's unnecesary for this problem after reading you code.
However, if the condition change to that v controls u if dist(v, u) <= a(v) (instead of a(u)), it seems we must have a way to count the number of elements <= d in O(logn) using merging set approach, and std::set doesn't satisfy this.

An explanation please?

Hi,your approach looks amazing, I just learned binary lifting through this problem and now you propose another way of doing the problem... Where did you learn this technique from, I want to learn this too,is there some blog post associated with it , or some source where I can learn the merging set technique,because I cant understand your solution , can you also explain it just a little..?

Thanks a ton!

Beautiful solution!

This question just keeps on giving :>

So explanation on the DSU on tree method to solve this problem (Alyona And Tree):

There's a basic HLD (heavy light decomposition) concept of light child and heavy child in a tree for each node.So, consider you have a node $$$N$$$, which has $$$\alpha$$$ children, $$$C_1,C_2,C_3,...,C_{\alpha}$$$. Now, the child, which has the maximum size of it's subtree, is the one which is called the big child or the heavy child. Every other child is called a light child.

How is this concept useful?

So, for a node, consider, you need to perform some query that needs information from the whole tree, then in that case, if you do a brute force operation, then you'll get a $$$O(n^2)$$$ time complexity. What we can do here, is store the information of the big child while the traversal is done, and for the rest of the children, we do whatever we did in the brute force method.

How does that help us?

Basically we're not going into the big child, but are going into the light children. Consider this, if $$$x=tree[lightchild].size()$$$ and $$$y=tree[bigchild].size()$$$. So, $$$y > x$$$, obviously. So, if I merge the subtree of the lightchild into the subtree of the bigChild, then it's size: $$$y+x > x+x = 2\times x$$$. That is, each merge operation will, at least, double the size of the bigchild subtree. So, we can do this doubling operation only until the total number of elements ($$$=n$$$) is reached. That is, $$$log(n)$$$ times.

And since we have $$$n$$$ nodes in total, the total time complexity is $$$O(n log n)$$$.

You can learn more about DSU on graphs, here and here.

Steps for the algorithm:

1. For a node, find the bigChild.

2. DFS through the lightChilds, and do not remember their results

3. DFS through the bigChild, and remember it's result

4. Add the result of the current node, if possible.

5. Add the values of the subtrees of the lightChilds.

6. At this point, we have the result for the node

7. Remove the values of the lightChilds if the current node is a light child, else do not delete them

This is the procedure, I understood from the tutorial.

Now let's try to analyze szawinis' solution. Here we are not keeping results in some variable array or something, therefore there is no removal of values at the end of the DFS. That is, we can keep the subtree information intact, while traversing the tree. So priority queue pq stores the $$$\text{distance from root}-a[v]$$$ value for the nodes that satisfy the condition. That is for the node node, pq[node] will have the mentioned difference for the nodes which satisfy the condition (d[child]-d[node]<=a[child]).

In the big for loop, if we see a light child, we push all it's values into the current node's pq. Whereas, if we see a potential bigChild, we push all the elements of the current node into the bigChild's pq and then point to the bigChild's pq as the current node's pq.

The point is, not to transfer the elements of the big child (which actually makes the algorithm run in O(nlog n)). Then we disregard the elements which do not satisfy the condition. If you think that's a problem, then think how many elements in total can you remove? So yeah this can, at max n elements, because only the elements that satisfy the condition for the current node, are percolated up as potential candidates.

At this point, you can take the value of pq[node].size() as the answer. And then add the node itself in it's priority queue.

I hope this helps.

My Code 22652723

easy to understand

That is not correct. Let me clarify a part of the editorial's proof for archival reasons.

Assume that the pokemons have been sorted in descending order of $$$u_i$$$, therefore $$$u_0 >= u_1 >= u_2 >= .... u_{n-1}$$$. Now, let $$$i$$$ be the index of the last pokemon to be thrown an ultraball.

Claim: For all pokemon in $$$[0, ... i - 1]$$$, we throw a ball at them (or perhaps two).

Proof: Assume that there was a pokemon, say $$$x$$$, where $$$0 <= x < i$$$, and we don't throw a ball at $$$x$$$. But note that we do throw a ultraball at $$$i$$$. What is the total change if we throw that ultraball at $$$x$$$ instead?

Case 1: We do not also throw a pokeball at $$$i$$$:
— Loss in not throwing the ultraball at $$$i$$$ = $$$u_i$$$
— Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
Since $$$u_x >= u_i$$$, we can throw the ultraball at $$$x$$$ and not be worse.

Case 2: We do also throw a pokeball at $$$i$$$.
— Loss in not throwing the ultraball at $$$i$$$ = $$$(u_i + p_i - p_{i}u_{i} - p_i) = u_i(1-p_i)$$$
— Gain in throwing the ultraball at $$$x$$$ = $$$u_x$$$.
Since $$$u_x >= u_i >= u_i(1-p_i)$$$, we can throw the ultraball at $$$x$$$ and not be worse.

Hence Proved

Yeah, I also think so

"The mex of a set S is a minimum possible non-negative integer that is not in S."

if you fill array with max value your ans will be 0