PERFPERM - Editorial

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

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 :slight_smile:

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() {
// your code goes here
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.

Your code is correct.
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.
Can anybody please help to find the mistake in this code.

#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.