CHEFK1 Unofficial editorial

PROBLEM LINK:

Contest
Practice

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)

  1. 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.
  2. 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.
  3. 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.
  4. 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 -

  1. 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 .
  2. Now we divide our questions into 2 steps. We first make a base case when N<3 and other when N>=3
  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.
  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.

4 Likes

Shouldn’t Beta be 3 after end of 3rd step?

Yes you’re right! Sorry

Following is a short and concise code, that doesn’t take parity into account :-
https://www.codechef.com/viewsolution/26620905

2 Likes

how u come across this concise code@jackknowsit

Nice editorial! I like your approach. I have done something similar. I’ve mentioned a different way of looking at the diagonals part using graph theory. Here’s my editorial. :slight_smile:

2 Likes

Can you please explain the logic behind your last condition when m>n+1??

Awesome edge case : If we have 1 computer and 0 wires,we call it a network with data consumption factor 0.
My approach.
1)Covered all base cases using else if
2)Started drawing polygons for general case and started distributing diagonals(wires) from vertices in a non-greedy manner(trying to keep Consumption Factor of all Computers Constant as I add-in wires) and observed strange behaviour in odd sided polygons.
3)In odd sided polygon when consumption factor(CF) was even and all had this CF, one vertex was left redundant (i.e had CF-1 wires), where as when CF was odd all vertices had
same CF for max wires.
Here’s my solution,
https://www.codechef.com/viewsolution/26397422

1 Like

For m==n+1 all computer will have one link between them plus self loop on corner one’s.After that all computer will start having one self loop one by one as m increases until m<=2n-1, so answer will be 3 for range (n+2,2n-1) both inclusive, then for m==2*n corner edges will be linked since they are still having degree(consumption factor) 2 which makes answer still 3.

1 Like

You may look at @raisinten’s editorial given above. The logic used is exactly the same as given in it.

3 Likes

wow so much too handle when you can see for a given degree max number of edges is
if deg==2 : n+1
else : ((deg-1)*n)/2+n , now you just have to iterate from degree = 2 to n minimum satisfying one is your consumption factor.

derivation:: lets say self loops are x, then x + 2*(E-x) = sum(deg[i]) 1 to n
now to maximize E we need to maximize x that is atmost n . hence E= n+ ((deg-1)*n)/2

what is the logic behind your last condition?

Can you please explain the last condition ?? This one:
cout << (2*m - n -1)/n + 1 <<endl;