PERMMODK - Editorial

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given N and K, find any permutation P such that P_i\bmod K \neq i\bmod K for all i, or claim that no such permutations exist.

EXPLANATION:

There are likely several constructions, here’s one.

The main idea behind the following construction is that i and i+1 will always have different remainders modulo K (unless K = 1).

Why?

By the definition of the mod operator, x\bmod m = y\bmod m if and only if m divides (x - y).

So, if i\bmod K = (i+1)\bmod K, K must divide (i+1 - i) = 1, which is only possible if K = 1.

So, we can try to pair up i with i+1 and vice versa, and if we’re successful, we’ll obtain a solution that’s independent of K.
If N is even, it’s easy to see that this is always possible, and we’ll obtain

[2, 1, 4, 3, 6, 5, \ldots, N, N-1]

as our permutation, which is valid as long as K\neq 1.

However, if N is odd, pairing up elements will leave one element unpaired which isn’t ideal.

To fix this, let’s look at N = 3.
Consider the permutation [3, 1, 2].
For i = 2 and i = 3, the difference between the index and value is 1, so they’ll be fine.
For i = 1, the difference between the index and the value is 2.
So, if K \gt 2 this is a valid permutation.

Once these three elements are fixed, we have N-3 elements left - but that’s an even number, so we can just do what we did for the even case and pair them up into (4, 5), (6, 7), (8, 9), \ldots
So, when N is odd and K \gt 2, we obtain

[3, 1, 2, 5, 4, 7, 6, \ldots, N, N-1]

as a valid permutation.


The only cases we haven’t taken care of with the above constructions are K = 1 for all N, and K = 2 when N is odd.

K = 1 can be trivially seen to have no solution, since all numbers modulo 1 are just 0 and hence equal.

As for odd N with K = 2, there’s no solution as well.
To see why, note that taking numbers modulo 2 is essentially reducing them to their parity.
Since we want P_i\bmod 2\neq i\bmod 2, we want to place even values at odd indices and vice versa.
But when N is odd, \frac{N+1}{2} of the elements are odd, while only \frac{N-1}{2} of the positions are even. So, we’ll always end up having to place an odd element at an odd index, which isn’t allowed - meaning no solution exists.


Putting everything together, the final solution is:

  1. If K = 1, or N is odd and K = 2, no solution exists.
  2. Otherwise,
    • If N is even, print [2, 1, 4, 3, 6, 5, \ldots].
    • If N is odd, print [3, 1, 2, 5, 4, 7, 6, \ldots].

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)
def get(n):
    a = [0]*n
    a[::2] = list(range(2, n+1, 2))
    a[1::2] = list(range(1, n+1, 2))
    return a

for _ in range(int(input())):
    n, k = map(int, input().split())
    if k == 1: print(-1)
    elif k == 2 and n%2 == 1: print(-1)
    else:
        if n%2 == 0: ans = get(n)
        else:
            ans = get(n-3) + [n-1, n, n-2]
        print(*ans)
1 Like

This topic was automatically closed after 2 hours. New replies are no longer allowed.

This topic was automatically opened after 1 minute.

This is quite a good problem to help understand how %k works with indices from 1 till n.

I did it like this. I thought that 1 till n, if we take mod k, then we will have the indices something like

1 2 3 … k-1 0 1 2 3…

Then we can use the permutation as 2 3 4 5 … n-1 n 1

Now, the only issue that will come is if the final index mod n == 1, since we are always placing 1 at that position.

Now, we just need to check if there is any index j < n, where Pj %k != 1 and j%k != 1.

If possible then we swap those. ad that’s it. otherwise not possible.

1 Like

I assume constraints were small to allow people to simply use maximum matching if they don’t want to think, I did that
https://www.codechef.com/viewsolution/1110663325

1 Like

But isn’t maximum matching an advanced topic? Using this for such a simple question is too much. Plus what I posted is easier and simpler to think. Just that shifting by 1 would derange the permutation except the last index.