GALACTIK - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

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.

12 Likes

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

5 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

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

4 Likes

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…

6 Likes

DFS is much easier to handle :slight_smile:

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

Someone please help me to figure out why my solution gives a WA.
Link: oM1MVe - Online C++0x Compiler & Debugging Tool - Ideone.com

nice editorial but code was a little messy, dfs is easier though!

Hi please help me out.I am getting WA.Here is my commented


[1]


  [1]: https://ideone.com/Wl3WYn

please have a look at my code ia m using the same logic along with bfs but getting wa

i have solved the question using disjoint set data structure . I have heavily commented my code if anybody wants to solve by using disjoint set and finding difficulty here is my code.

Happy Coding :slight_smile:

5 Likes

can anyone tell me why we did (components-2)*global_min .

2 Likes

can anyone tell me why we did (components-2)*global_min .

could u plz look at CodeChef: Practical coding for everyone 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

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