PROBLEM LINK:
Author: Harendra Chhekur
Editorialist: Darshan Sen
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Check whether it is possible to design a network of exactly N computers and exactly M wires such that there exists at most one wire between each and every computer and each computer is directly or indirectly connected with each other.
If possible, find the minimum data consumption factor of the network. The data consumption factor of a computer is the number of computers it is directly connected to. The data consumption factor of the network is the maximum of the data consumption factors of all computers.
EXPLANATION:
Let’s stop calling this a computer network and think in terms of a graph. Since this is a greedy approach, let’s discuss a method of adding the M edges (or wires) to a given graph with N vertices (or computers).
The minimum value that M holds for all vertices to be connected is N - 1. Then, the graph would take the form of a Path graph.
The maximum value that is held by M is in the case where we generate a complete graph with all vertices having a self-loop each, i.e.,
M = {N}\choose{2}(number of edges in a complete graph) +N(self-loops) = N (N + 1) / 2
If the value of M lies beyond the mentioned range, we print -1. If that is not the case, we try to calculate the data consumption factor of the graph. We think of a method of adding the edges to the graph optimally, so that the data consumption factor is minimized in each case.
We’ll start off with N > 2.
Path graph(N - 1 edges)
Here, the data consumption factor is 2.
We may add edge #N in between the pair of vertices with degree 1, to either make
a Cycle graph or just add a self-loop to one of the vertices with degree 1.
The data consumption factor is still 2.
As we add edge #N + 1, we have a graph that looks like the Path graph with the two end vertices having self-loops. Hence, the data consumption factor is still 2.
For edge #N + 2, we join the two vertices with self-loops and get data consumption factor to be 3. We keep adding edges in the form of self-loops till we reach edge #2N. We still get data consumption factor to be 3.
Now, the scenario has changed. We change our perception of the graph. Since we are not touching the self-loops anymore, let’s denoise the graph we’ve been drawing by removing the obvious self-loops. What have we got now? A simple graph!
Let’s consider that we already have the required graph with M edges connected. The number of edges of the simple graph is:
E = M - N(removing N self-loops)
sum of degrees=2E
Now, let’s distribute the sum of degrees among all N vertices evenly. The maximum of degrees of all vertices is given by:
maxdeg = \lceil sum of degrees / N \rceil
Note:
We need not be concerned about parallel edges coming up in the resultant graph because, in a simple graph, we neither have parallel edges nor self-loops.
Let’s trace ourselves back to the original graph, where we had self-loops.
data consumption factor = maxdeg + 1(adding back the self-loop)
We have solved the problem for values of N>2. Now I’ll list out the solutions one can find out by manually working out the problem for N = 1 and N = 2:
N M data consumption factor
1 | 0 | 0
1 | 1 | 1
2 | 1 | 1
2 | 2 | 2
2 | 3 | 2
Clearly, the time complexity of the solution is O(1).
Below is a heavily documented code in C++.
SOLUTIONS:
Editorialist's Solution
#include <iostream>
typedef long long ll;
ll solve (ll N, ll M) {
/*
Spoiler: This is a greedy approach. =D
The minimum value M can hold,
for all the computers to be connected
is N - 1 -- a path graph
The maximum value M can hold,
= Combination(N, 2) // each pair of computers has 1 wire in between
+ N // 1 self loop on each computer
*/
ll res;
if (
M < (N - 1LL)
or
M > ((N * (1LL + N)) >> 1)
) {
res = -1LL;
} else {
if (N == 1LL) {
if (M == 0LL) {
res = 0LL; // Since the computer is connected to itself
} else {
// M == 1LL
res = 1LL;
/*
---1
|__|
*/
}
} else if (N == 2LL) {
if (M == 1LL) {
res = 1LL; // 1 ----- 2
} else if (M == 2LL) {
res = 2LL;
/*
---1 ----- 2
|__|
*/
} else {
// M == 3LL
res = 2LL;
/*
---1 ----- 2---
|__| |__|
*/
}
} else {
if (M <= 1LL + N) {
/*
1st N - 1 wires form a path graph
...
x x
\ /
x x
Nth wire forms a cycle graph
...
x x
\ /
x--x
N+1th wire forms this
...
x x
\ /
--x x--
|_| |__|
*/
res = 2LL;
} else if (M <= (N << 1)) {
/*
cycle graph with
all computers having
1 self-loop each
*/
res = 3LL;
} else {
/*
we remove the
obvious self-loops
and make it a simple graph
*/
ll simple_graph_edges = M - N;
/*
Here we use the simple Handshaking Lemma
: https://en.wikipedia.org/wiki/Handshaking_lemma
*/
ll sum_of_degrees = simple_graph_edges << 1;
/*
Since it is a greedy approach,
we consider that sum_of_degrees will be evenly distributed
among all the computers.
But, if we can't divide sum_of_degrees evenly
among N computers, we have to consider the computer with
the maximum degree. Hence, we find ceil(sum_of_degrees / N).
*/
// ceil of sum_of_degrees / N
ll c = (sum_of_degrees + N - 1LL) / N;
/*
maximum degree(for the simple graph)
+ 1(self-loop)
*/
res = 1LL + c;
}
}
}
return res;
}
int main() {
int T;
std::cin >> T;
while (T--) {
ll N, M;
std::cin >> N >> M;
std::cout << solve(N, M) << std::endl;
}
return 0;
}
: 
