PREFPERM - Editorial

PROBLEM LINK:

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

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

DIFFICULTY:

Simple

PREREQUISITES:

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[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];
	}
	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 :frowning:

5 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[1];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 :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.

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

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

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;

}