 # GALACTIK - Editorial

EASY

### PREREQUISITES

Disjoint Set Data Structure, Simple Math

### PROBLEM

There are N nodes in a graph labeled from 1 to N. Each node has an associated cost with it, given by cost array. You wish to connect this graph by constructing edges between the nodes.

• You can construct an edge between two nodes a and b iff cost[a] ≥ 0 AND cost[b] ≥ 0
• The cost of the construction of the edge is equal to cost[a] + cost[b]

Some edges already exist. Hence, some nodes are already connected. You wish to find the minimum cost of connecting the entire graph.

### QUICK EXPLANATION

We will be using a Disjoin Set Data Structure that supports the following operations

• init(N), initialize N disjoint sets.
• find(A), get the id of the disjoint set to which A belongs.
• join(A,B), merge the two disjoint sets in which A and B belong respectively.

Union-Find along with Union by Rank and Path Compression is the asymptotically optical way of maintaining Disjoint Sets.

After considering the existing set of edges, we will have some disjoint sets, where there are one or more nodes in each set. Let us assume there are K disjoint sets.

We only need to put K-1 edges

This is easily proven by considering that adding each edge reduces the number of disjoint sets by 1. If it doesn’t, then the edge is connecting two nodes that are already connecetd.

Thus, we only consider K-1 edges at most.

### EXPLANATION

As we dwell deeper into discussing the solution to the problem we will encounter a lot of difficulty discussing the ideas if we keep reminding ourselves of ignoring the vertices with negative costs. To be able to handle them in the discussion below (and maybe in your implementation as well), we assume that each negative cost is replaced by a very large positive cost. We will see soon that doing this does not affect the optimal answer.

We can consider each disjoint set as an independent vertex and try to build a minimum spanning tree on the graph. The problem is, that for K disjoint sets, there may be as many as KC2 edges. We know that we can solve the problem of finding the minimum spanning tree by greedily considering the edges in increasing order of weights.

Here comes to our rescue the definition of the weight of edges in the problem statement.

Edge Weight for edge from a to b = cost[a] + cost[b]

Let x be the vertex for which cost[x] is smallest. An edge between x and any other vertex will have a lower cost than any other edges in the graph.

Also, considering all the edges with one end point on x means we are considering sufficient edges for a connected graph!

Note how assuming that all negative cost vertices were actually very large positive cost edges allows us to get around several edge cases

• The lowest cost vertex, x, is automatically the lowest non-negative cost vertex
• We will consider all the edges from x to other vertices in the order of increasing weights, thus we avoid considering edges to vertices with negative weights
• If we are forced to consider an edge to a vertex with large weight (negative cost vertex originally), then we know that we could not have connected to the connected component of that vertex through any vertex whose weight was positive (otherwise we already would be connected to that component).

Hence, if the answer could be reached before connecting to any vertex with very large weight, we can print the answer, otherwise, we will print -1.

Note that we can avoid the sorting step altogether and consider the minimum cost vertices in each connected component. This way, if we know the sum of costs of the minimum cost vertices in each component, the answer is simply

```cost[x] * (K-1) + sum - cost[x]
```

Where x is the vertex with the smallest cost.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.

9 Likes

My solution involves using DFS to find connected components and minimum costs in a connected component.

4 Likes

I also used DFS to find the connected components. I think its easier to understand as well as to implement than union-find method.

2 Likes

could u plz look at http://www.codechef.com/viewsolution/2389555 its giving wa

I am giving you a test case. Try to figure it out on your own.
7 4
1 2
2 3
1 3
5 6
3
-1
-1
2
6
8
4

1 Like

I was going through a few submissions of this problem. Interestingly, @mugurelionut’s solution seems way too clear than the editorial itself!!

1 Like

@tijoforyou Your code does not handle the case for multiple paths with the same vertex, or is it so?
When (1->3); then (3->2); and then (2->1) is given as the paths, your code would store it as 1(->2), 2(->1) and 3(->2) as the final list for DFS.
Could you clarify how this does not change the correctness of the solution?

@programme I am using adjacency list representation. When (1->3); then (3->2); and then (2->1) is given as the paths, my code would store it as 1(->2->3), 2(->1->3), 3(->2->1). (For each edge `<u, v>`, I add `u` at the front of the adjacency list of `v`, and `v` at the front of the adjacency list of `u`.

@tijoforyou I really appreciate your help, I finally figured it out. Thanks again!

@programme We are all here to learn and help each other. Happy to help! Hello all,
I’m applying this approach…

1. Use DFS to count number of components and minimum tax of each component.

2. If any component has all planets having negative taxes, then answer is -1

3. Otherwise find global min tax value.

4. Compute result = sum of minimum value of all components + (components-2)*global_min

Is my algo right ??

Using this approach,I’m able to get right answers in all test cases I can think of…still getting WA…

2 Likes

“If any component has all planets having negative taxes, then answer is -1”

What if this is true, but there is only one component? Then, surely, the answer is 0 and not -1.

Have you checked this case?

1 Like

Apart from this, the steps you said are right.

thanks bro, for your help…now it got accepted.

DFS is much easier to handle Can anyone please provide a test case where my solution is wrong?? I used DFS…but getting WA…

@tijoforyou What is the mistake with the following code. My code has exactly the same logic as yours, just the way of implementation differs: http://ideone.com/OOQUBQ

``````