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.
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)
I’m amazed, I have to admit. Seldom do I come across a blog that’s both educative and engaging, and without a doubt, you’ve hit the nail on the head. The issue is something that not enough folks are speaking intelligently about. Now i’m very happy that I came across this in my hunt for something regarding this.
Excellent write-up. I definitely love this website. Keep it up!
Hi there! This blog post could not be written much better! Looking at this article reminds me of my previous roommate! He continually kept talking about this. I am going to send this information to him. Fairly certain he’s going to have a good read. Thanks for sharing!
This is a topic that is close to my heart… Many thanks! Exactly where are your contact details though?
You’ve made some good points there. I checked on the internet to find out more about the issue and found most people will go along with your views on this website.
This is a topic that’s near to my heart… Take care! Exactly where can I find the contact details for questions?
There’s definately a great deal to learn about this topic. I really like all of the points you made.
Good web site you’ve got here.. It’s difficult to find good quality writing like yours nowadays. I truly appreciate people like you! Take care!!
Pretty! This was an extremely wonderful post. Many thanks for supplying this information.
I like it when people come together and share thoughts. Great website, continue the good work!