 SUMAGCD - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Roman Derkach

Editorialist: Teja Vardhan Reddy

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 + suff;
pr = a;
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; ++i)
if(a % i == 0){
check(i);
check(a / 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

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

for _test in range(T):
A.sort()

d = 1
while d * d <= A:
if A % d == 0:
answer = max(answer, d + compute_other_gcd(A, d))
answer = max(answer, A // d + compute_other_gcd(A, A // d))

d += 1

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

// 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;
int pre,suf;
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*2<<endl;
continue;
}
n=vec.size();
pre=vec;
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+suf,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. 10 Likes

Another solution, a little bit less intuitive but simpler:

You must therefore need to do the following:

Handle the trivial case of only one distinct value.
Otherwise, obtain the 2 highest elements;.
Compute the GCD g_0 of all the n-2 lowest elements.
Compute the GCD's g_with_highest = GCD(g_0, M) and g_with_second_highest = GCD(g_0, M-d).
Choose the singleton by comparing M + g_with_second_highest with (M-d) + g_with_highes

Taken from:

1 Like

this question was asked on stack overflow 10 days ago i.e. when the contest was live. It’s so sad to see that people cheat just to get higher ratings .

9 Likes

can this problem be solved by DP?

1 Like

are sure that this approach would work always because it may be the case when the third highest element may count to the result sometimes, I mean can you explain if it only happens that result will always compute with the second largest or the largest.

My thought process was slightly different, first I observed and verified that the largest and 2nd largest number in the input array can never be together. If we put the largest and 2nd largest number in the same bracket we will never be able to achieve max. sum.
I started by removing the repetitions and sorted, if there’s only single element (call it x) then print 2x.
{GCD(8,8) = 8, GCD of two same numbers is always that number}
If you get two distinct numbers then simply add them and print the result. Since we have sorted the array we will get something like this {a, b, c, d, e, f} all in ascending order.
GCD(a, b, c, d) <= a and GCD(e,f) <= e (case 1 where we’ve taken max and 2nd max together)
GCD(a, b, c, d, e) <= a and GCD(f) == f (case 2)
Now just by looking at the equations we can say that putting max and 2nd max in same bracket is not optimal.
if we just assume that case 1 produces max. results (i.e. a+e, note : when GCD(e,f) == e then f=n
e where n!=1 cuz there are no repetitions) and case 2 produces min results (i.e. 1+f)
a+e < 1 + ne (f == ne)
on reducing the equation we get
a < 1 + (n-1)*e (note : n >= 2) and this equation is true
and also one of the two brackets should only contain the max or the second max element.
In cases like {10, 14, 15} we have to split it like {14} and {10, 15}.
we will simply calculate GCD from the first element to the 3rd last element (inclusive) , let’s call that g. Here v[n-1] refers to the last element or max element and v[n-2] refers to 2nd max element. we’ll use an if statement to check which combination produces maximum output.

int gcd_a = __gcd(g,v[n-2])+v[n-1];
int gcd_b = __gcd(g,v[n-1])+v[n-2];
if (gcd_a >= gcd_b)
cout << gcd_a << '\n';
else
cout << gcd_b << '\n';

Link to my solution : SUMAGCD

3 Likes

yup, i too saw that today right now and this should be brought under the code of conduct

1 Like

third highest element can’t be kept in a separate bracket. we can’t find the max. sum that way.

Interestingly the setter’s solution gives a TLE.
https://www.codechef.com/viewsolution/24862780

4 Likes

it works, So unhappy to see answers posted in communities while contests are still going on

2 Likes

What is wrong with this method??

Can someone disprove it and give some test case where it fails?

Prefix gcd ( or sum ) and suffix gcd are basic dp
Aren’t they ?

2 Likes

Yeah
My solution was same as editorialist approach People were doing another approach.
Nice proof @teja349

Can anybody please help me to figure it out in which testcase this solution is failing : https://www.codechef.com/viewsolution/24812870

My approach based on sorting. Except two testcases its passed all test case during contest.

@karangreat234 my approach of exactly same as above approach, but the approach u said can u prove mathematically. And why then Teja sir didn’t think for your approach ( means I think your approach is simply an observation).

Yahhh bro mine is also exactly same I also have same issue
https://www.codechef.com/viewsolution/24862289

Hello sir,
please provide the input that fails my code
below is my approach
Fact 1:-GCD of a set never greater than the minimum element
Fact 2:-removing an element from the set can effect the GCD of the set
Fact 3:-Fact 2 is not always true for the max element of the set

1)finding min and max elements of the set
2)divide the set based on the GCD example:S={6,10,12} leads to two sets gcd(2)={10},gcd(6)={12}
3)gcd(1) set plays the important role
4)If the set gcd(1) conatins more than one element
then result=1+max,since we have 2 elements that leads to GCD 1,we can keep all elements with gcd 1 elemets in one set and the max element in the other set
5)if the set gcd(1) having only one element
then merge the gcd sets from step 2,after merging gcd(2) ngcd(6) it gives gcd 2
now compare the result=MAX(gcd(after merge) +only element from gcd(1) ,1+max)
6)if the gcd(1) set not exisit
then find the gcd without max element of complete set and find a element that contributing more to the gcd .
gcd without max element forms 2 sets one with only max element and other is with rest
From the Fact 3:-we are finding an element that contribute more the gcd and remove that from the set and find the gcd of the set that is not having that element
that element is need not be the second max
result is which is more
Link to the solution:-
https://www.codechef.com/viewsolution/24891558

My approach, please give me a counter example if I’m wrong.

If input is of the form A A A A A A then answer is 2A
If it’s of the form A A A A A B B B B B then answer is A+B

In the third case first sort the input and get A A A A B B B C C D E E F F G H… (this is the sorted version of the input i.e A >B > C …
Now the answer is either A + gcd(B, C, D, E …) or B + gcd(A, C, D, E …). So we have to output the greater of these two values.

Here is my solution. It’s giving TLE. First let me know if my method is correct, if not please give an counter example. And if yes, then let me know the shortest method to implement my program so I don’t get TLE.
Any help will be appreciated.

Mine approach was also the same but game Wrong answer
Here it is