Flipping Range (Codeforces 1630D)
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
I = lambda : [*map(int, sys.stdin.readline().split())]

def consec(a):
    tot = 0
    big = float('inf')
    neg = 0
    for guy in a:
        tot += abs(guy)
        if abs(guy) < big:
            big = abs(guy)
        if guy < 0:
            neg += 1
    if neg % 2 == 0:
        return (tot, tot - 2 * big)
    return (tot - 2 * big, tot)
import math

def main():
    (n, m) = I()
    a = I()
    b = I()
    g = b[0]
    for i in range(1, m):
        g = math.gcd(g, b[i])
    if g == 1:
        print(sum((abs(guy) for guy in a)))
        return
    tot = 0
    tot1 = 0
    for i in range(g):
        guy = []
        j = i
        while j < n:
            guy.append(a[j])
            j += g
        (x, y) = consec(guy)
        tot += x
        tot1 += y
    print(max(tot, tot1))
(t,) = I()
for _ in range(t):
    main()

Solution (Python):
import math
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = [0] * n
    for i in range(n):
        if a[i] < 0:
            a[i] *= -1
            c[i] = 1
    g = b[0]
    for i in b:
        g = math.gcd(g, i)
    (u, v) = (0, 0)
    for i in range(g):
        mi = inf
        x = 0
        for j in range(i, n, g):
            mi = min(mi, a[j])
            x ^= c[j]
        if x:
            u += 2 * mi
        else:
            v += 2 * mi
    ans0 = sum(a) - min(u, v)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import io
import os
from functools import reduce
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def solve(n, a, k):
    ans = sum(map(abs, a))
    cnt = [0] * k
    lo = [float('inf')] * k
    for i in range(n):
        if a[i] < 0:
            cnt[i % k] += 1
        lo[i % k] = min(lo[i % k], abs(a[i]))
    m1 = 0
    m2 = 0
    for i in range(k):
        if cnt[i] % 2 != 0:
            m1 += lo[i]
        else:
            m2 += lo[i]
    return ans - min(m1, m2) * 2

def main():
    t = int(input())
    for _ in range(t):
        (n, m) = [int(word) for word in input().strip().split()]
        a = [int(word) for word in input().strip().split()]
        b = [int(word) for word in input().strip().split()]
        print(solve(n, a, reduce(gcd, b)))
if __name__ == '__main__':
    main()