# SUMAGCD easiest Editorial

Editorial:

1. Use set to store the unique elements from all the given elements.
2. Find the GCD of all the unique elements(say X) except the last two elements i.e. maximum and second maximum elements.
3. now find max from GCD (X, second maximum)+ maximum and GCD (X, maximum)+ second maximum.
4. That’s it, you have got the maximum element as the ans.
8 Likes

And that’s not an easy editorial at all cuz you never explained why are you doing those steps

27 Likes

How yoy reached to the above conclusion

Even i followed the same approach, but i understood the logic after trying to find the max GCD of various different problems, but i still was in doubt as to why that approach worked in the first place. If anyone here could provide a concrete proof as to why the following approach works, it would be great!

2 Likes

This proof is not very rigorous but I hope it gives some intuition. So the first thing is to realize that the highest (let’s call its value max) and the second highest unique elements cannot be in the same subsequence. Let’s say they were in the same subsequence, then the GCD of the group containing both of them can be at most the max / 2. This is because the prime factorization of the highest element might look p1 * p2 * … pk, and the GCD of the subsequence would be maximized if the second highest contained all these primes p1…pk except the smallest one (they have to be unique). In the best case that prime is 2.

Now, in the best case the other subsequence just has one element, the third highest, but since that is less than the second highest it can also only be max / 2. So overall the total can only be max, but in that case we are just better off putting the max alone in one subsequence, and the other subsequence will have gcd at least 1, which will give us max + 1.

By the same logic, we can also see that both subsequences cannot have more than 1 unique element, because if they did the highest gcd for both would be max / 2, which only yields a total of max. So, you see which one is better, putting the highest separately or the second highest and then output your solution.

9 Likes

first of all GCD of two no.s is always a no. less than or equal to the smaller no.
After doing some observations i got to know the exact steps.
And it is an easy editorial because complexity of a soln doesn’t depend upon its explanation.
The steps are easy to understand and might not be difficult for a top 100 coder of INDIA.

2 Likes

Absolutely correct explained.

1 Like

Bro but your editorial is not required for top coders…they solve by their own…only new coders need it so you need to explain well …
I got it and hv no issues but saying all this just to realize you what you said…

7 Likes

Could you please help me to find out a test case where my code for SUMAGCD fails?

code

What observation? Hit and trial is not observation. You gotta prove it bro.

3 Likes

please give some input to fail my code
https://www.codechef.com/viewsolution/24828838

In one subsequence,we have put either the max element or the second max element…Why are we not checking all the elements in that subsequence?

Yeah that easy but not an editorial

I have a solution which take one element in one set and rest of them in another and it is O(n) also but still what is the proof that one set will only have one value elements ?

what’s wrong here
give me runtime error

import math
t = int(input())
while t>0 :
n = int(input())
l = set(map(int,input().split()))
l = list(l)
l.sort()
#print(l)
if(len(l)==1):
print(2*l[0])
elif(len(l)==2):
print(l[0]+l[1])
elif(len(l)>2):
fmax = l[-1]
smax = l[-2]
gcd3 = l[0]
for i in range(0,n-2):
gcd3 = math.gcd(gcd3,l[i])
gcd1 = math.gcd(gcd3,smax) + fmax
gcd2 = math.gcd(gcd3,fmax) + smax
if(gcd1>gcd2):
print(gcd1)
else:
print(gcd2)
t-=1

I used the same approach . But yours seems cleaner

Read the official editorial . The reason to put a single element in one set is explained clearly.

I know but it’s not in this editorial !!
It’s incomplete !!

1 Like

Wish !!! had a haha react option…

Solution Approach :

==> Reason for two maximum distinct number not being in same set :

The easiest maximum you will get is (maximum number + 1).
Now the GCD of two distinct numbers is always <= (maximum of two numbers/ 2)

if i did so, the maximum value i can now reach is (Third maximum + 1 :: In case max two number’s gcd goes to zero) or (maximum of the given values :: How -> see this example 70,35,35,35)

But i have (maximum + 1) in my pocket already with me.

==> Reason for taking GCD of rest of the numbers and putting it in only one set :
GCD of two numbers is always <= (maximum of two numbers/ 2)

Now instead of making both the maximum number be divided by 2 halves we should make only one which suits the best for the maximum answer because again i have (maximum + 1) in my pocket already with me.

Hope this would help