 # PREFPERM - Editorial

Setter: Hazem Tarek
Tester: Harris Leung
Editorialist: Kanhaiya Mohan

Simple

None

# PROBLEM:

You are given an array A of length K. Find any permutation P of length N such that only the prefixes of length A_i (1 \le i \le K) form a permutation.

Under the given constraints, it is guaranteed that there exists at least one permutation which satisfies the given condition.

If there are multiple solutions, you may print any.

Note: A permutation of length N is an array where every element from 1 to N occurs exactly once.

# EXPLANATION:

Observation 1

For two elements A_i and A_{i+1}, we need to ensure that prefixes of length A_i and A_{i+1} are permutations.

Note that prefixes of length j (A_i < j < A_{i+1}) must not be permutations.

Observation 2

In the required permutation P, the j^{th} element (A_i < j \leq A_{i+1}) should lie in the range [A_i+1, A_{i+1}]. Why?

We know that the prefix of length A_i is a permutation. This means till index A_i, all the elements in the range [1, A_i] have been used.

Also, the prefix of length A_{i+1} is a permutation. This means that till index A_{i+1}, all the elements in the range [1, A_{i+1}] should be used (exactly once). Since we have already used the elements [1, A_i], we are left with elements [A_i+1, A_{i+1}] for the indices [A_i+1, A_{i+1}].

Solution

To find a permutation under the given constraints, we need to satisfy two conditions:

• In the required permutation P, the j^{th} element (A_{i-1} < j \leq A_i) should lie in the range [A_{i-1}+1, A_{i}].
• No prefix of length j (A_{i-1} < j < A_i) should be a permutation.

To satisfy both these conditions, we can set the (A_{i-1}+1)^{th} element of the permutation P as A_{i}, (A_{i-1}+2)^{th} element as (A_{i}-1), (A_{i-1}+3)^{th} element as (A_{i}-2) and so on. The A_{i}^{th} element would be (A_{i-1}+1). This way, no prefix of length j would be a permutation, where (A_{i-1} < j <A_i).

In simpler words, the construction would be:

• Start with the identity permutation. This means P_i = i for all 1 \leq i \leq N.
• Reverse the first A_1 elements of P. This way prefix of length A_1 remains a permutation while prefixes of length <A_1 are not permutations.
• Similarly, for index i (1 < i \leq K), reverse the elements of P in the range [A_{i-1}+1, A_i]. This ensures that only the prefixes of length A_i are permutations.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

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

void solve()
{
int n ,k;
scanf("%d%d",&n,&k);
vector <int> a(k);
for(int&i : a)
scanf("%d",&i);
a.insert(a.begin() ,0);
vector <int> p(n);
iota(p.begin() ,p.end() ,1);
for(int i = 1; i <= k; i++)
reverse(p.begin()+a[i-1] ,p.begin()+a[i]);
for(int i = 0; i < n; i++)
printf("%d%c",p[i]," \n"[i+1 == n]);
}

int main()
{
int t;
scanf("%d",&t);
while(t--)
solve();
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n,k;
int a,b;;
void solve(){
cin >> n;
for(int i=1; i<=n ;i++) a[i]=i;
cin >> k;
for(int i=1; i<=k ;i++){
cin >> b[i];
}
sort(b+1,b+k+1);
for(int i=1; i<=k ;i++){
reverse(a+b[i-1]+1,a+b[i]+1);
}
for(int i=1; i<=n ;i++) cout << a[i] << ' ';
cout << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--) solve();
}

Editorialist's Solution
#include <iostream>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int k, n;
cin>>k>>n;
int a[n];
for(int i = 0; i<n; i++){
cin>>a[i];
}
int prev = 1;
for(int i = 0; i<n; i++){
int next = a[i];
for(int j = next; j>=prev; j--){
cout<<j<<' ';
}
prev = next+1;
}
cout<<endl;
}
return 0;
}


judge was high today…
first WA and AC 6 Likes

What was wrong here

#include <bits/stdc++.h>
using namespace std;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

void solve()
{
int n,k; cin>>n>>k;
vector<int> v(n+1);

for(int i = 1;i<=k;i++)
cin>>v[i];

for(int i = 1;i<=v;i++)
cout<<i<<" ";

for(int i = 2;i<=k;i++)
{
int x= v[i];
while(x!=v[i-1]){
cout<<x<<" ";
x--;
}

}

}

int32_t main()
{
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}


Bro I thought only my day was bad today 1 Like

Question says: Find any permutation P of length N such that only the prefixes of length Ai(1≤i≤K) form a permutation.

It means that there should exist no prefix and non-prefix permutation other than the prefix length given.
so for test case 2 :
7 6 5 4 3 2 1 it is not a valid answer cause it is forming all the non-prefix permutations of 1<=length<N
Question should specifically mention that not only prefix but it may contain non-prefix permutations

Same here , I got highly demotivated by WA coz in Cookoff we get penalty for wrong submission , then after the contest ended, it magically became AC.
I had quit the contest after Q2 coz Q1 had got WA !
This is highly disappointing !!

Same bro:(

It taught me something —> never give up
Even after WA on A I solved 2 and 3 que
After I resolved first one but yeah a lot of time was wasted on 1st questions I didn’t understood what you wrote in editorial but I understood your code. good logic bro

1 Like

Actually, we can also interpret it as our confidence level testing I respect problem setters and coordinators, as I love competitive programming. But getting WA 6 times on 1st problem itself got me badly demotivated, and after the contest its all green. It basically ruined my contest.

https://www.codechef.com/viewsolution/58871029

up till v, you’re printing in increasing order, so that would mean any prefix smaller than length v will be a permutation which is not desirable. For example, if v=3 v=8 v=12, then your code’s output will be-
1 2 3 8 7 6 5 4 12 11 10 9
In this sequence, prefixes of length 1, 2 and 3 are permutations but we want only the prefix of length 3 to be a permutation. You should have printed the first prefix in reverse as well.

What does prefix and non-prefix permutation mean?? I am stuck

MY SOLUTION(EASY)
void solve() {
ll n, k;
cin >> n >> k;
ll ele;
map<ll, ll> mp;
for (ll i = 1; i <= k; i++) {
cin >> ele;
mp[ele]++;
}
set s;
s.insert(1);
ll sz = 1;
while (sz <= n) {
if (mp.find(sz) != mp.end()) {
cout << *(s.begin()) << " ";
s.clear();
s.insert(sz + 1);
}
else {
cout << sz + 1 << " ";
}
sz++;
}
cout << nl;

}