HackerRank Minimum MST Graph problem solution

In this HackerRank Minimum MST Graph problem solution you have Given n, m, and s for g graphs satisfying the conditions above, find and print the minimum sum of the lengths of all the edges in each graph on a new line.

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))

{"mode":"full","isActive":false}

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("(\r\n|[\n\r\u2028\u2029\u0085])?");

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

{"mode":"full","isActive":false}

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;
}

{"mode":"full","isActive":false}

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("%lld\n",ans);
 // cout << ans << "\n";
}
int main()
{
 int ntest,test;
 scanf("%d",&ntest);
 // cin >> ntest;
 for (test = 0; test < ntest; test++)
 run();
}

{"mode":"full","isActive":false}