COALSCAM - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Graph, Tree, Kruskal’s Algorithm

PROBLEM

You are given an undirected graph representing cities and roads in Byteland. Initially, there are no roads connecting the cities. Chef and other companies have proposed to build roads. Each road proposal also gives the cost of building the road. In other words, there are two types of road proposals: the ones proposed by Chef and the ones proposed by other companies. Choose a subset of the road proposals in such a way that for each two cities, there is exactly one path of roads between them, and the total cost of Chef’s chosen road proposals is maximized. If there are more than one way, choose the way where the total cost of all chosen road proposals is minimized.

QUICK EXPLANATION

Use Kruskal’s Algorithm twice. First, consider each of the Chef’s road proposals in non-increasing order of cost and add each road if it connects two different tree of cities. Hence, we will have a maximum spanning forest of cities. Second, consider each of the other companies’ road proposals in non-decreasing order of cost and add each road if it connects two different tree of cities.

After all road proposals have been considered, if the cities are still not connected, the answer is “Impossible”.

EXPLANATION

A graph where there is exactly one path between every two vertices is a tree. Essentially, the problem asks for a spanning tree of the graph which satisifies some constraints. We will use greedy approach to solve this problem.

The first constraint is that the total cost of Chef’s chosen road proposals is maximized. Therefore, we should first build a spanning forest considering only Chef’s road proposals. Use Kruskal’s Algorithm. Since we want to maximize the total cost, we should consider the road proposals in non-increasing order of cost, building a maximum spanning forest.

We can use Union-Find data structure to implement the Kruskal’s Algorithm. The pseudocode is as follows.

sort the Chef's road proposals in non-increasing order of cost
total_chef = 0
for i = 0; i < M2; i++:
    (u, v, c) = chef_road_proposal[i]
    if u and v are in different components:
        merge u's and v's components
        total_chef = total_chef + c

After building the maximum spanning forest, there will be connected component(s) of the graph consisting of trees. The next step is to connect the components in the forest to form a single tree as required by the problem statement. We will use other companies’ road proposals to connect these trees. Since we want to minimize the total cost, we should consider the road proposals in non-decreasing order of cost.

sort the other companies' road proposals in non-decreasing order of cost
total_others = 0
for i = 0; i < M1; i++:
    (u, v, c) = others_road_proposal[i]
    if u and v are in different components:
        merge u's and v's components
        total_others = total_others + c

The answer to this problem is (total_chef, total_chef + total_others). However, if after the whole steps the cities are still not connected, then the answer is “Impossible”.

Now, you may wonder how to handle Chef’s road proposals with equal costs. What is the tie-breaker method? The choice for Chef’s road proposals with equal costs seems to affect the choice for other companies’ road proposals too. We will prove that this is not important; we can sort road proposals with equal costs in any order.

Theorem. The set of (set of cities which forms a single component), after building the maximum spanning forest considering Chef’s road proposals only, is always the same no matter how you handle ties between road proposals with equal costs.

For example, let N=6 and a maximum spanning forest divides the cities into three components: {3, 4}, {1}, {2, 5, 6}. Then, any other ways of handling the road proposals with equal costs will always gives {{3, 4}, {1}, {2, 5, 6}}.

Proof. The proof is by contradiction. Suppose there are two ways which gives two different configurations of components. Then, in the first configuration, there will be a Chef’s road proposal which connects two cities of different components (otherwise there will be only one possible configuration). However, this is not possible: this road proposal should have been chosen at the first place in Kruskal’s Algorithm during the first step of the solution. Therefore, there is exactly one configuration of components as the result of building the maximum spanning forest.

Now that the theorem is proved, the answer only depends on the tie-breaker method during the Kruskal’s Algorithm in the second step, i.e., for other companies’ road proposals. However, this is also not important because we only care about the total cost. Conclusion: we can handle all road proposals with equal costs in any way we want.

The time complexity of this solution is O(M1 log M1 + M2 log M2) + (time complexity of the Union-Find data structure). With union by rank and path compression techniques, we can achieve time complexity of O(M1 log M1 + M2 log M2 + N).

