PROBLEM LINK:
Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Given a positive integer N and an integer k where 0 \leq k \leq N, we need to find a permutation p of numbers from 1 to N which has exactly k fixed points. A fixed point is defined as an index i for which p_i = i.
QUICK EXPLANATION:
-
If k=N, we output the array 1,2, \dots N.
-
If k = N-1, we output -1, since the N^{th} point will automatically be fixed once we fix N-1 points.
-
If k \lt N-1, we output the array as follows: 1, 2, 3, \dots k, k+2, k+3 \dots N, k+1.
EXPLANATION:
There are many ways to go about it. One such way is as follows:
-
If k=N, then simple we need to output the array 1, 2, 3, \dots N.
-
If k=N-1, that means there are N-1 fixed points, then automatically the remaining point will be fixed having N fixed points. Therefore, this case is impossible and we ouput -1.
Otherwise we are left with k< N-1, for which we can prove that answer is always possible by constructing the array as follows:
First let us fix the values p_i = i for 1 \leq i \leq k. Now we have our k fixed points and the remaining points (from k+1 to N) must not be fixed.
To achieve this, what we can do is to simply perform left cyclic shift of k+1, k+2, \dots N.
After performing this left cyclic shift we get k+2, k+3, \dots N, k+1 and store these in indices k+1, k+2, \dots , N respectively. Clearly, p_i = i+1 for k+1 \leq i \lt N and p_N = k+1 \lt N.
Therefore, we have our answer which is 1, 2, 3, \dots , k, k+2, k+3, \dots, N, k+1.
TIME COMPLEXITY:
O(N) for each testcase.
SOLUTION:
Editorialist's solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin>>tests;
while(tests--)
{
int n,k;
cin>>n>>k;
if(k==n-1)
{
cout<<-1<<endl;
continue;
}
for(int i=1;i<=k;i++)
cout<<i<<" ";
for(int i=k+1;i<n;i++)
cout<<i+1<<" ";
if(k!=n)
cout<<k+1<<endl;
else
cout<<endl;
}
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
void solve(int tc) {
int n; cin >> n;
int ans = 30;
for (int i = 0; i < n; i++) {
int x; cin >> x;
int cnt = 0;
while (x % 2 == 0) {
cnt++;
x /= 2;
}
ans = min(ans, cnt);
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k;
cin>>n>>k;
if(n - k == 1){
cout<<-1<<"\n";
}else{
for(int i = 0; i < n - k; i++){
cout<<(i + 1) % (n - k) + 1<<" ";
}
for(int i = n - k; i < n; i++){
cout<<i + 1<<" ";
}
cout<<"\n";
}
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 
