Sign permutation#12211

Sign permutation (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Notice that maximum sum of the permutation is the permutation itself with not doing anything which is

S = 1 + 2 + 3 + ... + n = \frac{n ( n + 1 )}{2}

\displaystyle S=1+2+3+...+n=\frac{n(n+1)}{2}

negating some element $x$ from $p$ meaning that $S \to S - 2 x$ S \rightarrow S-2x , this also applies for a sum of some subset of any length $m$ , thus we've a sufficient condition so that a permutation actually exists :

[S mod 2 = k mod 2]

[S \bmod 2 = k \bmod 2]

Thus we can get the subset sum of negated numbers to be $X = \frac{S - k}{2}$ X=\frac{S-k}{2} , We can bound the subset sum , which is at least

1 + 2 + 3 + ... + m = \frac{m ( m + 1 )}{2}

1+2+3+...+m=\frac{m(m+1)}{2}

, and at most $m$ integers from the highest

m + (n - 1) + (n - 2) + ... + (n - m + 1) = S - \frac{( n - m ) ( n - m + 1 )}{2}

m+(n-1)+(n-2)+...+(n-m+1)=S-\frac{(n-m)(n-m+1)}{2}

If $X$ is not bounded in that range , then it's obvious such permutation doesn't exists.

Finally , We can pick numbers to negate greedily , so that we always have a field to play with integers in the next move.

Solution

for _ in range(int(input())):
    n,m,k=map(int,input().split())
    S=n*(n+1)//2
    if (S-k)&1 or k>S:
        print(-1); continue
    X=(S-k)//2
    lo=m*(m+1)//2
    hi=S-(n-m)*(n-m+1)//2
    if X<lo or X>hi:
        print(-1); continue
    neg=[False]*(n+1)
    rem=m; target=X
    for i in range(n,0,-1):
        if rem==0: break
        if target>=i and target-i>=(rem-1)*rem//2:
            neg[i]=True
            target-=i
            rem-=1
    if rem or target:
        print(-1); continue
    print(*(-i if neg[i] else i for i in range(1,n+1)))

Complexity $O (n)$