Given array A of N elements. We are allowed to do one operation: merge two elements A[i] and A[i+1] into A[i]+A[i+1]. We need to find sequence of exactly K elements with maximum possible GCD.

1 <= K < N <= 10^5

A[i] <= 10^6

sum of all A[i]'s <= 10^6

Input: 6 3

12 7 3 2 15 15

Output:

6

12 12 30

Is there a link to the problem? I believe I have a solution but I want to make sure this isn't in any running contest right now.

https://petlja.org/BubbleBee/r/Problemi/2012-okruzno-ss-nzd

Just click "Posalji" which means "Submit". This is the problem from previous competitions in Serbia.

You can get WA even if your solution is correct, because checker doesn't accept different solutions to some tests.

Here's a solution:

First, we'll look at it from a different angle: we need to choose

kdistinct subarrays (continuous), taking a total of the whole array, so that the gcd of all the subarray sums is maximal.Now, by this observation, we can see that since all the subarrays' sums will be divisible by some number, then obviously, the whole array sum must be divisible by that number either. Let the sum of the whole array be

S. The answer must be a divisor ofS.How many divisors does

Shave? Since it's up to 10^{6}, on worst case (maximal amount) it will have 240 divisors (see highly composite number).Now, suppose we check if there's a valid partition to

ksubarrays, so that the gcd will beX. The idea is that we build the maximal amount of subarrays we can, greedily: we start from left to right, maintaining a valuesum= 0. We start adding the elements from left to right, untilsumis divisible byX. we mark this location as the end of the 1st subarray and setsum= 0, and do the process again from the new location. (I'll add on why greedy works if you want to but you can prove it by yourself).So now we formed the maximal amount of subarrays we can, in

O(n). If this amount of subarrays is at least as big ask, it means that we're able to make a partition intoksubarrays with gcdX. (If we got, say,k+ 4 subarrays, we can just merge the first 5 together and we getksubarrays).So, we can do this process in

O(n), and we do it for every divisor ofS, a total of 240 in worst case, then the time is just 240 *Nwhich is fine by the constraints.Thank you so much, but why does greedy work?

UPD: Nevermind, I got it.

The greedy part here was that, once

sumbecomes divisible byX, we end the current subarray and start a new one. Let's prove that this gives the maximal amount of subarrays we pick:Let's say we're now picking the first subarray, and we found the first location where

sumis divisible byX. This location will be namedloc_{1}. (We'll denote it as [1,loc_{1}] is divisible byX). Now, instead of picking this as the end, let's not go greedy and keep going until the next location wheresumis divisible byX, let it beloc_{2}. By the same way, we can keep not taking the current subarray and keep going, let's say until we reached someloc_{Z}, and we picked this location as the end of the first subarray.So what do we know? We know that all the following subarrays have a sum divisible by

X: [1,loc_{1}], [1,loc_{2}], [1,loc_{3}], ...., [1,loc_{Z}]. From this set of subarrays we can only pick one, since they all start from the 1st element.Notice how, by the above, we can derive that: [1,

loc_{1}], [loc_{1}+ 1,loc_{2}], [loc_{2}+ 1,loc_{3}], .... are all divisible byXtoo (this is just as saying that if 2 numbers are divisible by a 3rd, then their difference is divisible by the 3rd aswell). However, on the 2nd case we can actually pickallthe subarrays we have in the set. So obviously this greedy approach gives a better result.UPD: nevermind, you got it :)

The maximum number isn't 1e6, it's 1e6*1e5, so this solution will not work, you have to find those divisors and loop rep(i,divisors.size(),i++)rep(j,1e6*1e5,j+=divisors[i]) and count the occurences of accumilative array vals in a multi set, first val that counts >=k is the ans.

"sum of all A[i]'s <= 10^6"

aw didn't see that, stupid useless constraint :D , but tho if it's not existing i wouldn't be able to loop 1e11 times if i reached the 1 divisor or 2 or those small values.