CHEFGAME - Editorial

editorial
, , , , ,
41

Your solution is quite unclear. But it seems to me that maxheapify has complexity O(log(n/i)) in the worst case. And build call it for all i from 1 to n/2. So build has complexity O(n * log n).

42

I couldn’t determine why this submission of mine was failing. Please help.

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

43

Well I also can’t get it right. I always get wrong answer. Could anyone help me? :slight_smile:

My “solution”

44

Read editorial. Your mistakes are mentioned there.

1 Like
45

When maksi becomes zero you should break from the cycle.

1 Like
46

Well of course :smiley: Thanks Anton!

47

Thank you.
AC :slight_smile:

48

Hey I have tried implementing the same solution as mentioned in the editorial - http://www.codechef.com/viewsolution/2170014

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

Thanks.

49

I would really appreciate someone looking at the solution

50

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?

51

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
52

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

53

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?

54

When two towns have the same point, it’ll not connect those towns and give the initial answer which is 1.

55

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