CNTGRP- EDITORIAL(100 points )

Subtask 1:-
Observation :- As m=n-1 . Therefore we need to create a tree. Since we are considering shortest path in a tree from root to a certain vertex v, it means there should be a[v] vertex in its path or we can call a[v] as its level. Since it will only have a single parent ( as it is a tree) the edge should come from a vertex that is at level a[v]-1. So we have (count(nodes with a[i]= a[v]-1)) options for parent of this vertex. To answer this subtask we just have to multiply this to the answer for every vertex from 2 to n.

OR :-

You just have to consider it as a tree rooted at 1. Now to find the shortest path to any vertex v from root you just have to find its level right?
if its level is (say lev[v]) it’s parent must be a vertex with level (lev[v]-1 ). So you can choose any vertex with level lev[v]-1 as its parent. we can say that we have (cnt(number of nodes at level lev[v]-1)) options. By basic PnC rules we just have to multiply these options right ?

Subtask 2:- Now we do not have the condition that m=n-1 therefore there can be additional edges. Now as given in the problem statement that it should only have a single shortest path therefore it should only have a single edge connected to a vertex that has a[i]=a[v]-1. In this way we can select n-1 edges.
Now we have to explore the options for remaining m-n+1 edges . Lets say for current vertex v it has a edge from a vertex u and this hasn’t been selected yet.
What can be the value of a[u]:-

  1. a[u]==a[v]-1 we can’t select this edge as we want unique shortest path from 1 to v and one vertex with value a[x]=a[v]-1 has already been selected.
  2. a[u]< a[v]-1 if we select this edge the shortest path to v will have length a[u]+1 and which will not be equal to a[v]
  3. a[u]==a[v] Now if we select this edge the shortest path to v will still remain a[v] and same can be said for shortest path from 1 to u.
  4. a[u]>a[v] We can explore it later for when we will deal with u.

Now we can only select the edges which are in between two vertex have same value a[u]==a[v].
Now we just need to count total number of edges of this type (let’s say it as tot)and multiply tot choose (m-n+1) to our answer.

For calculating tot
int tot =0;
fr(i,1, max(a[v]))
{
int cnt =number of vertices with a[v]==i
tot+= cnt*(cnt-1)/2;
}

For calculating tot choose (m-n+1) :-
as we know nCr = (n/r )*(n-1Cr-1) ->we can simply write nCr as
(n * (n-1) * (n-2) * (n-3) *…(n-r+1))/(r * (r-1) * (r-2)…2 * 1)

Since m-n+1 will be less thatn 2e5 ,above numerator and denominator can be calculated under time limit . Then we just have to multiply numerator * ( inverse (denominator)) to the answer .
Where inverse ( c ) represent power(c,MOD-2)

You can see my code here :-https://www.codechef.com/viewsolution/37267460

13 Likes

To answer this subtask we just have to multiply this to the answer for every vertex from 2 to n.

can you taken an example to elaborate ?

You just have to consider it as a tree rooted at 1. Now to find the shortest path to any vertex v from root you just have to find its level right?
if its level is (say lev[v]) it’s parent must be a vertex with level (lev[v]-1 ). So you can choose any vertex with level lev[v]-1 as its parent. we can say that we have (cnt(number of nodes at level lev[v]-1)) options. By basic PnC rules we just have to multiply these options right ?
Tell me if you want more explanation. I will be happy to help.

1 Like

Yeah i got it.

1 Like

Excellent explanation man. I missed the “single shortest path” condition and complicated the problem.

3 Likes

:slight_smile:

I cannot find the editorial for other questions? Have they been uploaded yet?

2 Likes

While calculating \binom{tot}{m-n+1}, how will you calculate tot!? I am asking this to you because, tot can be as high as \relax10^{10} and it won’t be calculated in time.

1 Like

Awesome editorial bro !!

2 Likes

I have written it in the editorial itself.
It is just the number of edges in between the vertices with same value in the array.
So we just have to sum all those edges . Let say there are cnt number of vertex with value x we just have to add cnt*(cnt-1) in the tot. and x can only be from 1 to max value in our array which is definitely less than n. So we can find tot in O(n) time complexity.

1 Like

But if you are asking about calculating tot choose (m-n+1) since tot is very large… See we can find nCr in O(min(r,n-r)). And the method has already been mentioned in the editorial.

2 Likes

Let’s say we have 3 nodes at level 2( or shortest distance 1 from node 1) and 2 nodes at level 3( or shortest distance 2 from node 1) then I think there are 9(3 ^ 2) ways to connect the nodes at level 2 and level 3. Note that I am not considering now the other edges which can be between the nodes of the same level (because this case will be considered later in the part where we are selecting m-n+1 nodes from total edges).

Let’s say nodes at level 2 are 2, 3 and 4
and noes at level 3 are 5 and 6
According to me the 9 possibilities are :-
2 - 5, 2 - 6
2 - 5, 3 - 6
2 - 5, 4 - 6
3 - 5, 2 - 6
3 - 5, 3 - 6
3 - 5, 4 - 6
4 - 5, 2 - 6
4 - 5, 3 - 6
4 - 5, 4 - 6

I know it is wrong but i don’t know my mistake and i also don’t know how you are calculating 6 (3 * 2) ways to connect the nodes. Please tell me what I am doing wrong?

1 Like

didn’t see the constraints that M < 2e5 and wasted 1/2 hr during contest :expressionless:

You are absolutely right, the answer for above scenerio comes out to be 9. And even I am calculating it to be 9.

Yeah I got it thanks :+1:.

UPD : Very nice explanation and clean editorial.

1 Like

can anyone explain this -> cnt*(cnt-1)/2; why div by 2?

it is cnt C 2.
Let say there are v vertex and you have to find total number of edges between them, how will you find it. You can choose 2 vertices out of this v right and there will be a edge between them, the number of ways to choose these two vertices is cnt C 2. You can learn more about how to select r things out of n things from the internet.

yes i got it…thanks

1 Like

Yeah, I misunderstood your code, sorry for that. But still I am getting TLE in subtask 2 although i have calculated NCR in min(r, n-r) complexity. So can you please have a look at my code?
My code is very clean and commented as well, so it won’t be very difficult for you to go through my code.
https://www.codechef.com/viewsolution/37361149

just take i of long long type while calculating numerator and denominator and multiply (i%mod) instead of just i (since i can be of range 10^10 and answer can be as high as 10^9 which might cause integer overflow) in numerator and denominator

The updated code

1 Like