# FIXFIX - Editorial

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

SIMPLE

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.

1 Like

My approach :
Invert n-k elements from beginning or end. If the middle element matches(a[i] = i), then perform swap operation accordingly.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
const unsigned int M = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T_set; // PBDS_set
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> T_multiset; // PBDS_multiset

void solve()
{
int t, n,k;
cin>>t;
while(t--){
cin>>n>>k;
k = n-k;
vector<int> x(n);
for(int i = 0; i < n ; i++ )
x[i] = i + 1;
if(k == 1 or k > n){
cout<<"-1\n";
}else{
reverse(x.begin(),x.begin()+ k);
for(int i = 0; i < k ; i++ ){
if(x[i] == i + 1){
swap(x[i],x[i+1]);
}
}
for(int i = 0; i < n ; i++ )
cout<<x[i]<<" ";
cout<<"\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}



code run perfectly and pass all posiible testcases
but why this code gives Runtime Error(OTHER)

#include
using namespace std;

int main() {

int t;
cin>>t;
while(t--)
{

int n,k;
int a[n];
cin>>n>>k;

if(n-k==1)
{
cout<<"-1";
}

else
{
for(int i=0;i<n;i++)
{
a[i]=i+1;
}

for(int j=k;j<n-1;j++)
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}

for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
}

cout<<endl;

}


}

Index out of bounds in sample Test Input:

[simon@simon-laptop][19:44:28]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling vikas3103-FIXFIX.cpp
+ g++ -std=c++17 vikas3103-FIXFIX.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
+ set +x
Successful
[simon@simon-laptop][19:44:32]
[~/devel/hackerrank/otherpeoples]>echo "3
2 1
3 1
4 2
" | ./a.out
-1
vikas3103-FIXFIX.cpp:24:16: runtime error: index 2 out of bounds for type 'int [*]'
vikas3103-FIXFIX.cpp:32:23: runtime error: index 2 out of bounds for type 'int [*]'
vikas3103-FIXFIX.cpp:33:18: runtime error: index 2 out of bounds for type 'int [*]'
vikas3103-FIXFIX.cpp:38:22: runtime error: index 2 out of bounds for type 'int [*]'
1 3 2
1 2 4 3


Edit:

 int a[n];
cin>>n>>k;


You declare an array of size n before you’ve even read n.

Why does the following code incorrect???

#include<bits/stdc++.h>

using namespace std;

void solve() {
int n, k;
cin >> n >> k;
if(k == n-1) {
cout << -1 << "\n";
return;
}
for(int i = 1; i <= k; i++) {
cout << i << " ";
}
for(int i = k+1; i < n; i++) {
cout << i+1 << " ";
}
cout << k+1 << "\n";
}

// Driver code
int main() {

int t; cin >> t;
while(t--) {
solve();
}

return 0;
}


Consider the test input:

1
2 2


@ajit123q - at the time of writing, the “Editorialist’s Solution” appears to be for the wrong problem

1 Like

Thanks. Fixed!

1 Like

Can someone tell me about the test case where it is failing?

       int n,k;cin>>n>>k;
if(k==(n-1)){
cout<<-1<<" ";
}else{
if(k==0){
int j=n;
while(j>=1){
cout<<j<<" ";
j--;
}
}else{
int i=1;
while(i<=k){
cout<<i<<" ";
i++;
}
int x=i;
int temp=x;
x++;
while(x<=n){
cout<<x<<" ";
x++;
}
if(temp<n){
cout<<temp<<" ";
}
//         cout<<temp;
}
}
cout<<endl;


Try this,
N=5 K=0

5 4 3 2 1
(3 is in its correct place)

Can someone help me why my solution in java is not accepting?

Edit:

If it’s this one - try running it with the following test input:

10
100000 0
100000 1
100000 2
100000 3
100000 4
100000 5
100000 6
100000 7
100000 8
100000 9


and see how long it takes.

(in Java, concatenating strings S and T is \mathcal{O}(|S|+|T|))

2 Likes

when k == n you’ll print values till n that’s fine but at last you’ll again print k+1 that’s the reason of WA.

It will fail when N is odd and K is 0, as the middle element will be equal to its 1-based index.

Instead of reversing the list, try shifting it.

First of all, instead of uploading a screenshot of your code, try providing its editor link or envelope it in preformatted text tags (//code//).

In your code, you didn’t consider the case when K=0

Sure, In the future I will not upload any screenshots of the code.
But I didn’t agree with your answer because the case k=0 is already included in the else part

Thank you for the explanation.

1 Like

Runs Perfectly.

Exceptions Where Permutations Not Possible -
Number of Ai!= i is 1.

1. List A from 1 to K(inclusive).
2. List B from K+2 to N(inclusive)
3. List C = A + B
4. append (K+1) to C if (N not = K)
def outp(N):
ans = ""
for x in N:
ans += str(x) + " "
print(ans)

for tc in range(int(input())):
N, K = map(int, input().split(" "))
if N - K != 1:
list1 = [x for x in range(1, N+1) if x != K+1]
if N != K:
list1.append(K+1)
outp(list1)
else:
print(-1)


#include<bits/stdc++.h>
#define ll long long
#define mod7 1000000007
using namespace std;

void myfunc() {
int n,k;
cin >> n >> k;
vector<int> v(n);

if(n-k==1) {
cout << -1 << endl;
return;
}

int i=0;
for(;i<n && i<k;i++) {
v[i]=i+1;
}

int tmp=i++;
for(int j=n-1;j>=tmp;j--)
v[j]=i++;

for(int x:v)
cout << x << ' ' ;
cout << endl;

}

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