Vasiljko's blog

Maximum GCD of new sequence
By Vasiljko, history, 7 years ago, In English

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

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here's a solution:

First, we'll look at it from a different angle: we need to choose k distinct 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 of S.

How many divisors does S have? Since it's up to 106, 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 k subarrays, so that the gcd will be X. The idea is that we build the maximal amount of subarrays we can, greedily: we start from left to right, maintaining a value sum = 0. We start adding the elements from left to right, until sum is divisible by X. we mark this location as the end of the 1st subarray and set sum = 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 as k, it means that we're able to make a partition into k subarrays with gcd X. (If we got, say, k + 4 subarrays, we can just merge the first 5 together and we get k subarrays).

So, we can do this process in O(n), and we do it for every divisor of S, a total of 240 in worst case, then the time is just 240 * N which is fine by the constraints.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much, but why does greedy work?

    UPD: Nevermind, I got it.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      The greedy part here was that, once sum becomes divisible by X, 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 sum is divisible by X. This location will be named loc1. (We'll denote it as [1, loc1] is divisible by X). Now, instead of picking this as the end, let's not go greedy and keep going until the next location where sum is divisible by X, let it be loc2. By the same way, we can keep not taking the current subarray and keep going, let's say until we reached some locZ, 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, loc1], [1, loc2], [1, loc3], ...., [1, locZ]. 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, loc1], [loc1 + 1, loc2], [loc2 + 1, loc3], .... are all divisible by X too (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 pick all the subarrays we have in the set. So obviously this greedy approach gives a better result.

      UPD: nevermind, you got it :)

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply