here my doubt is if connected component here if order of 10^5’
then in my calculating total value it will give time limit.how i optimised that.
Https://ide.codingblocks.com/s/228092
Okay I think what you are asking is how to improve this part
for(int i=0;i<cnt;i++)
for(int j=i+1;j<cnt;j++)
total+=arr[i]*arr[j];
now this would give TLE if cnt is of order 10^5.
Well you can go about solving this in this way.
Let’s say there are n connected components, and the i’th component has xi values.We are storing our answer in sum. So initially sum=0. Also total number of nodes equal to N.
So we have x1,x2,x3…xi,…xn.
Now for any xi , we can simply add sum+=xi*(N-xi).
Do it for all i from 1 to n. Now divide sum by 2 and that is your answer.
You can use basic combinatorics to see why this result is correct. So now the algorithm runs in O(n) time and won’t give a TLE.
can you give explanation how to solve it mean proof type the value of this become this.
Okay for all x1 , you have N-x1 ways to choose.
So we add x1*(N-x1) to the answer, for all x2 we have (N-x2) to choose from so we add x2*(N-x2).
but see when we were choosing for x1 we would have picked from x2 component already, so we are doing it again while picking choices for x2, so we divide it by 2 because the order doesn’t matter.
Take a few examples, Run it for x1=1,x2=1…,xn=1 and you will know why it works.
1 Like