Problem Link:
Author: Keyur Chaudhari
Testers: Ishaan Shah, Sanyam Shah, Sambasai Andem and Tejas Chaudhari
Editorialist: Keyur Chaudhari
DIFFICULTY:
MEDIUM/HARD
EXPLANATION:
Explanation of hints
The name of the problem
Mandalore Satellite Tracing (short form: MST)
For all other problems with names greater than length two, only the first letter of the first word is in capitals, whereas for this problem, the first letter of all three words is in capitals.
Tree
- To indicate that the graph will be a tree, the word “sapling” was used.
- All 4 strings given as sample input are names of “saplings” on planet Mandalore.
MST hints
- The first paragraph of the problem statement discusses how the goal is to ensure that “all” lives are destroyed, which hints toward the spanning nature of the tree.
- The second paragraph of the problem statement hints toward minimizing cost.
- The word “terrain” was used to indicate that the integers given in the first “N” lines of input are the coordinates of the vertices.
- The weight of an edge between vertex u and vertex v is the Manhattan distance between vertex u and vertex v. This can be figured out from the samples given.
In this problem, we have to find the weight of the minimum spanning tree of the graph given as input. The weights of edges are the manhattan distance between the 2 vertices connected by the edges. The manhattan distance can be computed by making use of the coordinates given as input.
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> parent;
int find_parent(int i) {
if (parent[i] == i) {
return i;
}
parent[i] = find_parent(parent[i]);
return parent[i];
}
int main() {
int n, m;
cin>>n>>m;
vector<pair<long long int, long long int>> arr(n);
parent.resize(n);
for (int i = 0; i < n; ++i) {
string s;
long long int a, b;
cin>>s>>a>>b;
arr[i] = {a, b};
parent[i] = i;
}
vector<pair<long long int, pair<int, int>> > edgelist;
for (int i = 0; i < m; ++i) {
int u, v;
cin>>u>>v;
--u;
--v;
edgelist.push_back({abs(arr[u].first - arr[v].first) + abs(arr[u].second - arr[v].second), {u, v}});
}
sort(edgelist.begin(), edgelist.end());
long long int ans = 0;
for (int i = 0; i < m; ++i) {
int a = edgelist[i].second.first;
int b = edgelist[i].second.second;
a = find_parent(a);
b = find_parent(b);
if (a != b) {
parent[b] = a;
ans += edgelist[i].first;
}
}
cout<<ans<<endl;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
class UnionFind {
private:
vector<int> p, rank, setSize;
int numSets;
public:
UnionFind(int N)
{
setSize.assign(N, 1);
numSets = N;
rank.assign(N, 0);
p.assign(N, 0);
for (int i = 0; i < N; i++)
p[i] = i;
}
int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j)
{
if (!isSameSet(i, j)) {
numSets--;
int x = findSet(i), y = findSet(j);
if (rank[x] > rank[y]) {
p[y] = x;
setSize[x] += setSize[y];
}
else {
p[x] = y;
setSize[y] += setSize[x];
if (rank[x] == rank[y])
rank[y]++;
}
}
}
};
int distBtwnPoints(pair<int, int> a, pair<int, int> b)
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
signed main()
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> coordinates(n);
for (int i = 0; i < n; i++) {
string temp;
int x, y;
cin >> temp >> x >> y;
coordinates[i] = {x, y};
}
// storing edges in the form {cost, {node1, node2}}
vector<pair<int, pair<int, int>>> edges(m);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
edges[i] = {distBtwnPoints(coordinates[u - 1], coordinates[v - 1]), {u - 1, v - 1}};
}
sort(edges.begin(), edges.end());
UnionFind dsu(n);
int ans = 0;
for (int i = 0; i < m; i++) {
if (!dsu.isSameSet(edges[i].second.first, edges[i].second.second)) {
ans += edges[i].first;
dsu.unionSet(edges[i].second.first, edges[i].second.second);
}
}
cout << ans << endl;
}