SETTER’S SOLUTION

Can be found here

TESTER’S SOLUTION

Can be found here

5 Likes
2

We can do all the process in one pass of Kruskal algorithm. For this we set each edge weight as a pair (c1, c2), where c1 is the Chef profit from this road and c2 is its actual cost. So for Chef’s road we will have weight (c, c) and for other roads (0, c). Then we should sort edges at first in descending order of c1 and edges with equal c1 sort in ascending order of c2.

6 Likes
3

I cant figure out the mistake in my code… This is the link to my code : http://ideone.com/Sq4pQ
The code is readable and have been commented out at the required places.

4

Check lines 117, 119. It should be idx instead of i. Proof

3 Likes
5

Thanks anton_lunyov :slight_smile:

6

If i am not wrong in understanding your solution, the time complexity would be O((M1+M2)log(M1+M2)) which is greater than the two pass algorithm.

7

It is in fact has the same constant in asymptotic. If M1=M2=M then M1 log M1 + M2 log M2 = 2 M log M and (M1+M2) log(M1+M2) = 2 M log (2 M) = 2 M log M + 2 log 2 * M. So difference is just 2 M. But the main point was that it is easy to code and any copy-paste of pieces of code is non needed which usually can lead to bugs.

2 Likes
8

You can do it using one pass of kruskal by adding edges of chef as (u, v, -c) and that of others’ as (u, v, c).

2 Likes
9

k… nice :slight_smile:

10

submitting tester solution is giving wrong answer. :stuck_out_tongue:

11

Don’t doubt the tester’s solution. The solution is correct. Check for the spelling mistake in “Impossible”.

12

i wanted to implement disjoint sets using pointers – forests. got right answer in test cases but online :frowning: . even after repeated attempts getting WA. can somebody help ? –

http://www.codechef.com/viewsolution/1376433

13

i implemented in a similar way using Prim’s Algo but got WA. I used a max priority queue and entered the chefs road as positive and others as negative.
http://www.codechef.com/viewsolution/1382727
will this not work here

14

codechef is giving wrong answer for this problem COALSCAM. WHY?

#include
#include
#include

using namespace std;

#define lp(i,a,b) for(i=a;i<b;i++)

// comp(pair<long long int,pair<int,int> > i, pair<long long int,pair<int,int> > j){return i.first>j.first;}

int main(){
ios_base :: sync_with_stdio(0);
int t,i;
cin >> t;
int n,m1,m2,u,v;
long long int temp;
while(t–){
cin >> n >> m1 >> m2;
bool visit[n];
lp(i,0,n){
visit[i]=false;
}
vector<pair<long long int,pair<int,int> > > chef;
vector<pair<long long int,pair<int,int> > > other;

    lp(i,0,m1){
        cin >> u >> v >> temp;
        other.push_back(make_pair(temp,make_pair(u,v)));
    }
    sort(other.begin(),other.end());
    
    lp(i,0,m2){
        cin >> u >> v >> temp;
        chef.push_back(make_pair(temp,make_pair(u,v)));
    }
    sort(chef.rbegin(),chef.rend());
    
    long long int ans=0;
    for(i=0;i<m2;i++){
        if(!visit[chef[i].second.first] || !visit[chef[i].second.second]){
            visit[chef[i].second.first] = true;
            visit[chef[i].second.second] = true;
            ans+=chef[i].first;
        }
    }
    
//    cout << ans << "*";
    
    long long int x=0;
    for(i=0;i<m1;i++){
        if(!visit[other[i].second.first] || !visit[other[i].second.second]){
            visit[other[i].second.first] = true;
            visit[other[i].second.second] = true;
            x+=other[i].first;
        }
    }
    
    int flag=0;
    for(i=0;i<n;i++){
        if(!visit[i]){
            flag=1;
            break;
        }
    }
    
    if(flag==0){
        cout << ans << " " << ans+x << "\n";
    }else{
        cout << "Impossible\n";
    }
}
// your code goes here
return 0;

}