PRIMEGRAPH-Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Mamedov
Tester : Takuki Kurokawa
Editorialist: Kingvarun

DIFFICULTY:

Easy Medium

PREREQUISITES:

Graph

PROBLEM:

You need to find maximum number of edges that a graph can have such that a graph such that every node of that graph has prime degree.

EXPLANATION:

Degree of node is the number of edges connected to that node, and we have to make that prime for the all the nodes.

Maximum number of edges that can be drawn from a single node for a graph containing N nodes is N-1, means each node is connected to all the other remaining nodes.

So, we have to simply find a greatest prime number which is less than equal to N-1 and that will be the number of the edges containing by one single node.

But, if the value of N id odd than it is not possible to create a graph such that every node have same prime degree less than equal to &N-1$.

Why Not ??

Suppose we have value of N equal to 5 and prime number which is less than or equal to 4 is 3, Can we able to create a graph such that every node has degree 3.

No, because the sum of all the degrees is equal to twice the number of edges. Since the sum of the degrees is even and the sum of the degrees of vertices with even degree is even,

the sum of the degrees of vertices with odd degree must be even. If the sum of the degrees of vertices with odd degree is even, there must be an even number of those vertices.

Here in this case sum of degree of vertices is 5*3 which is odd, and sum of degree of vertices should always be even.

Therefore, what we have to do is simply reduce the degree of one node to 2 and for others keep it as same.

For even no.of number nodes

Maximum edges is (N * P) / 2

For odd no.of number nodes

Maximum edges is (((N-1) * P) / 2) + 1

where P is the maximum prime number less than equal to N-1.

TIME COMPLEXITY:

O(N * Sqrt(N)) per test case

SOLUTIONS:

Author's Solution
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
void solve() {
  int N;
  cin >> N;
  int P = N - 1;
  while (!isPrime(P)) --P;

  if (N % 2 == 0) {
    cout << (1ll * N * P / 2ll) << ln;
  } else {
    cout << (1ll * (N - 1) * P / 2ll + 1) << ln;
  }
}
int main() {
  ios_base::sync_with_stdio(false);

  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Tester's Solution
// input validation, not for editorial.
#include <bits/stdc++.h>
using namespace std;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        } else if (g == endd) {
            if (is_neg)
                x = -x;
            if (!(l <= x && x <= r)) {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            return x;
        } else {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
        char g = getchar();
        assert(g != -1);
        if (g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r) {
    vector<int> a(n);
    for (int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = (int) readInt(1, 100, '\n');
    while (tt--) {
        int n = (int) readInt(3, (int) 1e5, '\n');
        int p = n - 1;
        while (!is_prime(p)) {
            p--;
        }
        if (n % 2 == 0) {
            cout << 1LL * n * p / 2 << '\n';
        } else {
            cout << 1LL * (n - 1) * p / 2 + 1 << '\n';
        }
    }
    readEOF();
    return 0;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

 bool isprime( ll p)
    {
        ll count=0;

        for(ll i=1; i<=sqrt(p); i++)
        {
            if(p % i == 0 )
             count++;

        }
        if(count==1)
         return true;
        else
         return false;

    }

int main() {

    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);

        int t;
        cin>>t;
        while(t--)
        {
            ll n , i;
            cin>>n;
            for(i=n-1; i>=2; i--)
            {
                if(isprime(i))
                 break;
            }
            if(n%2==0)
            {
                cout << (n * i)/2 << "\n";
            }
            else
            {   
                cout << ((n-1) * i)/2 +1 << "\n";
            }
        }
        return  0;
    }
    
  
10 Likes

This problem can also be solved in O(N\cdot \log{N}) time using Sieve of Eratosthenes.

Here is my solution: Solution: 56927008 | CodeChef

Why there is exist graph on N vertexes with prime degree p<=N-1 for each vertex? That is not obvious.
An even sum of vertex degrees is only a necessary condition, but not a sufficient one.

Refer this—Existence of k-regular graph - Mathematics Stack Exchange

2 Likes

According to Havel Hakimi theorem we simply find that if there is any simple graph exist or not ,
by only knowing the degree of each node ?

From this we can simply proved that there exist a graph with N nodes having Prime degree <= N-1

Link - Havel Hakimi

Solved using Seive Of Eratosthenes in O(N logN).
My solution: Solution: 57011829 | CodeChef

1 Like

Can someone please explain how can we reduce the degree of a single node while keeping the others same, I can only think of reducing degree of two nodes simultaneously. Keeping this in mind the solution I got arived at was (P*(n-2) + 2 + 3)/2 for odd number of nodes. Decreasing the degree of two nodes simultaneously.

We are not reducing the degree of single node by keeping all the same
If the value of N is odd
We are making a graph for N-1 nodes and keeping degree of all N-1 nodes prime and for the last Nth node we connect it between any edges so that degree of that becomes 2 that is also prime

1 Like

Can someone please explain why in for the odd case we are adding 1 in this case as there is one element left in odd to not have its degree prime ((n-1)*prime)/2+1 ??? but why adding 1 only ??

oh I got it, thank you so much bro :wink:

Can I know why my Code is getting TLE ??

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;


void solve() {

    ll n ;
    cin >> n;

    if (n == 3) {
        cout << 3 << "\n"  ;
        return ;
    }
    vector<ll>adj[n + 1]  ;
    unordered_map<ll, ll>deg ;
    for (ll i = 1; i <= n - 1; i++) {
        adj[i].pb(i + 1)  ;
        adj[i + 1].pb(i)  ;
        deg[i]++ ;
        deg[i + 1]++  ;
    }

    adj[n].pb(1)  ;
    adj[1].pb(n)  ;

    deg[n]++ ;
    deg[1]++ ;

    // for (auto l : deg) {
    //     cout << l.F << " " << l.S << "\n"  ;
    // }
    // cout << "\n" ;

    ll edges = 0 ;
    if (n % 2 == 0 ) {
        ll i = n ;
        for (auto k : deg) {
            if (i == 0) {
                break ;
            }
            k.S++ ;
            edges += k.S;
            i-- ;
        }

        cout << edges / 2 << "\n" ;
    }
    else {

        ll i = n - 1;
        for (auto k : deg) {
            if (i == 0) {
                break ;
            }
            k.S++ ;
            edges += k.S;
            i-- ;
        }

        cout << (edges / 2) + 1 << "\n" ;
        // ll p1 = edges ;
        // p1 /= 3 ;
        // p1++ ;
        // p1 += 2;
        // cout << p1 << "\n"  ;
    }
}





int32_t main() {

    fast ; time;

    int t = 1;
    cin >> t;

    while (t--) {
        solve()  ;
    }


    return 0  ;
}