HackerRank Minimum MST Graph Solution

In this post, we will solve 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 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.
The sum of the lengths of all edges is as small as possible.

For example, let’s say n = 4. m = 5 and s = 4. We need to construct a graph with 4 nodes and 5 edges. The value of minimum spanning tree must be 4. The diagram belows shows a way to construct such a graph while keeping the lengths of all edges is as small as possible:

Here the sum of lengths of all edges is 7.
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.
Note: It is guaranteed that, for all given combinations of n. m, and s, we can construct a valid graph.
Input Format
The first line contains an integer, g. denoting the number of graphs.
Each of the g subsequent lines contains three space-separated integers describing the respective values of n (the number of nodes in the graph), m (the number of edges in the graph), and s (the value of the MST graph).

Output Format

For each graph, print an integer on a new line denoting the minimum sum of the lengths of all edges in a graph satisfying the given conditions.

Sample Input

2
4 5 4
4 3 6

Sample Output

7
6

Explanation

Graph 1:
The answer for this sample is already explained the problem statement.
Graph 2:
We must construct a graph with n = 4 nodes. m = 3 edges, and an MST value of $ = 6. Recall that a connected graph with n nodes and n-1 edges is already a tree, so the MST will contain all m = 3 edges and the total length of all the edges of the graph will be equal to the value of the minimum spanning tree. So the answer is 6.

Table of Contents

Minimum MST Graph C Solution

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);



