HackerRank Minimum MST Graph problem solution

In this HackerRank Minimum MST Graph problem solution, Allison loves graph theory and just started learning about Minimum Spanning Trees(MST). She has three integers, n, m, and s, and uses them to construct a graph with the following properties:

• The sum of the lengths of all edges is as small as possible.
• The graph has n nodes and m undirected edges where each edge has a positive integer length.
• No edge may directly connect a node to itself, and each pair of nodes can only be directly connected by at most one edge.
• The graph is connected, meaning each node is reachable from any other node.
• The value of the minimum spanning tree is s. Value of the MST is the sum of all the lengths of all edges of which are part of the tree.

HackerRank Minimum MST Graph problem solution in Python.

g = int(input().strip())
for a0 in range(g):
    n, m, s = map(int, input().strip().split(' '))
    n2 = (n * n - 3 * n + 4) // 2
    if n == 2:
        print(s)
    else:
        if m <= n2:
            print(s + m - n + 1)
        else:
            a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
            x = n - 1 - s % (n - 1)
            y = s % (n - 1)
            div = s // (n - 1)
            t = (x * (x + 1)) // 2
            a2 = t * div
            a2 += max(0, (div + 1) * (m - t))
            rem = s - (n - 2) * div
            kant = ((n - 2) * (n - 1)) // 2
            a3 = kant * div + (m - kant) * rem
            print(min(a1, a2, a3))

Minimum MST Graph problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    private static long minimumWeight(long n, long m, long s) {
        if (m <= (n - 1)*(n - 2)/2 + 1) {
            return m + s - n + 1;
        } else {
            long core = (n - 1)*(n - 2)/2;
            long unbalanced = core + (s - n + 2)*(m - core);
            
            long base = s/(n - 1);
            long larger = s - base*(n - 1);
            long smaller = n - 1 - larger;

            long midbalanced = base*core + (base + larger)*(m - core);
            
            long balanced;
            if (larger > 0) {
                core = smaller*(smaller + 1)/2;
                balanced = base*core + (base + 1)*(m - core);
            } else {
                balanced = base*m;
            }
            
            return Math.min(Math.min(unbalanced, balanced), midbalanced);
        }
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int g = scanner.nextInt();
        scanner.skip("(rn|[nru2028u2029u0085])?");

        for (int gItr = 0; gItr < g; gItr++) {
            String[] nms = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nms[0]);

            long m = Long.parseLong(nms[1]);

            long s = Long.parseLong(nms[2]);

            System.out.println(String.format("%d", minimumWeight(n, m, s)));
        }

        scanner.close();
    }
}

Problem solution in C++.

#include <iostream>

using namespace std;

int main() {
    int tasknum;
    cin >> tasknum;
    while (tasknum--) {
        long long n, m, s;
        cin >> n >> m >> s;
        long long ans = 0;
        if ((n - 1) * (n - 2) / 2 + 1 >= m) {
            ans = s + m - n + 1;
        } else {
            if (-(n-2) * (m - (n - 1) * (n - 2)/2) + (n - 2) * (n - 1) / 2 < 0) {
                //average
                long long k = s / (n - 1);
                long long t = s % (n - 1);
                ans = (m - (n - 1) * (n - 2) / 2) * (s - (n - 2) * k) + (n - 2) * (n - 1) / 2 * k;
                if (t != 0) {
                    ans = min(ans,
                        (k + 1) * (m - (n - 1) * (n - 2) / 2) + (n - 1) * (n - 2) / 2 * k + (t - 1) * (2 * n - t - 2) / 2
                    );
                }
            } else {
                ans = (m - (n - 1) * (n - 2) / 2) * (s - n + 2) + (n - 2) * (n - 1) / 2;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Problem solution in C.

#include<stdio.h>
//using namespace std;
typedef long long ll;
ll min(ll a,ll b)
{
 if(a>b)
 return b;
 else
 return a;
}
void run()
{
 ll N, M, S;
 scanf("%lld%lld%lld",&N,&M,&S);
 //cin >> N >> M >> S;
 ll blen = S - (N - 2);
 ll nedge = ((N - 1) * (N - 2)) / 2;
 ll ans=0;
 if (M > nedge)
 {
 ll bremain = M - nedge;
 if ((N - 1) * bremain < M)
 {
 ans = nedge + (M - nedge) * blen;
 }
 else
 {
 ll cval = S - (N - 1);
 ans = M + (M * (cval / (N - 1)));
 cval %= N - 1;
 ll lval = cval * bremain;
 ll rval = 1e18;
 if (cval)
 {
 rval = bremain + (cval - 1) * (N - 2) - (cval - 1) * (cval - 2) / 2;
 }
 ans += min (lval, rval);
 }
 }
 else
 {
 ans = (M - 1) + blen;
 }
 printf("%lldn",ans);
 // cout << ans << "n";
}
int main()
{
 int ntest,test;
 scanf("%d",&ntest);
 // cin >> ntest;
 for (test = 0; test < ntest; test++)
 run();
}