MAXMST-Editorial

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();
}
5 Likes

Observation 0: The order does not matter so we can sort edges.
Observation 1: We need (n-1) edges.
Observation 2: We cannot skip smallest edge because it is MST.
Observation 3: After selecting k edges we can skip atmost k-1 edges just after it.

#include<bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  for (cin >> t; t; t--) {
    int n, m;
    cin >> n >> m;
    vector<int> A(m);
    for (int i = 0; i < m; i++) {
      cin >> A[i];
    }
    sort(A.begin(), A.end());
    long long ans = 0;
    int cnt = 0, skip = 0;
    vector<bool> vis(m);
    for (int i = 0; i < m && cnt < n - 1; cnt++, skip++, i += skip) {
      ans += A[i];
      vis[i] = 1;
    }
    for (int i = m - 1; cnt < n - 1; i--) if (!vis[i]) {
      ans += A[i];
      cnt++;
    }
    cout << ans << '\n';
  }
  return 0;
}
10 Likes

How did you come to the last observation ? After K edges are picked, why can exactly K -1 edges be skipped ?

Well, Plz explain why we are skipping edges,like we need n-1 edges and we have m edges so what if we just select n-1 edges from them i dont got the point of skipping edges

Need a better editorial.

1 Like

Can anyone tell where I’m wrong or give a counter example? Thanks.

My approach:
Sort the edges. Since, a smaller edge weight would always be taken as it is mst. Try to use as many small edges as possible in a fully connected setup. Then of the remaining ones, a long chain can be made.

The graph in my case would look like, a fully connected cluster of k (max possible) nodes using the smallest weights, a node that is partially connected to the cluster using the next smaller weights till there are just enough for a long chain, a long chain of some suffix of sorted edge weights.

very well explanation

1 Like

Because we can assume that our graph has (k-1) new edges to the nodes of current connected component.

consider this graph with k=3 edges.

we can make 4th and 5th edge as (d–b) and (d–a) respectively:
image
We can skip (k-1 = 2) edges : 4th and 5th edge as they are in same connected component.
Same will work for bigger values of k.

Can explain this problem in better way ? This editorial is not enough.

Why not add edge c-a so as to skip one more edge?

we already skipped it when k was 2.

1 Like

The Editorial has been updated. See if that helps.

The Editorial has been updated. See if that helps

Ah! Indeed. Got it finally, thanks!

when will the video editorials be uploaded for this question ? @admin

@the_eagle_eye - we do not make video editorials for all problems. For the harder problems - users typically prefer the written editorials.

Please we should have video lecture for this . Infact easy problems should not have video lectures. Hard problems need better explanation. It would be great if we have video lectures for the harder ones else how would someone increase their level.

1 Like