PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: archit
Editorialist: raysh07
DIFFICULTY:
Simple
PREREQUISITES:
Binary Search
PROBLEM:
You are given a complete graph with N vertices. Consider all possible weighted graphs with exactly M edges weighted 1 and the rest 0. Let W denote the sum of weights in the minimum spanning tree. Find the sum of all possible distinct values of W.
EXPLANATION:
For each X, let us try to figure out if it is possible to obtain a MST sum of exactly X. For convenience, define K = \frac{N \cdot (N - 1)}{2} - M, where K is the number of weight 0 edges.
Consider the connected components formed by only adding the weight 0 edges and leaving out the rest. Suppose there are Y components with sizes A_1, A_2, ..., A_Y. Then, the number of weight 0 edges could be between \sum (A_i - 1) and \sum \frac{A_i \cdot (A_i - 1)}{2}.
The first quantity simply becomes N - Y because \sum(A_i) = N. The second quantity is not that easy to reduce. But, it is clear that we want to maximize it, since we want the range to be as large as possible.
Claim : To maximize \sum \frac{A_i \cdot (A_i - 1)}{2}, at most one A_i > 1.
Proof : Suppose A_i \ge A_j > 1 exists. Then, A_i + 1, A_j - 1 has more possible pairs of 0 weight edges, so the sum increases. Hence, we should have at most one A_i > 1.
After this, it is relatively easy to calculate the maximum sum. Because, assume A_1 > 1. Then, A_1 = N - Y + 1 and the remaining A_i = 1. Thus, the maximum sum is \frac{(N - Y + 1) \cdot (N - Y)}{2}.
Note that if there are Y connected components after adding weight 0 edges, that means we will need Y - 1 weight 1 edges to unite everyone (and that will also be our MST sum).
Thus, replacing Y with X + 1, we get the conditions N - X - 1 \le K \le \frac{(N - X) \cdot (N - X - 1)}{2}.
The left side introduces a constraint X \ge N - 1 - K. The right side introduces a more trickier constraint. However, notice that \frac{(N - X) \cdot (N - X - 1)}{2} is increasing as we decrese X. This means that we can binary search on X to find the maximum X such that K \le \frac{(N - X) \cdot (N - X - 1)}{2}.
After that, we simply need to calculate the sum of integers in range [L, R] which is just \frac{R \cdot (R + 1)}{2} - \frac{L \cdot (L - 1}{2}
TIME COMPLEXITY:
\mathcal{O}(log(N)) per testcase.
CODE:
Editorialist's Code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, m; cin >> n >> m;
// m weight 1 edges
int k = n * (n - 1) / 2 - m;
// k weight 0 edges
// for mst of cost w, need n - 1 - w <= k <= (n - w) C 2
// w >= n - 1 - k
// n - w >= lo
// w <= n - lo
int lo = 0, hi = n;
while (lo != hi){
int mid = (lo + hi) / 2;
if (mid * (mid - 1) / 2 >= k){
hi = mid;
} else {
lo = mid + 1;
}
}
int l = n - 1 - k, r = n - lo;
l = max(l, 0LL);
r = min(r, n - 1);
int ans = r * (r + 1) / 2 - l * (l - 1) / 2;
cout << ans << '\n';
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}