You missed a very impotant point. Not to take single element on side but rather take all elements of that value together. Best achievable by removing duplicates from array first 
See GCD is maximum only if there are similar elements na. Adding a dissimilar element, would just decrease the GCD. Let’s say the max element is MAX. The rest elements can have any GCD from 1 to <MAX so answer will be at least MAX+1. But if you put MAX alongwith some other dissimilar element, it will make the GCD at least MAX/2 if not lesser, and now the other half would have to be at least MAX/2 + 1 if it has to surpass the previous max value of MAX+1 that we got, which is not possible.
1 Like
Hello,this is my greedy approach of the same problem.
this code did not pass one test case in constraint 1 and 3 test case in constraints 2.
I don’t know where is the problem, I tried almost every corner case but don’t know where is this going wrong.
Please let me know if anyone can help.
Are you sure about O(n),as i can see there is n*log(n) complexity.
brute force approach also works if used with a little “jugaad”. I am checking all possible solutions using recursion, but breaking the recursive calls as soon as I find that the answer can be found without making further recursive calls.
Rigorous proof… Let x = \max_1(S) + \gcd(S\setminus\{\max_1(S)\}), y = \max_2(S) + \gcd(S\setminus{\max_2(S)}), where \max_1(S), \max_2(S) are the largest and second largest elements of the set S. (Assume all the duplicates were removed.) Let A, B be an arbitrary partition of the set, and assume WLOG that \max_1(S) belongs to A. If there are no other other elements in A besides for \max_1(S), then \gcd(A) + \gcd(B) = x. Otherwise, \gcd(A) \leq \max_1(S)/2, because all other elements are < \max_1(S). Meanwhile, \gcd(B) \leq \max_2(S) because all elements of B are \leq \max_2(S). If \gcd(B) = \max_2(S), then \gcd(A) + \gcd(B) = y, otherwise \gcd(B) \leq \max_2(S)/2, so \gcd(A) + \gcd(B) \leq \max_1(S)/2 + \max_2(S)/2 < \max_1(S) < x, and this certainly doesn’t achieve the max. This proves the max is either x or y.
5 Likes
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=ne 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
I already mention to convert into set.
Hello Karangreat234,please review my code
please send me some test inputs to fail my code
please review my code
please send me some test inputs to fail my code
please review my code
please send me some test inputs to fail my code
check for :-
4, 4, 4, 4
10, 15, 14
4, 4, 7, 6
6, 12, 16, 18
3, 8, 9
100, 100, 150, 300
Hello Wingman_7 sir,
Thanks for you input
I forgot to clear one of my collection for every test case that is the reason it has failed
after adding that line
i got below results
6
4
4 4 4 4
3
10 15 14
4
4 4 7 6
4
6 12 16 18
3
3 8 9
4
100 100 150 300
8
19
9
22
11
350
but still 2 test cases are failing from large input can you provide that input
practice section link
https://www.codechef.com/viewsolution/24862289
one more thing they are just saying WA,if they mention NZAC then i could caught this
1 Like
Checking all of them can be done in O(n)
No need to prove 2nd point
Check official editorials
Well, no need to thank me I got those inputs from my friend, after the contest got over I was discussing this question with him along with these inputs he gave me.
Please read this post or any other editorial from where you can understand the concept.
I think these inputs covered all the corner cases, when I started solving this question during the contest I didn’t created any inputs from my side instead just worked on the logic.
I tried reading your code, damn it’s too long!.. try to keep it simple and add comments, give proper variable names etc. If you understand C++, please have a look at my solution.
Thanks for looking my code and you comment.please ask you friend to get the test cases to fail my code
please see my code in practice
https://www.codechef.com/viewsolution/24862289
Well I want you to yourself debug the error… this is a very important part of learning
Hello sir,
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) +max ,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
provide input that fails my code
Regards
Samuel
Nice proof