FIXFIX - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

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

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

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

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

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

Please post the link to your submission - no one wants to squint at a screenshot :slight_smile:

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)

Can anyone please help me to find why this code is failing?

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