PER_MOD - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: danishiitp_24
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, find a permutation P of \{1, 2,3, \ldots, N\} such that:

  • P_i \neq i for every 1 \leq i \leq N
  • The set of distinct values of P_i\ \% \ i is as small as possible.

EXPLANATION:

Short answer

P = [2, 3, 4, 5, \ldots, N, 1] is what we want.

How do I come up with this?

First, let’s make a couple of observations:

  • No matter what P_1 is, P_1 \ \% \ 1 = 0 since 1 divides every integer.
  • We aren’t allowed to have P_1 = 1; so there’s some i \gt 1 with P_i = 1. No matter what i this is, P_i \ \% \ i = 1 \ \% \ i = 1.

So, no matter what P we choose, the set of remainders will always contain 0 and 1.
Ideally, we’d like to ensure that no other remainders are created, so that the number of distinct P_i \ \% \ i values remains as 2.

A remainder of 0 is obtained when P_i is a multiple of i. However, since we can’t choose P_i = i, it’s not possible to achieve this for most of the positions, so we need to try and make many of the remainders 1.

It’s not hard to see that the easiest way to get a remainder of 1 is via (i+1)\ \% \ i.
In fact, this can be done for every i = 1, 2, 3, \ldots, N-1. This allows us to place all the elements except 1.
1 can then be placed at the last position, and we’re done.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++) 
#include <bits/stdc++.h>
#define int long long 
 using namespace std;

    
signed main() {
       int t;
       cin>>t;
       while(t--)
       {  
            int n;
           cin>>n;
        
       
           for(int i=1;i<n;i++)
          cout<<i+1<<" ";
          cout<<1;
          cout<<"\n";
        
       }
	return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
	n = int(input())
	ans = list(range(2, n+1)) + [1]
	print(*ans)