Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
6 | adamant | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Название |
---|
Во время контеста я пришёл к следующему решению задачи E, но не смог его достаточно эффективно реализовать.
Создадим сеть с 4 + n вершинами: сток t, исток s, две вершины x и y, которые отвечают шарам разных типов, а также n вершин на каждого покемона. Проведём рёбра из s в x и y нулевой стоимости и пропускных способностей a и b соответственно. Из x проведём рёбра единичной пропускной способности во всех покемонов, со стоимостями ( - pi). Аналогично, из y проведём рёбра с единичной пропускной способностью и стоимостью ( - ui).
Мы хотим пустить поток величины a + b в сети, минимизировав стоимость. Заметим, что если в i-ого покемона выстрелить обоими шарами, вероятность того, что он будет повержен, равна 1 - (1 - pi)(1 - ui) = pi + ui - piui. Значит, нужно каким-то образом прибавить к общей стоимости piui в случае, если в покемона выстрелили обоими шарами.
Для этого из каждого покемона проведём в сток два ребра: одно пропускной способности 1 и стоимости 0, второе — способности 1 и стоимости piui. Оптимальный поток либо будет течь по верхнему ребру, если в i-ого покемона втекает единица потока, либо по обоим, увеличивая стоимость на нужную величину.
Стало быть, модуль минимальной стоимости максимального потока в такой сети равен ответу. В сети O(N) вершин и рёбер, поток есть O(N). Форд-Беллман получил TL, Дейкстра должна зайти.
UPD: Дейкстра зашла после замены long double на double. Форд-Беллману это не помогло...
Максимальный поток минимальной стоимости с алгоритмом Левита прошел вообще за 300 мс.
ссылка на посылку
Честно говоря задача "739A — Алёна и mex" очень запутанно написана. Не то что я не смог ее решить, я вообще не понял о чем речь.
Я прочитал условие. Там всё хорошо написано. Мне кажется, это один из важных навыков, которые дают эти соревнования — сесть, напрячься и прочитать технический текст формально и максимально естественно. Поверьте, и техническая документация к требования ПО бывает сложной и в computer science есть много текстов, которые надо суметь прочитать.
Я понимаю что немного запутать это часть соревнования. Меня сильно смутило это предложение.
"Назовем подмассивом некоторую последовательность из подряд идущих чисел в массиве."
Что значит подряд идущих чисел? Если числа просто рядом стоят разве это не подряд идущие числа? То есть под это условие по-моему подходит просто любые числа подряд идущие. Почему я не могу взять просто "10000 10000 10000 10000 10000"?
Если кто-то мне объяснит как это понять буду очень признателен.
А в чем разница между "подряд идущими" и "рядом стоящими", кроме того, что первые "идут", а вторые "стоят", и как вы понимаете это относительно чисел массива?)
Я понимаю, когда у новичков возникают проблемы с пониманием фраз "минимизировать максимум / максимизировать минимум", но такую проблему не понимаю.
Видимо я не очень владею терминологией и не вижу различий. Если предположить что "подряд идущие" это возрастающая или убывающая последовательность, где числа идут одно за другим. "1 2 3 2 1"
То как сюда вписывается пример "5 2 0 1"?
Подряд идущие не значит возрастающие или убывающие. Это означает что мы берем подпоследовательность элементов без пропусков. То есть все элементы с i-го по j-й. Иногда в задачах идет речь о подпоследовательностях общего вида, то есть в такие подпоследовательности попадают элементы, которые не обязательно идут подряд (например, каждый третий).
Кто-то может объяснить "Алёна и дерево" более подробно? Я понял что нужно найти высоту всех вершин, и что бинпоиском можно найти предков которые получат +1, но я не понял как заполнить эти +1 всем предкам?
Допустим у нас есть массив (пусть изначально из нулей), и нам нужно обработать кучу запросов вида прибавить на подотрезке [l, r] величину x, и в конце вывести результирующий массив. Это можно сделать следующим образом:
a[l] += x, a[r+1] -= x.
Так обрабатываем каждый запрос, а в конце накапливаем префикс суммыa[i] += a[i-1]
. В этой же задаче можно сделать аналогично, только вместо массива у нас будет стек дфса (в нем в каждый момент будут лежать все предки), и префикс суммы будем накапливать в обратную сторону.Еще это можно переформулировать немного иначе: ответ в вершине V равен сумме ответов ее детей минус количество вершин, для которых вершина V — первый предок, который не получит +1. Таким образом мы для каждой вершины бинпоиском находим первого предка, который не получит +1, и делаем в его ответе -1.
Теперь все понял, спасибо!
Для каждой вершины нужно делать свой бинпоиск? Если да, то я не совсем понимаю, на каком множестве?
Да, для каждой вершины бинпоиск свой, это бинпоиск по всем предкам этой вершины. Если отсортировать предков по глубине, можно заметить, что чем выше находится предок, тем больше расстояние от вершины до него :) Поэтому можно бинпоиском найти самого высокого предка, расстояние до которого не больше a[x].
В целом я понимаю, что бинпоиск надо делать по всем предкам)
Но мы же не можем хранить для каждой вершины список ее предков явно. Или мы бинпоиск делаем прямо в процессе обхода дерева?
Как вариант, можно поддерживать в дфсе стек вершин, которые мы посетили, но из которых еще не успели выйти. Легко заметить, что в этом стеке и будут храниться все предки, при чем уже отсортированные по глубине.
Осознать, спасибо!
Для каждой вершины надо хранить 1, 2, 4, 8 и т.д. предков. С этой инфой можно восстановить любого предка за логарифм.
О, вот это очень интересно, спасибо за идею!
В задаче 739B можно построить эйлеров обход и находить кол-во вершин x, h[x] — a[x] <= h[v] в поддереве c помощью дерева отрезков.
Я придумал другое решение Div1C, оно мне кажется немного проще авторского.
Как и в разборе, сначала перейдём к частичным разностям и массиву +1/0/-1. Теперь заведём сет отрезков вида +1 +1 ... -1 -1, максимальных по включению (т.е. таких, что в них ничего нельзя добавить ни слева, ни справа). Кроме этого, будем держать мультисет длин таких отрезков.
Теперь при изменении одной позиции можно понять, в каком отрезке она сейчас лежит, и при необходимости разделить отрезок на два или склеить его со следующим/предыдущим.
Второе авторское было таким же) Вот
Но кода в нем получилось намного больше, и писал я его дольше, так что как основное авторское использовал решение с ДО.
Could someone please look at my code for 739B? I was getting WA on pretest 15 and am not sure why...
I store the 2^k ancestors and the distance to them in bparent[][] and bdist[][]. I then binary search for each node that controls the node that I am on and store the start and end segments in event[]. The function solve() dfs's through the tree, keeping track of how many nodes each node controls.
Thanks!
For problem D, how do we store the ancestors of all nodes in O(n)?
You only store the (2^k)th ancestors of a node -> O(n*log n)
Can someone explain the approach for the problem 'Alyona and Tree'
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:
a1 being the furtherest ancestor (root of the tree) and ai the closest (immediate parent vertex),
we can see that dist(root, a1) < dist(root, a2) < ... < dist(root, ai) < dist(root, v), a sorted sequence that is binary searchable.
dist(v, u) ≤ value(u) dist(root, u) - dist(root, v) ≤ value(u) dist(root, u) - value(u) ≤ dist(root, v)
Ok, for each vertex u, I can find how many ancestor controls it, but how do I use this information to find out the reverse?
this can be maintained using segment tree on the path from root to current vertex
Let u is controlled by x vertices. Then the immediate x parents of u could control this vertex u.
But a simple approach in getting the answer requires O(n^2) which would fail on the time limit. Can you suggest a better approach?
Consider the array, A = [6, 1, 6, 9, 3]
We can compute an array of differences between the neighbouring two elements, a difference array, D = [6, - 5, 5, 3, - 6],
Note how we can reconstruct the array A from its difference array D,
A[0] = D[0]
A[1] = D[0] + D[1]
A[2] = D[0] + D[1] + D[2]
A[3] = D[0] + D[1] + D[2] + D[3]
A[4] = D[0] + D[1] + D[2] + D[3] + D[4]
If we can somehow first construct a difference "array" D for this problem, then we can reconstruct the answer "array" A from it.
Sorry, I still do not get it. How do you get this difference array?
Actually there's another solution that doesn't use binary lifting, but the merging sets technique. I think it's easier, because at first I thought of doing something with binary lifting but wasn't able to come up with anything. Check it out: 22490570
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.
Actually, I don't think my approach works with the harder version of the problem, since it relies on that fact that d(v) is monotonically increasing as you go down the tree. I think there should be a solution involving segment tree and coordinate compression, but I haven't thought about it that much. Please feel free to correct me on anything.
But Ordered Statistics Tree does. Can't we use it instead of sets?
An explanation please?
my solution using ordered statistics
This is Amazing. Thanks a lot I'm definitely gonna remember this after-before strategy! I had a few situations where I needed this and this was pretty neat.
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!
Article on the merging sets technique
For anyone looking for a binary lifting solution: here it is
Explanation to the binary lifting solution:
The base idea can be seen here. We just don't use the binary search over the ancestors of a node.
We create the parent's DP, that is required to do binary lifting. I saw this video to understand binary lifting. You create an 2D matrix with dims:
DP[N][HEIGHT]
, where DP[i][j] represents the parent of $$$i^{th}$$$ node at height $$$2^j$$$ from $$$i$$$.DP[i][0]
is simply the direct parent of the node, already given in the question. For the others, use this:Where
j
is the height, andi
is the node. If you're confused, watch the video.Now, we remove the binary search part, and instead do the search using the parent
DP
matrix we created.This can be done using:
This is what I stole from yaksha. Thenks. What does it mean tho?
It finds the farthermost parent of s, that satisfies the condition. Let's name it $$$\phi$$$. But we're iterating through the powers of 2. That is, it is possible that a parent at an height of $$$2^j$$$ from $$$s$$$, might satisfy the condition, but we didn't see $$$2^{j+1}-2^{j}$$$ elements between the two parents.
So, we'll have to iterate through the parents of $$$\phi$$$. But do we have to start again? No. We know that $$$2^{j+1}$$$th parent didn't satisfy, whereas $$$2^j$$$ did. So, we have a gap of $$$2^{j+1}-2^j = 2^j$$$ elements. So, we look into the $$$j^{th}$$$ parent of $$$\phi$$$ this time. This gap closes as we progress towards
d=0
.Everything else is pretty much the same.
Here is my submission, made from multiple code stealing activities.
Hey, thanks a lot! your comment helped to finally understand
Great!
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:
For a node, find the
bigChild
.DFS through the
lightChild
s, and do not remember their resultsDFS through the
bigChild
, and remember it's resultAdd the result of the current node, if possible.
Add the values of the subtrees of the
lightChild
s.At this point, we have the result for the
node
Remove the values of the
lightChild
s if the current node is a light child, else do not delete themThis 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 nodenode
,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'spq
. Whereas, if we see a potential bigChild, we push all the elements of the current node into the bigChild'spq
and then point to the bigChild'spq
as the current node'spq
.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.
Can someone please elaborate the binary lifting method for problem D?
My Code 22652723
easy to understand
Instead of binary lifting, I think you're using binary search in here.
For everyone trying to understand Sukeesh's solution, here is an explanation:
Basic what we knows:
$$$dist(u,v) = dist(root,v)-dist(root,u)$$$. We're given the condition: $$$dist(u,v) \leq a_i$$$, which can be written now as $$$dist(root,v)-dist(root,u) \leq a_i$$$ (where $$$u$$$ is an ancestor of $$$v$$$).
If you're looking at vertex $$$v$$$, then it's ancestors' distances from the root, will be in strictly increasing order, starting from the root itself. That is, if $$$a_1,a_2,a_3,...,a_i$$$ are the ancestors of $$$v$$$, where $$$a_1$$$ is the root, and $$$a_i$$$ is the parent of $$$v$$$, then the distance of this series of nodes, from the root, will be in strictly increasing order. Thus we can do a binary search on them.
So let's see the algorithm. We're doing a DFS here.
Consider we're at the vertex $$$v$$$, and we have the information of it's ancestors saved in an
vector
$$$arr$$$. We're saving the distance of a node from the root in the array $$$d$$$, while we're going down while the DFS. So while we're at $$$v$$$, we have the distance of it's ancestors from the root already saved in $$$d$$$.Great.
Now we look for the first ancestor $$$a$$$ which doesn't satisfy the condition:
We can calculate the LHS of this formula for our $v$ boi, and then we can search for this value in $$$arr$$$. Let's say this value's index is $$$hi$$$. So, bringing partial sums in here fam.
This part is good. So what do we have here? We can say that all ancestors of $$$v$$$ after $$$hi$$$ (including $$$hi$$$) till the parent of $$$v$$$ satisfy the condition, right?
We're saving the partial sums in an array
dp
.So as done in partial sums, we do
dp[par[v]]++
anddp[par[arr[hi]]--
. You'll understand this is you know about partial sums. We increase the starting of a segment, and decrease after the end of it.Now we carry on to our DFS work.
We do all this,and do complete our DFS from the root.
Now we can compute the answer of each node, by using the partial sums we built during the first DFS (oh no, there's no second DFS, yet).
So, we calculate the answer for each node, in the same way, we created the
dp
array(i.e. going through a DFS). So we calculate thedp
value for the children first, and then use it to calculate the value of the parent, by adding the childrendp
values in the parentdp
value. The functiongo
is used to do that.Why is this working you ask? Consider a positive value is encountered. This means that this is a starting point for a segment of nodes which have some node $$$v$$$ for which the needed condition is satisfied. Thus we increase our
dp
value. If a negative value is encountered, we know that some segment has ended, and we decrease ourdp
value.Hope this helps someone.
In 739E — Gosha is hunting, The editorial writes "Not hard to prove that in group Y we should throw Poke Balls to Pokemons with greatest u - p." I think that we want to maximize PokeBalls probability when we throw PokeBalls. So shouldn't we throw pokeballs to pokemons with greatest p-u?
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
Can you explain the Loss in case 2 proofbycontradiction? Does it mean that (ui + pi) -> either ultraball catches the pokemon or pokeball catches it. and (uipi + pi) -> either both types of balls catches pokemon or pokeball catches it.
therefore (ui + pi) — (uipi + pi) -> ultraball catches the pokemon but pokeball does not.
Yeah, I also think so
In Div1-A or Div2-C Why not to just fill the whole array with the maximum available value which is 10^9-1 and the maximum minimum mex becomes 10^9 ?
You didn't mention anything like : the array(or subarray) elements need to be unique !
What am I getting wrong here ?
"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