PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: S.Manuj Nanthan
Tester: Harris Leung
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
An index i in a permutation P of length N is said to be good if:
- P_i is divisible by i
You are given 2 integers N and K. You need to construct a permutation P of length N such that exactly K indices in that permutation are good.
If no such permutation exists, output -1.
If multiple such permutations exist, output any.
EXPLANATION:
Hints
- Two consecutive numbers, X and X+1 are coprime. Thus, X+1 can never be divisible by X.
- A number X can never be divisible by a number Y, if X<Y.
- A number is always divisible by itself and by 1.
Solution
Let us construct a solution based on above hints.
K is equal to N
In this case, P_i should be divisible by i for all 1 \leq i \leq N.
Only the identity permutation satisfies this condition.
Thus, if K=N, we can set P_i = i for all 1 \leq i \leq N. This way all indices 1 \leq i \leq N are good.
K is not equal to N
Let X = (N-K). We can rephrase the problem as: Find a permutation P such that there are exactly X indices in the permutation P that are not good.
For two indices i and (i+1), we can make them not good by setting P_i = (i+1) and P_{i+1} = i. In other words, we swap the values at indices i and (i+1) in the identity permutation.
We can construct a solution as following:
- Start with the identity permutation. This means, set P_i = i for all 1 \leq i \leq N.
- Leave the first K values of the permutation unchanged. Thus, the first K indices of permutation are good.
- After the first K indices, start swapping the values of consecutive elements in pairs. This means, we swap (P_{K+1}, P_{K+2}), (P_{K+3}, P_{K+4}), (P_{K+5}, P_{K+6}) and so on. By swapping the elements on these indices, we make these indices not good.
- We need X not good indices.
β If the value of X is even, all the X elements after the first K elements can be grouped into pairs of two and elements of each pair can be swapped.
β If the value of X is odd, the element P_N would be left alone. In this case, we can swap P_N with P_1. This way the first element of the sequence would become N (which is divisible by the index (1)), and, the last element of the sequence becomes 1 (which is not divisible by index (N)). This way, only the first K indices of the sequence are good.
Note that this way, a permutation can be constructed for all possible values of K and thus, the answer is never -1.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
#from itertools import *
#from math import *
#from bisect import *
#from collections import *
#from random import * # ( : ): ( :) : (: ) : ( ): ) : )
#from decimal import *
#from heapq import *
#from itertools import * # Things Change ....remember :)
import sys
input=sys.stdin.readline
def inp():
return int(input())
def st():
return input().rstrip('\n')
def lis():
return list(map(int,input().split()))
def ma():
return map(int,input().split())
t=inp()
while(t):
t-=1
n,k=ma()
res=[i for i in range(1,n+1)]
if(k!=n):
res[0]=n
pre=1
for i in range(k,n):
res[i],pre=pre,res[i]
print(*res)
else:
print(*res)
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
ll pw(ll x,ll y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
ll res=pw(x,y/2);
return res*res%mod;
}
int a[200001];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
int n,k;
cin >> n >> k;
for(int i=1; i<=n ;i++) a[i]=i;
if(k==1){
cout << n << ' ';
for(int i=1; i<n ;i++) cout << i << ' ';
cout << '\n';
}
else if(k%2==n%2){
for(int i=0; i<(n-k)/2 ;i++){
swap(a[n-i*2],a[n-i*2-1]);
}
for(int i=1; i<=n ;i++) cout << a[i] << ' ';
cout << '\n';
}
else{
for(int i=0; i<=(n-k)/2 ;i++){
swap(a[i*2+1],a[i*2+2]);
}
for(int i=1; i<=n ;i++) cout << a[i] << ' ';
cout << '\n';
}
}
}
Editorialist's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
int a[n+1];
for(int i = 1; i<=n; i++) a[i] = i;
if(k != n){
int x = n-k;
for(int i = k+1; i+1<=n; i+=2){
swap(a[i], a[i+1]);
}
if(x%2){
swap(a[1], a[n]);
}
}
for(int i = 1; i<=n; i++) cout<<a[i]<<' ';
cout<<endl;
}
return 0;
}