GALACTIK : getting WA

general
,
1

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
2

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

3

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.

4

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

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v); //v is also adjacent to W, it is the fix.
}

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

1 Like
5

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.

6

@a9393j007 please…explain me…for the input 8 5,2 3,4 5,6 7,7 8,8 2,1,-1,2,3,-1,4,1,3
the connected planets are
1 (1)

2,3,6,7,8 (1)for 7
and 4,5 (3) for 4

the correct answer should be 6 and not 5
bcz cost of connecting planet 1 and 7 is = 1+1=2
and cost of connecting planet 1 and 4 is = 1+3 =4
so total cost = 2+4 = 6

1 Like
7

my solution is giving right ans for all the above test cases bt Wrong Answer on submission…Here is the link to my solution… CodeChef: Practical coding for everyone …plz help…

8

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

9

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

10

@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. :slight_smile:

11

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.
12

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
13

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

14

i have already explained the logic.

15

I believe ravishanker is right about that.

16

thnx for clarifying

17

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.

18

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

19

ya I got it now … thx for that.

20

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