PROBLEM LINK:
Setter: Roman Derkach
Tester: Radoslav Dimitrov
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
Simple
PREREQUISITES:
Observations, greedy
PROBLEM:
Given an array A consisting of n integers. Split the array into two non-empty sets B and C, so that you maximize GCD(B) + GCD(C).
EXPLANATION
Case 1: When all the elements are same, then answer will be 2 times that element.
Case 2: When there are atleast two distinct elements in the array.
Its only logical to have all the elements with same value in only one set. Let us prove it formally. Assume they are present in both sets, moving them all into the first set will not affect GCD(B). On other hand, it might help to increase value of GCD(C).
So now, we remove all the duplicate from A and solve on this new array.
Claim: Let us take a set of 2 or more distinct elements. Lets call this set D. Let y be the maximum in D. Now GCD(D) \leq y/2. Because GCD(D) must be less than y and divide y.
Lets assume size(B) \leq size(C).
Lets say maximum value in A is x. Now , answer is greater than or equal to x+1 (taking set B as \{x\}). This is a lower bound on the answer.
Claim: size(B)=1 in optimal partition.
Proof: Proof by contradiction
Assume size(B) \geq 2. Now GCD(B) \leq x/2. And similarly GCD(C) \leq x/2. So now, GCD(B)+GCD(C) \leq x which is worse than the lower bound obtained above.
Hence, size(B)=1.
Now we will check all the possibilities for B and take maximum of all.There are atmost n possibilities for B. So for each possibility, we have to calculate the gcd of rest n-1 elements which are in set C. For this, we can compute prefix gcd’s and suffix gcd’s of the array A. And now let B be \{A_j\}. So GCD(C) = gcd(prefix gcd till j-1, suffix gcd till j+1).
TIME COMPLEXITY
O(nlog(n)) to remove duplicates from the array.
O(nlog(A_{max})) to construct the prefix gcd and suffix gcd of the array.
O(nlog(A_{max})) to check for all possibilities for B.
Hence , total complexity is O(n(log(n)+log(A_{max}))
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 121;
int suff[MAX_N],pr[MAX_N],a[MAX_N],ans,n;
void check(int x){
int y = x, z = 0;
for(int i = 1; i <= n; ++i)
if(a[i] % x != 0){
z = __gcd(z, a[i]);
}
ans = max(ans, y + z);
}
void solve(){
ans = 0;
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
suff[n] = a[n];
for(int i = n - 1; i > 0; --i)
suff[i] = __gcd(suff[i + 1], a[i]);
ans = a[1] + suff[2];
pr[1] = a[1];
for(int i = 2; i <= n; ++i){
pr[i] = __gcd(pr[i - 1], a[i]);
ans = max(ans, a[i] + __gcd(pr[i - 1],suff[i + 1]));
}
for(int i = 1; i * i <= a[1]; ++i)
if(a[1] % i == 0){
check(i);
check(a[1] / i);
}
cout << ans << '\n';
}
//int
main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t-->0)solve();
return 0;
}
Tester's Solution
import sys
def read_line():
return sys.stdin.readline().split()
def read_int():
return int(sys.stdin.readline())
def read_int_line():
return [int(v) for v in sys.stdin.readline().split()]
############
# Solution #
def gcd(x, y):
while x != 0 and y != 0:
z = y
y = x % y
x = z
return x + y
def compute_other_gcd(A, gcd1):
ret = 0
for x in A:
if x % gcd1 != 0:
ret = gcd(ret, x)
if ret == 0:
return A[-1]
return ret
T = read_int()
for _test in range(T):
N = read_int()
A = read_int_line()
A.sort()
d = 1
answer = 0
while d * d <= A[0]:
if A[0] % d == 0:
answer = max(answer, d + compute_other_gcd(A, d))
answer = max(answer, A[0] // d + compute_other_gcd(A, A[0] // d))
d += 1
print(answer)
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int a[123456];
int pre[123456],suf[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
vi vec;
rep(i,n){
cin>>a[i];
vec.pb(a[i]);
}
sort(all(vec));
vec.resize(unique(all(vec))-vec.begin());
if(vec.size()==1){
cout<<vec[0]*2<<endl;
continue;
}
n=vec.size();
pre[0]=vec[0];
f(i,1,n){
pre[i]=__gcd(pre[i-1],vec[i]);
}
suf[n-1]=vec[n-1];
fd(i,n-2,0){
suf[i]=__gcd(suf[i+1],vec[i]);
}
int ans=max(vec[0]+suf[1],pre[n-2]+vec[n-1]);
f(i,1,n-1){
ans=max(ans,vec[i]+__gcd(suf[i+1],pre[i-1]));
}
cout<<ans<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed.