PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yash Kulkarni
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
Minimum Spanning Tree, Kruskal Algorithm
PROBLEM:
Yash gave Swar 2 integers N and M, and an integer array A of size M. Swar has to consider all undirected weighted graphs G such that:
- G has N vertices and M edges
- G is simple, i.e, there is at most one edge between any pair of its vertices and it doesn’t contain self-loops
- The weights of the edges of G are exactly the array A
Among all these graphs, Swar has to find the maximum possible weight of a minimum spanning tree. Please help Swar find his answer.
OBSERVATION and INTUITION
Let us look at this problem from the view of Kruskal Algorithm: First the edges are going to be sorted in non-decreasing order. Then an edge is taken into MST if the nodes it connects lie in different connected components otherwise it is skipped. The algorithm stops when N-1 edges are taken.
This means the minimum weight edge is going to be taken in the MST as it connects two different components. Let the nodes added in the MST be 1->2 Now since multiple edges between two nodes are absent, second edge also connects two different components and hence has to be taken into the MST. Let the graph now be (1->2->3). We construct this graph instead of 1->2 and 3->4 .so that we can skip the third edge otherwise it will again connect two distinct components. Now we can construct a graph in which the third edge connects the the first node and the third node and thus it can be skipped. This is the maximum number of edges we can skip till we have three nodes. The formula about the number of edges that can be skipped till there are N nodes selected using this form of construction is given under the explanation section.
EXPLANATION:
Let us first sort the edges in non-decreasing order. We intend to skip some edges by connecting them to the vertices which are already in the MST and try to increase the weight of the MST as much as possible. Start with a set of selected vertices S with a single vertex 1. Iterate over the edges from i=1 to M, every edge that is selected or included in the MST must add a node that is not included in S till then and every edge that is skipped must have an edge between two nodes of S at that time. Let at this moment the set S contains V vertices. Maximum number of edges in a set of V vertices is \frac{V\cdot(V-1)}{2} out of which exactly V-1 are included in the MST till now. This means i^{th} edge must be included in the answer if number of edges skipped till this point is = \frac{V\cdot(V-1)}{2}-(V-1). If in the end some nodes remain unconnected because of skipping we can connect them to vertex 1 directly using the largest weight edges which are not used.
TIME COMPLEXITY:
O(Nlog(N)) for each test case.
SOLUTION:
Setter's solution
#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
int main(){
ll T;
cin >> T;
while(T--){
ll n,m;
cin >> n >> m;
vector<ll>a(m);
for(ll i=0;i<m;i++)cin >> a[i];
sort(a.begin(),a.end());
vector<bool>present(m,false);
ll pos=0;
ll c=1;
ll ans=0;
ll x=0;
while(pos<m){
present[pos]=true;
if(x<n-1){
x++;
ans+=a[pos];
}
pos+=c;
c++;
}
for(ll i=m-1;i>=0;i--){
if(x==n-1)break;
if(present[i])continue;
x++;
ans+=a[i];
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, m;
cin >> n >> m;
vll v(m);
for (int i = 0; i < m; i++)
cin >> v[i];
sort(all(v));
bool ingraph[m];
memset(ingraph, false, sizeof(ingraph));
ll relax = 0, ans = 0, curr_nodes = 1,skippedtillnow=0;
for (int i = 0; i < m; i++)
{
if(skippedtillnow==1-curr_nodes+((curr_nodes)*(curr_nodes-1))/2)
{
ingraph[i]=true;
curr_nodes++;
}
else
skippedtillnow++;
}
for (int i = m-1; i >= 0; i--)
{
if (curr_nodes == n)
break;
if (!ingraph[i])
{
ingraph[i] = 1;
curr_nodes++;
}
}
for (int i = 0; i < m; i++)
{
if (ingraph[i])
ans += v[i];
}
cout << ans << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
