CHEFGAME - Editorial

editorial
, , , , ,
21

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

22

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

23

Hi programmers,

I tried to implement Prim’s algorithm, but I’m getting WA.
I compared the results with my previous Kruskal implementation and I’m getting same result. Is there some corner case, that’s not covered by my random tests (or any other bug)?

My submission is here - http://www.codechef.com/viewsolution/2056473

Thanks

24

can anyone explain NZEC ?

25

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
26

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
27

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

2 Likes
28

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

29

thnx a lot :slight_smile:

30

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

1 Like
31

Hello @all,

I have tried to implement Prim’s Algorithm…but I am getting TLE,I have used a stl::priority queue for the finding the min distance…could you all have a look into my program and tell me where my program is getting slow.

ideone link: http://www.codechef.com/viewsolution/2038046

Thanks in advance.

32

Complexity of your solution is O(N^2 * log N).
It is slow in this problem.
Refer to code snippet in editorial.
It contains simple O(N^2) solution without any data structures.

33

Firstly thanks for the reply,secondly could you please explain me how did you come up with that complexity…actually I thought that my complexity is O(N*log N)…considering the log N was the insertion time in the priority queue…Thanks in advance again…:slight_smile:

34

At each step of algorithm (N-1 times) for each unvisited vertex you push pair (u, j) to the heap.
So total number of pushes is about N*N/2.
Also you should not take distance modulo MOD when create adjacency matrix.
Please read the editorial carefully (the bold sentence).

1 Like
35

Thanks a lot…will keep in mind next time.

36

can anyone tell where this code fails i have tried many test cases it is giving correct answer but still getting wa on the judge my submission id is : http://www.codechef.com/viewsolution/2060320

37

k+=(a*a) should be k += (long long)a * a
sum=(sum*k)%MOD should be sum = k%MOD * sum % MOD
But most likely after this it will get TLE.

38

thank you very very much for your help i made the changes and it worked…got ac after 10 wa

39

Congrats!
You were lucky to pass with O(N^2 * log N) solution which supposed to get TLE in this problem.
This is probably because of own-written heap class.

40

can you explain how the complexity comes out to be O(N^2 * log N) .as in the while loop i build the heap which is o(n)and this loop will occur n times so overall complexity should be O(n^2)