PROBLEM LINK:
Author: Dharanendra L V
Tester: Dharanendra L V
Editorialist: Dharanendra L V
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Pre Computation technique, Sieve of Eratosthenes
, GCD.
PROBLEM:
Given N gifts on which an integer G_{i} is written, you have to check all the given values G_{i} are prime numbers if it is found to be true, then print ”Do not distribute”. Else print “Distribute” and then you have to find the smallest integer C and paint all the gifts with two colors. If the integer G_{i} is divisible by C then it is colored red, otherwise white. You have to paint the gifts such that no two consecutive gifts should have the same color, if it is possible to achieve this, then print the value of C, otherwise, print “Coloring is not possible”.
EXPLANATION:
Initially, to if check all the numbers are prime numbers are not, if you solve it by brute force approach then the worst-case time complexity would be O(T \times N \times 10^5) i.e. ~10^{11} operations, that will definitely lead to TLE(Time limit Exceed) as max only 10^8 operations are possible in 1sec, we can follow pre-computational technique to handle this by sieve of eratosthenes algorithm to find the prime numbers in O(1) per query. Then if all the numbers are found to be prime numbers then just print ”Do not distribute”.
Else print “Distribute” and to find the value of C, What does it mean that no contiguous gifts should have the same color? It means that either all gifts on odd positions are red and all gifts on even positions are white, or vice versa. So, we need to check these two cases. Let’s try to solve a case when we have to find a number C such that G_{1},G_{3},… are divisible by C, and G_{2},G_{4},… are not. What does it mean that C divides all of the numbers G_{1},G_{3},…? It means that C divides the gcd(G_{1},G_{3},…), where gcd represents the greatest common divisor. Let’s calculate this gcd using Euclidean algorithm or some built-in functions in O(N+logG). Now we need to check all divisors of the gcd(G_{1},G_{3},…) and find if any of them does not divide G_{2},G_{4},… So, we have to factorize gcd and generate all of its divisors… or do we? In fact, gcd(G_{1},G_{3},…) divides any of the numbers G_{2},G_{4},…, then every divisor of gcd also divides that number. So, the only two numbers we have to check as canditates for the answer are gcd(G_{1},G_{3},…) and gcd(G_{2},G_{4},…), if these both values divides any number then you have to print “Coloring is not possible” otherwise print the minimum value.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxSize 100005
bool pri[maxSize];
void prime() {
for(int i = 0; i < 100005; i++) {
pri[i] = true;
}
pri[1] = false;
for(int i = 2; i*i < 100005; i++) {
if(pri[i]) {
for(int j = i*i; j < 100005; j += i) {
pri[j] = false;
}
}
}
}
void solve() {
int n;
cin >> n;
vector<int> gifts(n, 0);
for(int i = 0; i < n; i++) {
cin >> gifts[i];
}
bool flag = false;
for(auto gift: gifts) {
if(!pri[gift]) {
flag = true;
break;
}
}
if(!flag) {
cout << "Do not distribute" << endl;
return;
}
cout << "Distribute" << endl;
vector<int> gcd(gifts.begin(), gifts.begin() + 2);
for(int i = 0; i < n; i++) {
gcd[i%2] = __gcd(gcd[i%2], gifts[i]);
}
vector<bool> gcd1(2, true);
for(int i = 0; i < n; i++) {
gcd1[i%2] = gcd1[i%2] && (gifts[i]%gcd[(i%2) ^ 1] > 0);
}
int c = 0;
if(gcd1[0] && gcd1[1]) c = min(gcd1[0], gcd1[1]);
else {
for(int i = 0; i < 2; i++) {
if(gcd1[i])
c = gcd[i^1];
}
}
if(c > 0)
cout << c << endl;
else
cout << "Coloring is not possible" << endl;
}
signed main(int argc, char const *argv[]) {
prime();
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}
Feel free to share your approach here. Suggestions are always welcomed. 