PREFPERM - Editorial


Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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






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.


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}].


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.


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


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

void solve()
    int n ,k;
    vector <int> a(k);
    for(int&i : a)
    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;
Tester's Solution
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
int n,k;
int a[100001],b[100001];;
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];
	for(int i=1; i<=k ;i++){
	for(int i=1; i<=n ;i++) cout << a[i] << ' ';
	cout << '\n';
int main(){
    int t;cin >> t;
    while(t--) solve();
Editorialist's Solution
#include <iostream>
using namespace std;

int main() {
	int t;
	    int k, n;
	    int a[n];
	    for(int i = 0; i<n; 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;
	return 0;

judge was high today…
first WA and AC :frowning:


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++)

   for(int i = 1;i<=v[1];i++)
   cout<<i<<" ";
   for(int i = 2;i<=k;i++)
           int x= v[i];
           cout<<x<<" ";

int32_t main()
    int t = 1;
    return 0;

Bro I thought only my day was bad today :frowning:

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

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

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.

what is wrong with the code anyone one please help ?

up till v[1], you’re printing in increasing order, so that would mean any prefix smaller than length v[1] will be a permutation which is not desirable. For example, if v[1]=3 v[2]=8 v[3]=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

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