SUMAGCD HELP June long challenge 2019

help
1

Hello!

Please can anyone find error in my code for which subtask1 test cases are given as Wrong Answer(I understand TLE for Subtask2)

https://www.codechef.com/viewsolution/24849906

What i have simply done is for each element in array A for i, copied n-1 elements to array B except index i element of A. And simply calculated sum array B GCD and that element. And finding the max value of it. Cannot find where is the problem.

2

your code giving WA in this test case,
5
12 12 15 5 5
correct ans = 17
your code ans = 16

consider all elements in array are distinct,
then 1 group always of one elemnet,

your ans are,

for i=1 to n:
ans = max( ans, gcd(f(1,i-1), f(i+1,n)) + Arr[i] )
here, f(l,r) = gcd of all elemnts in range l to r

you can done this is in O(N) time,
precompute preffix and suffix gcd.

for i=1 to N:
ans max( ans, gcd( preffix[i-1], suffix[i+1]) + Arr[i])

3

Thanks for help Bhai.

1 Like