CHEFGAME - Editorial

editorial
, , , , ,
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 <=.

35

You should take distance modulo only before you multiply it to the answer. Refer to my code snippet in editorial (I’ve changed it a bit to explain this bug).

1 Like
36

Thanks, fixed. If double would be allowed than distance could be any positive real number and only your version is correct since multiplying the answer by number less than 1 will decrease it.

1 Like
37

1
2 3
0 0 0
19325 19339 149
The answer should be 0 while your answer is 747474747.

2 Likes
38

Thank you very much that was the problem. Probably I have same bug in my Kruskal implementation so I didn’t find it.

39

thnx a lot :slight_smile:

40

Fun fact, modulo 747474747 is not a prime number :slight_smile:

2 Likes