We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Absolute Permutation
  5. Discussions

Absolute Permutation

  • landonkoo0207
     + 14 comments

    There are many clever solutions in the discussion, but they aren't exactly straightfoward to me, so I've worked out myself.

    First, there are two exception cases, like below:

    1.k == 0: print all the numbers from 1 to N

    2.if (n / k) % 2 is not ZERO, print -1 (as this must be zero to be abolute permutation)

    Otherwise, follow the pattern below:

    if we go from 1 to N (i),

    Permutation is either i+k or i-k. It always starts with i+k.

    1.Put i+k to permutaion for k times

    2.Switch to i-k for k times

    • repeat 1 & 2 until the end.

    my python3 solution is below:

    t = int(input().strip())
for a0 in range(t):
    n,k = map(int, input().split(" "))
    
    if k == 0:
        print (*list(range(1, n+1)))
    elif (n/k) % 2 != 0:
        print ("-1")
    else:
        add = True
        perm = []
        
        for i in range(1, n+1):
            if add:
                perm.append(i+k)
                
            else:
                perm.append(i-k)
                
            if i % k == 0:
                if add:
                    add = False
                else:
                    add = True
        print (*perm)