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.

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

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

4

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.

5

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

6

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

7

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

@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
9

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
10

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

11

i have already explained the logic.

12

I believe ravishanker is right about that.

13

thnx for clarifying

14

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.

15

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.

16

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

17

ya I got it now … thx for that.

18

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

19

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

20

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