SUBPERM-Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Author: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Daanish Mahajan

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given two integers N and K. Find a permutation of length N such that it contains exactly K good subsegments where a subsegment of an array A[L \dots R]=[A_L, A_{L+1}, \dots, A_{R}] is called good if the subsegment is a permutation of length (R-L+1). Print -1 if no such permutation exists.

EXPLANATION:

Since there are many possible constructions, the editorial describes the one used by the setter.

Hint 1

Consider the array A [1, 2, \ldots, N] which has N good subsegments, and try modifying it to reduce it to K good subsegments.

Hint 2

Choose a suffix of A and reverse it to see the change on the count of good subsegments.

Solution

Consider the array A [1, 2, \ldots, N] which has N good subsegments, the prefixes of the array.
It’s easy to observe that if we reverse the suffix of length x, the number of good subsegments reduces by x - 1, since the elements from the range [N - x + 1, N - 1] won’t contribute with the prefix of length N - x to make a good subsegment as they would have done in case the array was an identity permutation.
So we reverse the suffix of length N - K + 1 so that our good subsegments reduce by N - K and hence total good subsegments left are N - (N - K) = K.

Corner Case

It can be observed that for N \ge 2, there are at least 2 good subsegments, the subsegment of length 1 having element as 1 and the entire array.
So for N \ge 2 and K = 1, no answer is possible, hence we print -1.

COMPLEXITY ANALYSIS

Since the only extra operation performed is to reverse the array which is linear, the complexity is \mathcal{O}(N).

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

int main() {
  ios_base :: sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    if (k == 1 && n > 1) {
      cout << "-1\n";
      continue;
    }
    for (int i = 1; i < k; i++) {
      cout << i << ' ';
    }
    for (int i = n; i >= k; i--) {
      cout << i << ' ';
    }
    cout << '\n';
  }
  return 0;
}
Tester's Solution 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        if (n == 1) {
            cout << 1 << '\n';
        } else if (k == 1) {
            cout << -1 << '\n';
        } else {
            vector<int> p(n);
            iota(p.begin(), p.end(), 1);
            reverse(p.begin() + k - 1, p.end());
            for (int i = 0; i < n; i++) {
                cout << p[i] << " \n"[i == n - 1];
            }
        }
    }
    return 0;
}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); 
	int t; cin >> t;
	int n, k;
	while(t--){
		cin >> n >> k;
		if(n > 1 && k == 1){
			cout << -1 << endl;
			continue;
		}
		vector<int> v(n);
		iota(v.begin(), v.end(), 1);
		reverse(v.end() - (n - k + 1), v.end());
		for(int x : v){
			cout << x << ' ';
		}
		cout << endl;
	}

	return 0;
}
2 Likes
2

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

int main() {
int t;
cin>>t;
while(t–)
{
int n, k;
cin>>n>>k;
if(n==1 && k==1)
cout<<1<<endl;
else if(n>1 && k==1)
cout<<-1<<endl;
else
{
for(int j=1;j<n;j++)
** {**
** if(j==k)**
** cout<<n<<" “<<j<<” “;**
** else**
** cout<<j<<” ";**
** }**
cout<<endl;
}
}
return 0;
}

Can someone verify this solution !? The test case is run successfully but am getting the first two tasks as WA for this piece of code. Thanks in advance.

3

No need to use a vector to store the answer and reverse the same.

We can simply print i, from i = k till i <=n.
And then print i, from i =1 till i < k.

Here’s my solution: Codechef | SUBPERM 57338170

4

I used the fact that if we swap a[k-1] and a[n-1] where a[n] is a permutation of length n then no. of good subsegments will be k :grinning:

#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;
if(n==1)cout<<1<<endl;
else{
if(k==1)cout<<-1<<endl;
else{
int x=k-1;
int a[n];
for(int i=0;i<n;i++)a[i]=i+1;
swap(a[n-1],a[x]);
for(auto x : a)cout<<x<<" ";
cout<<endl;

        }
    }
}
return 0;

}

5

I used that swapping arr[k-1] and arr[n-1] is the answer and there can be many other possibilities.
Code:
#include <bits/stdc++.h>

using namespace std;

void solve(){

int n, k, x, sum=0;

unordered_map<int, int> m;

cin>>n>>k;

vector<int> v(n);

if (n>1 && k==1){

    cout<<-1<<endl;

    return;

}

for (int i=0;i<n;++i)

    v[i]=i+1;

swap(v[k-1], v[n-1]);

for (int i=0;i<n;++i){

    cout<<v[i]<<" ";

}

cout<<endl;

}

int main(){

int t=1;

cin>>t;

while (t--){

    solve();

}

return 0;

}