PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
Basic Geometry, Principle of Mathematical Induction
PROBLEM:
Given a system of N computers and M wires, we need to compute the minimum data consumption factor ( let’s say \beta ) which is defined as \beta = max ( \delta(C_{1}), \delta(C_{2})....,\delta(C_{N})), where \delta denotes the degree of C_{i}th vertex of our computer network. If we cannot create such a network, we should return -1.
- All computers should be connected to each other (directly or indirectly)
- A pair of computer (C_{i}, C_{j}) could be connected at most once.
- Our system should have exactly M wires (edges) and N computer (vertices)
STRATEGY
To be able to return the smallest \beta from a network, we try to make the network in the following way (This way strives to keep \beta at the minimum at every step)
- Connect N-1 wires so as to connect all computers. Let’s say computers C_{1}, C_{N} aren’t connected directly. \beta of the system becomes 2 after the end of this step.
- Now we connect 2 computers C_{1}, C_{N} to themselves using 2 more wires. \beta of the system remains 2 after the end of this step.
- Now we connect computers C_{1}, C_{N} followed by self connecting every computer pair (u,u) that hasn’t already been connected. This would require N-2 more wires. \beta of the system becomes 3 after the end of this step.
- Now the problem reduces to the problem of optimally drawing diagonals of a polygon.
DRAWING DIAGONALS
Now we need an efficient way (so as to keep \beta minimum) to be able to draw diagonals of a polygon with sides N. Let’s divide our problem in two cases, when N is even and when N is odd.
-
WHEN N IS EVEN
Let’s see what happens when we draw a diagonal in a polygon. Since a diagonal connects two points, it increases the degree of both points by 1. Here degree or \delta_{i} is defined as the total number of wires attached directly to a computer C_{i}.
In a polygon with even sides, we can make exactly N/2 diagonals while only raising the degree of every vertex by 1. So, after making N/2 diagonals, \beta increases by 1. We keep making these N/2 diagonals until \beta=N, as N is the highest achievable degree of the system. -
WHEN N IS ODD
Now, when N is odd, we can make \lfloor N/2 \rfloor diagonals which will raise the degree of N-1 vertices by 1. Now in the next step when we draw diagonals, we have N+1 points, (1 point left from prev step). So this time we can make (N+1 )/2 diagonals which will raise the degree of N+1 vertices by 1. So in total, after processing 2 times, \beta of our system increases by 2.
We repeat this process too until \beta=N.
ALGORITHM:
We can approach the problem with these steps -
- We first should make sure that it is possible to make a network from the given values of N and M. We need a minimum of N-1 wires to be able to connect N computers. Also, for N computers, the maximum wires could be obtained from the expression N*(N+1)/2 .
- Now we divide our questions into 2 steps. We first make a base case when N<3 and other when N>=3
- For N=1, we have two possibilities, M=[ 0, 1], here we simply return M as the degree of vertex C_{1}. When N=2, M=[1,3] and we can return \beta as (M + 6)/4.
- Now we follow the optimal strategy stated above to count wires required to
4 A. Make end connections. ( \beta=2 )
4 B. Complete remaining edge and self connect remaining computers. ( \beta=3 )
4 C. Count wires needed to make diagonals. (4<= \beta <= N)
CODE
#include <iostream>
typedef long long lld;
bool inRange(lld N, lld M) {
return (M >= N-1) && (M <= (N*(N+1)/2));
}
lld baseCaseResolver(lld N, lld M) {
if (N==1) {
return M;
}
return (M + 6)/4;
}
lld networkSolver(lld N, lld M) {
if (!inRange(N, M)) {
return -1;
}
if (N < 3) {
return baseCaseResolver(N, M);
}
// Self connections at end
if (N-1 <= M && M <= N+1) {
return 2;
}
// Complete side and self connections
if (N+2 <= M && M <= 2*N) {
return 3;
}
// Draw diagonals
M = M - (2*N + 1);
if (N%2 == 0) {
return 4 + (2*M)/N;
} else {
lld period = N/2 + (N+1)/2;
lld index = 4 + 2*(M/period);
index += (M%period >= N/2);
return index;
}
}
int main() {
int T;
std::cin >> T;
while (T--) {
lld N, M;
std::cin >> N >> M;
std::cout << networkSolver(N, M) << "\n";
}
return 0;
}
TIME COMPLEXITY
Time complexity of the algorithm discussed in this editorial is O(1) per test case.