CHEFK1 - Editorial



Author: Harendra Chhekur
Editorialist: Darshan Sen




Greedy, Handshaking lemma


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.


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


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++.


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)
			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;
			} 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
					   \    /
					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
					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;

Really nice and clean editorial.


Thank you so much! :slightly_smiling_face:

1 Like

My Clean Python Code :stuck_out_tongue: : click

1 Like

Beautiful solution :smile:

1 Like

Thanks a lot! :slight_smile:

Thanks a lot. Great Explanation

1 Like

Thank you very much! :slight_smile:

Wow !! great explanation !! :+1:
Many forgot the case “A computer with zero wires is still a network with data consumption factor 0.”

1 Like

Thank you so much! Even I got confused initially, but then using common sense, I figured out the exceptions. :slightly_smiling_face:


I am not able to follow this part. Lets take a simple case of three nodes - A,B,C.

If there are 2 edges - we could go (A,B) and (B,C). CF is 2, since B is connected to two nodes.

If there are 3 edges (N edges) - we could go (A,A) (A,B) and (B,C). CF is still 2.

If there are 4 edges (N+1th edge) - we could go (A,A) (A,B) (B,C) and (C,C). CF is still 2 and not 3.

Beyond N+1 edge until 2N edge, the CF will be 3.

1 Like

Thanks for pointing it out, I’ll change it right now. I have it correct in the code though. :slight_smile:

1 Like

Thanks! Cheers! :smiley:

1 Like

Done! Happy coding! :slightly_smiling_face:

Official editorial is also there:
Check out : CHEFK1 - Editorial

1 Like

Your blog is filled with unique good articles! I was impressed how well you express your thoughts.

OCR App For Android

1 Like

Thanks a lot! I’m glad you liked it. :slight_smile: