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;
}
