CHEFGAME - Editorial

editorial
, , , , ,
15

Hey I have tried implementing the same solution as mentioned in the editorial - CodeChef: Practical coding for everyone

I am getting WA. Can anyone point out the mistake in this solution?

Thanks.

16

I had a doubt regarding the time complexity of Prim’s algorithm. Isn’t Prim without a heap and using adjacency list O(V*E) because the outer loop is O(V) and the inner that computes the greedy minimum values O(E).Won’t the simple implementation give TLE in this case?

17

Getting WA.But am not able to work out any corner cases.Can somebody give me some test cases.Help?


[1]


  [1]: http://www.codechef.com/viewsolution/2285768
18

I am getting WA in my approach for a similar problem DAVIDG on spoj

Can you help me figure out the mistake ?
It is on similar lines.
My Code

19

What happen when 2 towns are in 1 same points? should it output 0/1, as i tested in your program it gave 1, but shouldn’t it 0 because we need to connect those two town with distance of 0?

20

Why my solution is giving WA . I am following the approach given in editorial.
My Solution

21

You are using Kruskal algorithm that for complete graph has complexity O(V^2 * log V) (due to sort of edges) and is asymptotically slower than Prim’s algorithms.

It was expected that such approach will get TLE.

3 Likes
22

I see, thanks for your answer :wink:

23

@tijoforyou same here calculaton of distances and sorting of edges took all the time I was also getting TLE due to the same reason :frowning:

24

@amitupadhyay
the problem is not with filling of the graph (n(n-1)/2 edges).
But with the sorting of edges also some over head due to union-find.

I have precalculated all the distance (V^2) than applied prim’s.

http://www.codechef.com/viewsolution/2026500

25

@nirajs got it :frowning: my bad. thanks btw:)

26

according to wikipedia, Prim’s complexity is O(V^2) - Prim's algorithm - Wikipedia

27

Thanks. It has been added.

28

AFAIK O(V * log V) solution exists only in the case of plane (D = 2).

29

I know that won’t be a big improvement, but we can use

if d[j] <= 1 then break
30

@betlista : Using binary heap Prim’s complexity can be brought down to O(ElogV)

31

I’ve also noticed this but decided to stay on “d[j] = 0” version.
But now I see that your version is better since if distances are allowed to be between 0 and 1 then your version is correct but mine not :slight_smile:
So I’ve changed the code snippet.

32

The delaunay triangulation cannot be used for dimensions greater than 3 . And for the higher dimensions the research is still on. Check this wiki page for more information Delaunay triangulation - Wikipedia

33

I saw that on wikipedia, but when E=V^2, is this better? I don’t think so, or I missed something?

34

But in this problem d[j] cannot be in interval (0;1), points have integer coordinates. Btw: comparison is wrong >= instead of <=.