PROBLEM LINK:
Setter: admin
Tester: admin
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Simple
PREREQUISITES:
Disjoint Set Union or DFS/BFS, Greedy, Two-Pointer.
PROBLEM:
Given a graph with N nodes/cities and M bidirectional edges, where each city has some number of museums. You have to make K trips, and in start of each trip you visit a non-visited city and all the cities connected to it . You have to check if you can make K trips or not. If you can make K trips you have to find number of museums that will be visited such that in Lavanya's turn you visit the city and cities connected to it, to maximize the number of museums and in Nikhil's turn you visit to minimize the number of museums.
QUICK EXPLANATION:
- As stated when you start a trip you visit a previously non-visited city and visit all the cities connected to it. Hence you are visiting all the cities in a connected component.
- We can find the number of connected component using DSU or DFS.
- If number of components < K, the answer will be -1.
- If number of components \geq K, count the number of museums in each connected component. In Lavanya's turn choose the current maximum, add it to the answer and remove it from the list and in Nikhil's turn choose the current minimum, add it to the answer and remove it (this step can be done with two-pointer).
EXPLANATION:
Few Keywords
- K - Total number of trips to make.
- Connected Component - A set of nodes in which each node can be visited from any other node in the set using the given edges .
As it is clear from the problem statement that when we make a trip we visit a previously non-visited city and visit all the cities connected to it. So each trip can considered as an operation in which we visit a connected component and add the total number of museums(sum of museums of all the cities/nodes present in the component), and then delete the component(as all the cities in the component in visited so we can’t visit the same component again).
You can use Disjoint Set Union to find the number of connected components. This can also be done using DFS/BFS, you can learn about it from here Link.
Now If the number of connected components < K, then it is not possible to make K trips hence the answer will be -1.
If the number of connected components \geq K, then answer is possible.
So lets propose a strategy.
- First count the total number of museum in each connected component.
- In Lavanya's turn - when you have to choose the city to maximize the museum visit, choose the connected component with current maximum count of museum, add to the answer and then remove it.
(Why we do this?, As in the question it is asked to maximize number of museum in this trip, so we will choose this component with maximum count as it maximize the number of museum and then remove it). - In Nikhil's turn - when you have to choose the city to minimize the museum visit, choose the connected component with current minimum count of museum, add to the answer and then remove it.
Few Tips For Implementation
- Count the number of museums in each component and put it in an array A.
- Sort the array.
- Maintain two pointers. Left and Right, Initially pointing towards the minimum and maximum value in the array.
- Do an iteration from 1 to K.
When i is odd add A[Right] to the answer and do Right - -.
When i is even add A[Left] to the answer and do Left + +.
TIME COMPLEXITY:
-
To find Connected Components
- Using DFS - O(N) per test case.
- Using DSU - O(N *\alpha(N)) per test case. where \alpha(N) is Inverse Ackermann Function.
-
For Sorting O(N*\log(N)).
-
Total O(N*\log(N)) per test case.
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
struct DSU {
using T = int;
vector<T> parent;
vector<T> size;
T numComponents = 0;
DSU(T n = 0) {
if(n >= 0)
init(n);
}
void init(T n = 0) {
parent.resize(n);
size.assign(n, 1);
numComponents = n;
for (T i = 0; i < n; i++)
parent[i] = i;
}
T getParent(T x) {
return (x == parent[x]) ? x : parent[x] = getParent(parent[x]);
}
bool merge(T x, T y) {
x = getParent(x);
y = getParent(y);
if (x == y) {
return false;
}
if (size[x] < size[y]) {
swap(x, y);
}
parent[y] = x;
size[x] += size[y];
numComponents--;
return true;
}
};
void solveTestCase() {
int cityCount; // Number of cities, (N)
int roadCount; // Number of road connections, (M)
int tripCount; // Number of trips they have to make, (K)
cin >> cityCount >> roadCount >> tripCount;
vector<int> museumsInCity(cityCount+1); // Number of museums in each city
DSU uf(cityCount+1); // Use of DSU to get to connected components (which are connected by road).
for(int i = 1; i <= roadCount; i ++) {
int a, b;
cin >> a >> b;
uf.merge(a, b);
}
for(int i = 1; i <= cityCount; i ++) {
cin >> museumsInCity[i];
}
int ccCount = 0; // Number of connected components
for(int i = 1; i <= cityCount; i ++) {
if(i == uf.parent[i]) {
ccCount ++;
}
}
if(ccCount < tripCount) { // In this case they won't be able to make the required number of trips. As all cities will be visited
cout << -1 << '\n';
return;
}
// Now we will count the number of museum in each connected component
vector<int> ccMuseum(cityCount+1, 0);
for(int i = 1; i <= cityCount; i ++) {
int componentID = uf.getParent(i);
ccMuseum[componentID] += museumsInCity[i];
}
vector<int> A;
for(int i = 1; i <= cityCount; i ++) {
if(i == uf.parent[i]) {
A.push_back(ccMuseum[i]);
}
}
sort(A.begin(), A.end());
int answer = 0;
int Left = 0, Right = ccCount-1;
for(int i = 1; i <= tripCount; i ++) {
if(i % 2) {
answer += A[Right];
Right --;
}
else {
answer += A[Left];
Left ++;
}
}
cout << answer << '\n';
}
int main() {
ios_base::sync_with_stdio(0); // fast IO to speed up input and output
cin.tie(0);
cout.tie(0);
int testCase;
cin >> testCase;
while(testCase --) {
solveTestCase();
}
return 0;
}
This in my first time writing an editorial hope you like it 
. Any suggestions on how to improve are welcomed.