PERMCON - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given N and K, construct a permutation P such that P_i \neq i and P_i\bmod K = i\bmod K for every i.

EXPLANATION:

We want indices and values to be equal modulo K.
So, let’s split the indices from 1 to N into groups modulo K: the first group is indices 1, K+1, 2K+1, \ldots, the second group is 2, K+2, 2K+2, \ldots and so on.

Let’s look at the group corresponding to r (where 1 \leq r \leq K).
This means the indices r, r+K, r+2K, \ldots
These indices must contain the values r, r+K, r+2K, \ldots in some order, as long as indices and values differ.

If there’s only a single index, and a single value to place there (i.e. r+K \gt N so we only have r to work with), we’re forced to set P_r = r to satisfy the modulo condition, so no valid permutation can exist.
If there are at least two indices, a valid rearrangement always exists.

A simple construction is as follows.
Let the indices be r, r+K, r+2K, \ldots, r+xK.
Then, place the value r at index r+K, value r+K at index r+2K, and so on.
That is, for each 0 \lt i \leq x, set P_{r + iK} = r + (i-1)K.
This leaves only the index r empty, with the element r+xK unplaced, so place it there to finish.

Do this for each 1 \leq r \leq K, and that solves the problem.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    p = [0]*(n+1)
    for i in range(1, n+1):
	    # Place i at i+k	    
        x = i + k
        if x > n: x = (i-1)%k + 1 # Unless i+k is too large, then go to the smallest index instead
        p[x] = i
    for i in range(1, n+1):
        if p[i] == i: # Invalid
            p = [-1, -1]
            break
    print(*p[1:])
1 Like