# GALACTIK : getting WA

I am getting WA and I have even considered the case where all planets are connected to each other and the answer is zero for that. please help me. here the the link to my code.

1 Like

consider dis input
8 5,
2 3,
4 5,
6 7,
7 8,
8 2,
1,
-1,
2,
3,
-1,
4,
1,
3
ur program is giving wrong ans

@proxc , can you explain how did you find this test case for my code ?

disjoint -= 2;

ans += disjoint * min_all;

This code is wrong. Suppose we have 4 connected components.
Let m1, m2, m3, & m4 be the minimum of each connected component sorted in increasing order.
Then

if m1 < 0 ans is -1;

otherwise the answer is 3 * min1 + Sum(m2, m3, m4); The general formula is (n - 1) m1 + sum(mi)

n here represents the number of connected components.

The answer should be zero since all the planets are connected and there is only one connected component. Your code gives 9 while the right answer is 0

@a9393j007 try as many possibility as u can using pen and paper and later check if your program produces correct outputâ€¦
This is one of the test case i used to test my program before submitting.

in my code,

1. i first visit the set of planets which are connected to each other and find there min(min is always positive) and then add it to answer.
2. so if we have 4 components so i have already added m1,m2,m3,m4 to answer in the DFS().
3. at the end 2 components are already connected so i use disjoint-=2 and add disjoint*min_all to answer.

@a9393j007: the bug in your code is that u have not marked the adjacency vice versa:

``````void Graph::addEdge(int v, int w)
{
}
``````

this is your modified submission which get AC.
http://www.codechef.com/viewsolution/2384136

1 Like

actually in your test case all the planets are not connected and yaaa my code is giving wrong answer for you test case. answer should be 5 not 9 .

1 Like

Can you explain the logic u used to solve this problem?

i have already explained the logic.

I believe ravishanker is right about that.

thnx for clarifying

Well some faults that i could find was that when you are creating an edge you are not making it bi-directionalâ€¦ i.e when you use addEdge function call it for both (a,b) and (b,a)â€¦Otherwise for a test case in which connections(agreements) are like

1 2

3 2

4 1

your code will identify(incorrectly) 3 disjoint componentsâ€¦while all of 1 2 3 4 are connected.

Secondly, when input for costs are all negative you seem to give 0 as the answer even if there are no connections!
This is because you break your DFS loops as soon as you get negative value of cost for all vertices of a single connected component.Thus for correcting that u must continue the DFS loops to get exact number of connected components then check for complete connectedness.

It is quite strange that even for that modified AC code the case
5 0,-1,-1,-1,-1,-1 will give 0 while actual answer is -1â€¦i donâ€™t think there was any constraint disallowing all negative costs or 0 connections.

If the number of connected components is 1 then you can reach any planet from any other planet thus there is no need to pay anything thatâ€™s y the answer should be 0 even if all the costs are -ve

ya I got it now â€¦ thx for that.

If there are no connections how are number of connected components 1??
They should be N.

@amitrc17 , i think we need to report this to the author.
@bondoc73, as m=0 so there is no connection between the five planets so answer should be -1.

@a9393j007 i believe you are right, but there wonâ€™t be any changes in the contest results as rechecking for the question is quite difficult at this point of timeâ€¦but hopefully the practice section test cases can be updated.