# PERFPERM - Editorial

Setter: S.Manuj Nanthan
Tester: Harris Leung
Editorialist: Kanhaiya Mohan

Easy

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
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;
}

4 Likes

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int A[n];
A[0]=1;
for(int i=1;i<k;i++){
A[i]=i+1;
}
for(int i=k;i<n;i++){
A[i]=i+2;
}
for(int i=0;i<n;i++){
cout<<A[i]<<" “;
}
cout<<”\n";
}

}
Can you please rectify the error?

t=int(input())

while(t):
t=t-1
n,k=map(int,input().split())
arr=[0]*n

if n%2==0:
for i in range(n):
arr[i]=n-i
if k%2==0:
for i in range(k//2):
arr[i],arr[n-1-i]=arr[n-1-i],arr[i]
else:
for i in range(k//2):
arr[i+1],arr[n-2-i]=arr[n-2-i],arr[i+1]
print(*arr)

else:
for i in range(n):
arr[i]=n-i-1
arr[n-1]=n
if k==1:
arr[0],arr[n-1]=arr[n-1],arr[0]
elif k==2:
check=0
elif k%2==1:
for i in range(k//2 ):
arr[i],arr[n-2-i]=arr[n-2-i],arr[i]
else:
for i in range(k//2 - 1):
arr[i+1],arr[n-3-i]=arr[n-3-i],arr[i+1]
print(*arr)

Can anyone provide a test case where this solution gives the wrong output?

I got all the 3 observations mentioned in the hints, but wasnt able to make an algo using it.
Can anyone give some tips to get better at making algos

2 Likes

My solution

#include <bits/stdc++.h>
#define int long long int

void solve(){
int n, k;
std::cin >> n >> k;
std::vector <int> v;
for(int i=0; i<n; i++){
v.push_back(i+1);
}
if(n%2 != k%2){
std::swap(v[0], v[1]);
}
int i = n-1;
while(k+2 <= n){
std::swap(v[i], v[i-1]);
i -= 2;
k += 2;
}
for(int i=0; i<n; i++){
std::cout << v[i] << " ";
}
std::cout << "\n";
}

signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t = 0;
std::cin >> t;
//t = 1;
while(t--){
solve();
}
}


My Solution:

#include<bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define F first
#define S second
#define MOD 1000000007

using namespace std;

typedef long long int ll;

void solve()
{
int n, k;
cin >> n >> k;
vector <int> v(n + 1);
if(k == n - 1)
{
v[1] = n;
for(int i = 2; i < n; i++) v[i] = i;
v[n] = 1;
}
else
{
for(int i = 1; i <= k; i++) v[i] = i;
for(int i = k + 1; i <= n - 1; i++) v[i] = i + 1;
if(k != n)
v[n] = k + 1;
}

for(int i = 1; i <= n; i++) cout << v[i] << " ";
cout << "\n";
}

int main()
{
FAST_IO
int t = 1;
cin >> t;
while(t--)
{
solve();
}
return 0;
}

1 Like

5
6 1
1 3 4 5 6 7
6 2
1 2 4 5 6 7
6 3
1 2 3 5 6 7
6 4
1 2 3 4 6 7
6 5
1 2 3 4 5 7

you are getting wrong answer with testcases, as you have to print all number from
1 to n. Please refer editorial for better understanding

Or you can refer my code:
#include<bits/stdc++.h>
#define flash ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
using namespace std;

void solve(){
int n,k;
cin>>n>>k;
int a[n+1];
for(int i=1;i<=n;i++)
a[i]=i;
if(k==n){
for(int i=1;i<=n;i++)
cout<<a[i]<<" “;
cout<<”\n";
}
else if(k==1){
for(int i=2;i<=n;i++){
cout<<i<<" ";
}
cout<<“1 “;
cout<<”\n”;
}
else{
cout<<"2 ";
for(int i=2;i<=n;i++){
if(i==(n-k+1)){
cout<<“1 “;
k=i;
break;
}
else
cout<<i+1<<” “;
}
for(int i=k+1;i<=n;i++){
cout<<i<<” “;
}
cout<<”\n”;
}
}

int32_t main(){
flash;
int tc;
cin>>tc;
while(tc–)
{
solve();
}
}

1 Like

what is the problem in this logic? why it is showing wrong answer after submission ?
for _ in range(int(input())):
N,K=map(int,input().split())
count=1
l=[]
for i in range(1,N+1):
if count<=K:
l.append(i)
count=count+1
else:
l.append(i+1)
print(*l)

Take these values:
4
5 1
5 2
5 3
5 4

output->
1 3 4 5 6
1 2 4 5 6
1 2 3 5 6
1 2 3 4 6
It is not printing all numbers from 1 to n.
please refer editorial for better understanding.

1 Like
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
int a[n+1];
int i;
for (i=1; i<=n; i++)
a[i] = i;
if (k+1<=n){
int j= k+1;
for (; j<n; j++)
swap(a[j],a[j+1]);
}
if (k<n){
swap(a[1],a[n]);
}
for (int p = 1; p<=n; p++)
cout << a[p] << " ";
cout << endl;
}
return 0;
}



can anyone tell me the test case this code is failing:

void solve(){
int n,k; cin >> n >> k;
vector ans;
if(k == n-1){
for(int i=0;i<n;i++){
if(i+1 == 1){
ans.push_back(k);
continue;
}
if(i+1 == k){
ans.push_back(1);
continue;
}
ans.push_back(i+1);
}
for(int i=0;i<ans.size();i++){
cout << ans[i] << " ";
}
cout << endl;
return;
}
if(k == n){
for(int i=1;i<=n;i++){
cout << i << " ";
}
cout << endl;
return;
}
for(int i=1;i<=k;i++){
ans.push_back(i);
}
for(int i=k+2;i<=n;i++){
ans.push_back(i);
}
ans.push_back(k+1);
for(int i=0;i<ans.size();i++){
cout << ans[i] << " ";
}
cout << endl;
}

Can anyone hep why this is giving WA ? please

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define vs vector

#define vi vector

#define vll vector

#define vc vector

#define mv(a) *max_element(a.begin(), a.end())

#define f(i, a, n) for (int i = a; i < n; i++)
int main()

{

IOS;

int t;

cin >> t;

// t = 1;

while (t--)

{

int n, k;

cin >> n >> k;

vector<bool> flag(n + 1, false);

vi arr(n);

if (k == n)

{

f(i, 1, n + 1)

{

cout << i << " ";

}

}

else

{

arr[0] = n;

flag[n] = true;

cout << n << " ";

f(i, 1, k)

{

arr[i] = i + 1;

cout << arr[i] << " ";

flag[arr[i]] = true;

}

f(i, 1, n + 1)

{

if (flag[i] == false)

cout << i << " ";

}

}

cout << "\n";

}

return 0;


}

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
vectorv(n+1);
for(int i=1;i<=n;i++){
v[i]=i;
}
for(int i=1;i<=n;i++){
if(i<=k)
continue;
else if(i>k && i!=n)
swap(v[i],v[i+1]);

    }
for(int i=1;i<=n;i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
return 0;


}

////bro why its showing wrong in contest also i tried to swap two consecutive no so that v[i] is not divisible by i

Take n=2 and k=1:
your output-- 1 2 which is wrong, this is valid for k=2.

correct output should be 2 1 because it should divide index exactly k times.

In order to confirm, I submitted your code from my account(after removing some syntax errors), and it got accepted.
Check here: Solution: 58878482 | CodeChef

Hey, your code has a lot of syntactically incorrect. Please try to remove those errors and try again.

https://www.codechef.com/viewsolution/59117765

This code is giving Wrong Answer.

#include
using namespace std;

int main() {
int t;
cin>>t;

while(t--)
{
int n,k;
cin>>n>>k;
int i;

int A[n+1];
for(i=1;i<n+1;i++)
{
A[i]=i;
}

if(k==n)
{
//do nothing
}
else
{
int x=n-k;
for(i=k+1;i<=n;i++)
{
A[i]=A[i]+1;


//all the remaining values just increment by one to not make them divisible and that’s it.
}
}

        for(i=1;i<n+1;i++)
{
cout<<A[i]<<" ";
}

cout<<endl;

}
return 0;


}

tell me the test case where mycode not working.