Kick Start Round E: Problem Analysis — Cherries Mesh
Hello! fellow competitive programmers, Kick start Round E is wrapped up and here is my take at the Problem Cherries Mesh.
For starters Kick Start is a programming competition organized by Google.
The problem statement goes as follows:
Your friend is recently done with cooking class and now he wants to boast in front of his school friends by making a nice dessert. He has come up with an amazing dessert called Cherries Mesh. To make the dish, he has already collected cherries numbered 1 to N. He has also decided to connect each distinct and unordered pair of cherries with a sweet strand, made of sugar. Sweet strands are either red or black, depending on the sugar content in them. Each black strand contains one units of sugar, and each red strand contains two units of sugar.
But it turns out that the dessert is now too sweet, and these days his school friends are dieting and they usually like dishes with less sugar. He is really confused now and comes to your rescue. Can you help him find out which all sweet strands he should remove such that each pair of cherries is connected directly or indirectly via a sugar strand, and the dish has the minimum possible sugar content?
Input Format:
The first line of input gives the number of test cases, T.
Each test case begins with a line containing two integers N and M, the number of cherries and the number of black sweet strands, respectively.
Then M lines follow, each describing a pair of cherries connected to a black strand. The i-th line contains cherries numbered Ci and Di, it indicates that Ci and Di cherry are connected with a black strand of sugar.
Note: Any other pair of cherries not present in the input means that they are connected by a red strand.
Output Format:
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is minimum possible sugar content.
Constraints:
Time limit: 15 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100
M ≤ N*(N-1)/2
1 ≤ Ci ≤ N, for all i.
1 ≤ Di ≤ N, for all i.
Ci ≠ Di, for all i.
Every {Ci, Di} is distinct.
My Analysis:
Let’s simplify the problem statement.
Let’s assume that cherries are vertices, strands of sugar is edges and the sugar content is weight edges in an undirected graph.
It’s given that we need to remove edges from the graph such that the graph still remains connected and the sum of weights of edges present in the graph is minimal.
Once we develop this view we can easily solve the problem.
A brute force approach could be to construct the graph and then take the minimal spanning tree of the graph.
A minimal spanning tree is nothing but the subset of edges from the graph, such that the graph is still connected and the sum of the weights of edges taken is minimal.
We can do this by using Prim’s Algorithm and you can read more on that here:
However this solution is lengthy to code and can have more memory occupancy.
A much more elegant solution to solve this problem could be found, if we dive a bit more into the problem statement.
We know that we have M edges whose weight (sugar content) is 1 unit and the remaining (N*(N-1)/2 )- M edges have weight as 2 units.
Obviously we need to include all the edges with weight 1 unit in our minimal spanning tree. Apart from these edges we may need some additional edges of weight 2 to connect these edges to the remaining portion of the graph and also to connect these edges among each other.
One way to solve this problem is to use the concept of Disjoint sets.
A disjoint set is a data structure that can be used to determine which set of vertices are in the same connected component, which is basically the set of vertices in which every vertex is either directly or indirectly reachable from every other vertex.
So the idea is to construct a disjoint set from the given graph such that we put all the M edges of weight 1 into it.
We can make the following observations from it:
- Now we can easily group the vertices belong to the same connected component.
- Find the vertices which are not at all a part of any of the connected component or belong to two different connected components, these vertices should be connected to any one of the groups and it would cost us an edge of weight 2.
- Also now we would need to connect all the edges in the same connected component and this would cost us an edge of weight 1. (As we initially took only M edges into consideration)
All of this can be done by using the array which stores the parent of each vertex in disjoint set representation let’s call this parent array
We also use a map to store which vertices belong to which connected component once we have the parent array.
Let’s say we have x independent connected components in the map.
Now we can connect these x components using x-1 edges. It really doesn’t matter which vertex we choose from each of those connected components.
So our base cost is (x-1)*2, where x is nothing but the size of the map (or number of keys in the map). As the number of independent connected components is the size of the map.
Once we have his base cost, we only need to add the weight for connecting the edges internally in every connected component.
This can be done simply by iterating on the map and let’s say we have y vertices in a connected component. The cost to connect y edges is (y-1)*1
So the total cost is nothing but:
(length(map)-1)*2 + ∑(y-1) where y is the number of vertices in a pirticular connected component.
The code I used to solve the problem can be found below:
https://github.com/Tarun047/KickStart/blob/master/2019/Round%20E/Cherries%20Mesh.py
And that’s for today fellas, see you with another good problem next time.
