Flipping Range (Codeforces 1631F)
Tags: Greedy, number theory

You are given an array $$$a$$$ of $$$n$$$ integers and a set $$$B$$$ of $$$m$$$ positive integers such that $$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$ for $$$1\le i\le m$$$, where $$$b_i$$$ is the $$$i$$$-th element of $$$B$$$. You can make the following operation on $$$a$$$:  Select some $$$x$$$ such that $$$x$$$ appears in $$$B$$$. Select an interval from array $$$a$$$ of size $$$x$$$ and multiply by $$$-1$$$ every element in the interval. Formally, select $$$l$$$ and $$$r$$$ such that $$$1\leq l\leq r \leq n$$$ and $$$r-l+1=x$$$, then assign $$$a_i:=-a_i$$$ for every $$$i$$$ such that $$$l\leq i\leq r$$$. Consider the following example, let $$$a=[0,6,-2,1,-4,5]$$$ and $$$B=\{1,2\}$$$:  $$$[0,6,-2,-1,4,5]$$$ is obtained after choosing size $$$2$$$ and $$$l=4$$$, $$$r=5$$$. $$$[0,6,2,-1,4,5]$$$ is obtained after choosing size $$$1$$$ and $$$l=3$$$, $$$r=3$$$. Find the maximum $$$\sum\limits_{i=1}^n {a_i}$$$ you can get after applying such operation any number of times (possibly zero).

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2\leq n \leq 10^6$$$, $$$1 \leq m \leq \lfloor \frac{n}{2} \rfloor$$$) — the number of elements of $$$a$$$ and $$$B$$$ respectively. The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\leq a_i \leq 10^9$$$). The third line of each test case contains $$$m$$$ distinct positive integers $$$b_1,b_2,\ldots,b_m$$$ ($$$1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$$$) — the elements in the set $$$B$$$.It's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case print a single integer — the maximum possible sum of all $$$a_i$$$ after applying such operation any number of times. 

Note: In the first test, you can apply the operation $$$x=1$$$, $$$l=3$$$, $$$r=3$$$, and the operation $$$x=1$$$, $$$l=5$$$, $$$r=5$$$, then the array becomes $$$[0, 6, 2, 1, 4, 5]$$$.In the second test, you can apply the operation $$$x=2$$$, $$$l=2$$$, $$$r=3$$$, and the array becomes $$$[1, 1, -1, -1, 1, -1, 1]$$$, then apply the operation $$$x=2$$$, $$$l=3$$$, $$$r=4$$$, and the array becomes $$$[1, 1, 1, 1, 1, -1, 1]$$$. There is no way to achieve a sum bigger than $$$5$$$.

Sample Inputs:
3
6 2
0 6 -2 1 -4 5
1 2
7 1
1 -1 1 -1 1 -1 1
2
5 1
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000
1

Sample Outputs:
18
5
5000000000

Solution (Python):
import sys
fin = sys.stdin
from functools import reduce
from math import gcd

def solve(n, m, a, b):
    b = reduce(gcd, b[1:], b[0])
    parts = [[] for _ in range(b)]
    counts = [0] * b
    total = 0
    for (i, v) in enumerate(a):
        parts[i % b].append(abs(v))
        counts[i % b] += v < 0
        total += abs(v)
    min_parts = [min(p) for p in parts]
    minus_a = 0
    minus_b = 0
    for (c, m) in zip(counts, min_parts):
        if c % 2 == 1:
            minus_a += 2 * m
        else:
            minus_b += 2 * m
    return total - min(minus_a, minus_b)
t = int(fin.readline())
for test in range(t):
    (n, m) = map(int, fin.readline().split())
    a = list(map(int, fin.readline().split()))
    b = list(map(int, fin.readline().split()))
    print(solve(n, m, a, b))

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def gcd(a, b):
    """"""
    if a < b:
        (a, b) = (b, a)
    while b > 0:
        (a, b) = (b, a % b)
    return a

def solve(N, M, A, B):
    g = B[0]
    for b in B:
        g = gcd(g, b)
    s0 = s1 = 0
    for i in range(g):
        (v0, v1) = (A[i], -A[i])
        for j in range(i + g, N, g):
            nv0 = max(v0 + A[j], v1 - A[j])
            nv1 = max(v0 - A[j], v1 + A[j])
            (v0, v1) = (nv0, nv1)
        s0 += v0
        s1 += v1
    return max(s0, s1)

def main():
    T = int(input())
    for _ in range(T):
        (N, M) = list(map(int, input().split()))
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        out = solve(N, M, A, B)
        output(f'{out}\n')
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
import math

def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    g = 0
    for i in b:
        g = math.gcd(g, i)
    res = sum([abs(i) for i in a])
    if g == 1:
        print(res)
        return
    mn = [10 ** 9] * g
    cnt = [0] * g
    for i in range(g):
        for j in range(i, n, g):
            if a[j] < 0:
                cnt[i] ^= 1
            mn[i] = min(mn[i], abs(a[j]))
    res1 = 0
    res2 = 0
    for i in range(g):
        if cnt[i]:
            res1 += mn[i]
        else:
            res2 += mn[i]
    print(res - 2 * min(res1, res2))
for _ in range(int(input())):
    solve()