int main()
{
    char* g_endptr;
    char* g_str = readline();
    int g = strtol(g_str, &g_endptr, 10);

    if (g_endptr == g_str || *g_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int g_itr = 0; g_itr < g; g_itr++) {
        char** nms = split_string(readline());

        char* n_endptr;
        char* n_str = nms[0];
        long n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

        char* m_endptr;
        char* m_str = nms[1];
        long m = strtol(m_str, &m_endptr, 10);

        if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

        char* s_endptr;
        char* s_str = nms[2];
        long s = strtol(s_str, &s_endptr, 10);

        if (s_endptr == s_str || *s_endptr != '\0') { exit(EXIT_FAILURE); }

        long mintotal;
        long maxedges = ((long)(n - 1)*((long)n - 2))/2;
        if(m <= maxedges + 1){
            mintotal = m + s - n + 1;
        }
        else{
            //Extreme difference - all 1 except last
            long mintotalex = ((long)(m - maxedges))*((long)(s - n + 2)) + maxedges;

            //Partial extreme - all same except last, as close together as possible
            long lowedge = s/(n - 1);
            long highedge = s - (n - 2)*lowedge;
            long mintotalpart = ((long)maxedges)*((long)lowedge) + ((long)(m - maxedges))*(long)highedge;
            mintotal = (mintotalex < mintotalpart? mintotalex : mintotalpart);

            //Complete average
            long highnum = (s - 1)/(n - 1) + 1;
            long numlow = (n - 1) - ((s - 1)%(n - 1) + 1);
            long lowedges = (numlow * (numlow + 1))/2;
            long mintotalave = lowedges * (highnum - 1) + (m - lowedges)*highnum;
            mintotal = (mintotal < mintotalave? mintotal : mintotalave);
        }
        printf("%ld\n", mintotal);
    }

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }
    if(data[data_length - 1] != '\0'){
        data = realloc(data, data_length + 1);
        data[data_length] = '\0';
        data_length += 1;
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

Minimum MST Graph C++ Solution

#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <long long> vll;
typedef pair <long long, long long> pll;
typedef pair <int, int> pii;
typedef vector <int> vii;
typedef complex <double> Point;

#define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mp make_pair
#define fst first
#define snd second

long long t, n, m, u, v, q, k;
const int N = 1e5 + 500;
const long long mod = 1e9 + 7;
const long long INF = 1LL << 61LL;
long long arr[N], brr[N];
string str, ss;

long long place[N];
long long sum(long long n) {
  return n * (n - 1) / 2;
}

int main() {
  csl;
  cin >> t;
  while (t--) {
    long long s;
    long long N, M, S;
    cin >> n >> m >> s;
    N = n, M = m, S = s;
    m -= (n - 1);
    long long cost = s;
    long long tt = (n - 2) * (n - 3) / 2;
    if (tt >= m) {
      cost += m;
    } else {
      cost += tt;
      m -= tt;
      cost += m * (s - (n - 2));
    }
    long long costa = 0;
    long long cur = s / (n - 1);
    m = M;
    costa += sum(n - 1) * cur;
    costa += (m - sum(n - 1)) * (cur + (s % (n - 1)));
    if (M > sum(n - 1)) cost = min(cost, costa);
    m = M;
    costa = 0;
    costa += sum(n - 1) * cur;
    costa += (m - sum(n - 1)) * cur;
    costa += max(0LL, sum(n - 1) - sum(n - (s % (n - 1))));
    if (s % (n - 1)) costa += (m - sum(n - 1));
    if (M > sum(n - 1)) cost = min(cost, costa);
    cout << cost << '\n';
  }
  return 0;
}

Minimum MST Graph C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution {

    static void Main(string[] args) {
        long g = long.Parse(Console.ReadLine());

        for (long gItr = 0; gItr < g; gItr++) {
            string[] nms = Console.ReadLine().Split(' ');
            long numberOfNodes = long.Parse(nms[0]);
            long numberOfEdges = long.Parse(nms[1]);
            long minimunSpanningTree = long.Parse(nms[2]);

            var result = minimumWeight(numberOfNodes, numberOfEdges, minimunSpanningTree);
            Console.WriteLine($"{result}");
        }
    }
    
    static long minimumWeight(long numberOfNodes, long numberOfEdges, long minimunSpanningTree) {
        try{
            if (numberOfEdges <= (numberOfNodes - 1)*(numberOfNodes - 2)/2 + 1) {
                return numberOfEdges + minimunSpanningTree - numberOfNodes + 1;
            }
        long core = (numberOfNodes - 1)*(numberOfNodes - 2)/2;
        long unbalanced = core + (minimunSpanningTree - numberOfNodes + 2)*(numberOfEdges - core);
        
        long temp = minimunSpanningTree/(numberOfNodes - 1);
        long larger = minimunSpanningTree - temp*(numberOfNodes - 1);
        long smaller = numberOfNodes - 1 - larger;
        long midbalanced = temp*core + (temp + larger)*(numberOfEdges - core);
        
        long balanced;
        if (larger > 0) {
            core = smaller*(smaller + 1)/2;
            balanced = temp*core + (temp + 1)*(numberOfEdges - core);
        } else {
            balanced = temp*numberOfEdges;
        }
        
        return Min(Min(unbalanced, balanced), midbalanced);
        } catch (Exception e){
            Console.WriteLine(e.Message);
            return -1;
        }
        
    }
    
    static long Min(long x, long y){
        if(x > y){
            return y;
        }
        else{
            return x;
        }
    }
}

Minimum MST Graph Java Solution

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

Minimum MST Graph Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

g = int(input().strip())
for a0 in range(g):
    n,m,s = input().strip().split(' ')
    n,m,s = [int(n),int(m),int(s)]
    
    if m <= (n - 1) * (n - 2) // 2 + 1:
        print(m + s - n + 1)
    else:
        s -= n - 1
        e = m - (n - 1) * (n - 2) // 2
        mnc = (s + n - 2) // (n - 1)
        ans = 1e42
        s -= mnc
        for A in [0, s // (n - 2), s // (n - 2) - 1]:
            for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
                x = A * (n - 2) + B
                if 0 <= x <= s:
                    ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))

        print(ans + m)

Minimum MST Graph C Solution

Minimum MST Graph C++ Solution

Minimum MST Graph C Sharp Solution

Minimum MST Graph Java Solution

Minimum MST Graph Python Solution

Related Posts

Leave a Reply Cancel reply