Bear and Clique Distances Doubts

general
,
1

Problem link :

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

Code link :

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

2

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
3

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

4

U need to remove these two loops for old cities.

5

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

6


Here it is discussed by @mathecodician…u can see his solution also.

1 Like
7

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:

8

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

9

@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.

If you feel your query has been answered, please mark this as an accepted answer.

2 Likes
10

Thanks !!
It helped a lot!!