Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
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 |
Name |
---|
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