 # SUBPERM-Editorial

Tester: Takuki Kurokawa
Editorialist: Daanish Mahajan

Simple

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

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

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

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 #include <bits/stdc++.h>
using namespace std;

int main() {
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;


}

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;


}