Bipartite Array (Codeforces 1620F)
Tags: Greedy, dp

You are given a permutation $$$p$$$ consisting of $$$n$$$ integers $$$1, 2, \dots, n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once).Let's call an array $$$a$$$ bipartite if the following undirected graph is bipartite:  the graph consists of $$$n$$$ vertices;  two vertices $$$i$$$ and $$$j$$$ are connected by an edge if $$$i < j$$$ and $$$a_i > a_j$$$. Your task is to find a bipartite array of integers $$$a$$$ of size $$$n$$$, such that $$$a_i = p_i$$$ or $$$a_i = -p_i$$$, or report that no such array exists. If there are multiple answers, print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the size of the permutation.The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$.The sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output: For each test case, print the answer in the following format. If such an array $$$a$$$ does not exist, print "NO" in a single line. Otherwise, print "YES" in the first line and $$$n$$$ integers — array $$$a$$$ in the second line.


Sample Inputs:
4
3
1 2 3
6
1 3 2 6 5 4
4
4 1 3 2
8
3 2 1 6 7 8 5 4

Sample Outputs:
YES
1 2 3
NO
YES
-4 -1 -3 -2
YES
-3 -2 1 6 7 -8 -5 -4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u << 2 ^ v
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    dp = [inf] * (4 * n)
    b = [-1] * (4 * n)
    (dp[0], dp[1]) = (-inf, -inf)
    for i in range(n - 1):
        for j in range(4):
            if dp[f(i, j)] == inf:
                continue
            u = f(i, j)
            (x, y) = (dp[u], -p[i] if not j & 1 else p[i])
            if x < y:
                (x, y) = (y, x)
            for k in range(2):
                (z, v) = (-p[i + 1] if not k & 1 else p[i + 1], 0)
                if z > x:
                    (v, w) = (f(i + 1, k), y)
                elif z > y:
                    (v, w) = (f(i + 1, k ^ 2), x)
                if v and dp[v] > w:
                    (dp[v], b[v]) = (w, u)
    ans0 = 'NO'
    for j in range(f(n - 1, 0), f(n, 0)):
        if dp[j] ^ inf:
            (ans0, i) = ('YES', j)
            break
    ans.append(ans0)
    if ans0 == 'NO':
        continue
    ans0 = [0] * n
    ans0[-1] = -p[-1] if not i & 1 else p[-1]
    for j in range(n - 2, -1, -1):
        i = b[i]
        ans0[j] = -p[j] if not i & 1 else p[j]
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
N = 1 << 20
P = print
for _ in [0] * I()[0]:
    (n,) = I()
    p = I()
    D = [[-N, -N, N, N]]
    for i in range(1, n):
        (a, b, c, d) = [N] * 4
        (w, x, y, z) = D[i - 1]
        (q, r) = (p[i], p[i - 1])
        if q > r:
            a = w
        elif q > w:
            c = r
        if -q > w:
            d = r
        if x < a:
            a = x
        if -q > -r:
            b = x
        elif -q > x:
            d = -r
        if q > y:
            a = min(a, r)
        elif q > r:
            c = y
        if q > z:
            a = min(a, -r)
        else:
            c = min(c, z)
        if -q > z:
            b = min(b, -r)
        elif -q > -r:
            d = min(d, z)
        D.append([a, b, c, d])
    if D[-1] == [N] * 4:
        P('NO')
    else:
        P('YES')
        (i, x, y) = (n, N - 1, N - 1)
        while i > 0:
            i -= 1
            (a, b, c, d) = D[i]
            v = p[i]
            if a <= y and v <= x:
                (x, y) = (v, a)
            elif b <= y and -v <= x:
                (x, y) = (-v, b)
                p[i] = -v
            elif c <= x and v <= y:
                (x, y) = (c, v)
            elif d <= x and -v <= y:
                (x, y) = (d, -v)
                p[i] = -v
        P(' '.join(map(str, p)))

Solution (Python):
import sys
inpu = sys.stdin.readline
prin = sys.stdout.write
I = lambda : [*map(int, inpu().split())]
big = 1 << 20
(t,) = I()
for _ in range(t):
    (n,) = I()
    p = I()
    dp = [[-big, -big, big, big]]
    for i in range(1, n):
        (a, b, c, d) = (big, big, big, big)
        y = dp[i - 1][0]
        if p[i] > p[i - 1]:
            a = y
        elif p[i] > y:
            c = p[i - 1]
        if -p[i] > y:
            d = p[i - 1]
        y = dp[i - 1][1]
        if y < a:
            a = y
        if -p[i] > -p[i - 1]:
            b = y
        elif -p[i] > y:
            d = -p[i - 1]
        x = dp[i - 1][2]
        if p[i] > x:
            a = min(a, p[i - 1])
        elif p[i] > p[i - 1]:
            c = x
        x = dp[i - 1][3]
        if p[i] > x:
            a = min(a, -p[i - 1])
        else:
            c = min(c, x)
        if -p[i] > x:
            b = min(b, -p[i - 1])
        elif -p[i] > -p[i - 1]:
            d = min(d, x)
        dp.append([a, b, c, d])
    if dp[-1] == [big, big, big, big]:
        print('NO')
    else:
        print('YES')
        i = n - 1
        x = big - 1
        y = big - 1
        while i >= 0:
            (a, b, c, d) = dp[i]
            val = p[i]
            if a <= y and val <= x:
                (x, y) = (val, a)
            elif b <= y and -val <= x:
                (x, y) = (-val, b)
                p[i] = -val
            elif c <= x and val <= y:
                (x, y) = (c, val)
            elif d <= x and -val <= y:
                (x, y) = (d, -val)
                p[i] = -val
            i -= 1
        print(' '.join((str(guy) for guy in p)))