# Bear and Clique Distances Doubts

https://www.codechef.com/APRIL17/problems/CLIQUED/

Why it is showing TLE for 2nd subtask for given constraint???

for(a=1;a<=oldnode;a++)
{
for(m=a+1;m<=oldnode;m++)
{
v[a].push_back(make_pair(m,oldedge));
v[m].push_back(make_pair(a,oldedge));

``````    }}
``````

Consider these lines from your code [line 23-30]. It’s simple to see that the time complexity for this code snippet is O(K^2). For the second subtask, K <= 10^5, so it’s easy to see that your code’s going to time out here.

To pass the second subtask, you’ll need to find a way to solve the problem without explicitly adding the original K*(K-1)/2 roads.

1 Like

U need to remove these two loops for old cities.

https://discuss.codechef.com/questions/95716/dgtcnt-solution
Here it is discussed by @mathecodician…u can see his solution also.

1 Like

Can someone tell me why my code is giving TLE. I have implemented the solution after looking at the editorial but still it is giving TLE.
Here is the link to the code - http://ideone.com/6KfQWj

@chunky_2808 You need to remove the k^2 part where you add edges between all the pairs from 1 to k from your code. This can be done in many ways which are mentioned in the editorial https://discuss.codechef.com/questions/95657/cliqued-editorial

The most easiest I found in the editorial goes as follows

1.Create an extra node i.e if n is 5, you need to create a graph of 6 vertices.
Let’s call this node as ‘z’

2 Traverse i <- 1 to k ,
for each i, make a connection to z with incoming weight to z as x(given in the problem) and outgoing
weight from z to i as 0

The above two steps will create a star-like graph in which you can go from any node within 1 to k with cost only as x and also reduce the k^2 factor from your complexity to k.

Visualization of first given test case with and without optimisation:

You need to make very minor changes in your code to implement the above mentioned optimisation.

2 Likes

Yes, its O(N2) roughly. Can you additionally help him out by telling what he should use to optimise his code? Thanks

Yes how can i optimize it for second test case??

I intentionally left out the solution in case you wanted to try it yourself. If you really want to know, the editorial explains it better than I could:
https://discuss.codechef.com/questions/95657/cliqued-editorial

Thanks !!
It helped a lot!!