GCDISCOUNT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author & Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums, basic properties of GCD

PROBLEM:

There are N ingredients to be bought, the i-th of them has price A_i.
At most one ingredient can be bought for the price of B_i, instead of A_i.
Find the maximum possible GCD of costs of purchases.

EXPLANATION:

Let’s first start with a simple quadratic algorithm.

For each i from 1 to N, we’ll try to see what happens if we use the discount coupon on item i.

  • To do that, we find the GCD of the elements A_1, A_2, \ldots, A_{i-1}, B_i, A_{i+1}, A_{i+2}, \ldots, A_N
    This can be done in linear time by just iterating across the array,

The final answer is the maximum of the values obtained this way.
To optimize this, notice that the values we’re computing the GCD of have a rather special structure — other than B_i itself, they form a prefix and suffix of A.
That is, you have the pieces
[A_1, A_2, \ldots, A_i], [B_i], [A_{i+1}, A_{i+2}, \ldots, A_N]

So, instead of having to recompute these each time, let’s precompute them all!
Let \text{pref}[i] = \gcd(A_1, A_2, \ldots, A_i) and \text{suf}[i] = \gcd(A_i, A_{i+1}, \ldots, A_N).
Then,

  • \text{pref}[i] = \gcd(A_i, \text{pref}[i-1])
  • \text{suf}[i] = \gcd(A_i, \text{suf}[i+1])

So all N values of \text{pref} and \text{suf} can be computed in \mathcal{O}(N) time in total.

Once they’re computed, processing an index is easy: the resulting GCD is simply
\gcd(B_i, \text{pref}[i-1], \text{suf}[i+1]).

So, we’ve found the answer for each index in \mathcal{O}(\log{\max A}) time (this is the complexity of computing GCD itself fast, using the Euclidean algorithm).
Simply take the maximum of them all as the final answer.
Don’t forget to include the case where no B_i is chosen, i.e, just the GCD of the entire A array.

The entire problem is thus solved in \mathcal{O}(N\log{\max A}) time.

TIME COMPLEXITY

\mathcal{O}(N\log{\max A}) per testcase.

CODE:

Author's code (Python) 
import math
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    pref, suf = [0]*n, [0]*n
    for i in range(n):
        pref[i] = a[i]
        suf[n-1-i] = a[n-1-i]
        if i > 0:
            pref[i] = math.gcd(pref[i], pref[i-1])
            suf[n-1-i] = math.gcd(suf[n-1-i], suf[n-i])

    ans = pref[n-1]
    for i in range(n):
        cur = b[i]
        if i > 0: cur = math.gcd(cur, pref[i-1])
        if i+1 < n: cur = math.gcd(cur, suf[i+1])
        ans = max(ans, cur)
    print(ans)
1 Like