GOODPERM -Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

Simple

PRE-REQUISITES:

STL, Generate all Permutations of an Array

PROBLEM:

Given a partially filled permutation p, we have to find number of possible good permutations from it. A permutation is good if-

  • It has all numbers from [1,n]
  • Number of positions such that p_i>p_{i-1} is exactly equal to K

QUICK EXPLANATION:

Key to Success- Anyone with good knowledge of STL and implementation skills can do this question very, very easily!

We generate all permutations of [1,n] and check if-

  • it satisfies the condition of number of p_i>p_{i-1} equal to K.
  • it can be achieved from sequence A

We can easily use C++ STL’s next_permutation() to generate the permutations easily.

EXPLANATION:

This editorial will have a single section. There is little concept to be discussed, hence we will discuss the cleanest way of implementing it quickly. We will refer to Setter’s solution for it :slight_smile:

Setter’s Solution-

"I took the input Mr. Editorialist. WTF THIS QUESTION SO DIPHICULT I CANT SOLVE WTFWTF?!"

Hold your breath young man/woman/boy/girl/whatever. We shall deal with the question one step at a time, i.e. @step_by_step .

The first thing will be, to make a new array for permutations. Remember, that repetitions are not allowed in permutations, and all numbers in range [1,n] must occur exactly once!!

Since we plan to use next_permutation() function from STL, lets generate the lexicographically smallest permutation first. In other words, initialize new permutation array p[] as- p[]=\{1,2,3,...,n\}. Code for it-

for (int i=1;i<=n;i++){
        p[i]=i;
    }

Our next_permutation() will generate ALL permutations for us. We only have to check 2 things-

  • If that permutation is achievable from a
  • It satisfies the condition of number of p_i>p_{i-1} equal to K.

When will a permutation be achievable from a? Recall that, we can only fill in 0's, and not shuffle permutation a. Hence, we can say that a permutation is valid IF AND ONLY IF-

  • A_i==0 and P_i doesnt occur elsewhere in A_i.
  • A_i \neq 0 and P_i==A_i.

In other words, if A_i is 0 and the element P_i can be inserted in A, or if A_i \neq 0, then P_i must be equal to A_i, because shuffling/moving-elements is not allowed.

A sample code for that is-

`for (int i=1;i<=n;i++){
            if (a[i]>0 && a[i]!=p[i]){
                //Invalid Permutation
            }
        }`

Note that we didnt check for "A_i==0 and P_i doesnt occur elsewhere in A_i." It is redundant. Why? (Q1)

Now what is left is, simply, to check the count of P_i>P_{i-1} being equal to K. Simple looping for that is needed. A sample code-

for (int i=2;i<=n;i++){ if (p[i]>p[i-1]){ cnt++; } }

A full overview of working loop is given in tab below-

Click to view
do{
        int cnt=0;
        for (int i=1;i<=n;i++){
            if (a[i]&&a[i]!=p[i]){
                cnt-=100;
            }
        }
        for (int i=2;i<=n;i++){
            if (p[i]>p[i-1]){
                cnt++;
            }
        }
        ans+=(cnt==k);
    }
    while (next_permutation(p+1,p+n+1));

Thats it! We’re done with this question now as well :slight_smile:

SOLUTION:

The setter and tester’s code are pasted in tabs below because @admin can take some time in linking the solutions. Please refer to them :slight_smile:

Setter

Click to view
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
 
using namespace std;
#define int long long
 
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
 
const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
 
///---program start---///
 
int a[arr];
int p[arr];
 
void solve()
{
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    for (int i=1;i<=n;i++){
        p[i]=i;
    }
 
    int ans=0;
    do{
        int cnt=0;
        for (int i=1;i<=n;i++){
            if (a[i]&&a[i]!=p[i]){
                cnt-=100;
            }
        }
        for (int i=2;i<=n;i++){
            if (p[i]>p[i-1]){
                cnt++;
            }
        }
        ans+=(cnt==k);
    }
    while (next_permutation(p+1,p+n+1));
 
    cout<<ans<<"\n";
}
 
main()
{
    #ifdef I_love_Maria_Ivanova
        files("barik");
        freopen("debug.txt","w",stderr);
    #endif
 
    int test;
    cin>>test;
    while (test--){
        solve();
    }
}

Tester

Click to view

Its VERY scary for newbies. Dont open it!!

Click to view

You wont agree huh? A glimpse is given in next tab. Heed my warning!

Click to view

The only persistence I like is in persistent segment trees. Open next tab at your own risk!!

Click to view
for (int i = 2; i <= n; ++i) {
		memset(ndp, 0, sizeof(ndp));
		for (int mask = 0; mask < 1 << 8; ++mask) {
			for (int last = 0; last < 8; ++last) {
				for (int cnt = 0; cnt < 8; ++cnt) {
					if (dp[mask][last][cnt] > 0) {
						if (p[i] == 0) {
Click to view

Want the full solution still? Fineeee

Click to view
#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = (int)4e5 + 10;
const int MOD = (int)1e9 + 7;
const int INF = 1e9;
 
int p[10];
int dp[1 << 8][8][8];
int ndp[1 << 8][8][8];
 
void solve() {
	int n, k;
	scanf("%d%d", &n, &k);
	set < int > s;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &p[i]);
		if (p[i] > 0) {
			assert (!s.count(p[i]));
			s.insert(p[i]);
		}
	}
	memset(dp, 0, sizeof(dp));
	if (p[1] == 0) {
		for (int i = 1; i <= n; ++i) {
			dp[1 << (i - 1)][i - 1][0] = 1;
		}
	} else {
		dp[1 << (p[1] - 1)][p[1] - 1][0] = 1;
	}
	for (int i = 2; i <= n; ++i) {
		memset(ndp, 0, sizeof(ndp));
		for (int mask = 0; mask < 1 << 8; ++mask) {
			for (int last = 0; last < 8; ++last) {
				for (int cnt = 0; cnt < 8; ++cnt) {
					if (dp[mask][last][cnt] > 0) {
						if (p[i] == 0) {
							for (int nlast = 0; nlast < 8; ++nlast) {
								if (~mask & (1 << nlast)) {
									ndp[mask | (1 << nlast)][nlast][cnt + (nlast > last)] += dp[mask][last][cnt];
								}
							}
						} else {
							if (~mask & (1 << (p[i] - 1))) {
								ndp[mask | (1 << (p[i] - 1))][p[i] - 1][cnt + (p[i] - 1 > last)] += dp[mask][last][cnt];
							}
						}
					}
				}
			}
		}
		memcpy(dp, ndp, sizeof(ndp));
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans += dp[(1 << n) - 1][i][k];
	}
	printf("%d\n", ans);
}
 
int main() {
//	freopen("input.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t --> 0) {
		solve();
	}
	return 0;
}

Editorialist Solution will be put on demand

Time Complexity=O(N!*N) (Setter)
Time Complexity=O(???) (Tester)

CHEF VIJJU’S CORNER :smiley:

1. Note that we didnt check for "A_i==0 and P_i doesnt occur elsewhere in A_i." It is redundant. Why?

Click to view

Simply because, if the element corresponding to that A_i is at some other position, and all elements occur only once, then a mismatch at the position where A_i\neq 0 is confirmed.

2. Tester’s Solution- He solved it using dp+bitmask, which should deserve a mention here :).

Click to view

Permutation: solution with bitmasks. Make a dp table as-

dp[i][mask][last][cnt]

How many permutations with filled first i positions. Subset of elements on those positions = mask.

q[i] = last

and there was cnt p[i] > p[i-1]

Transitions processing in O(N) if p[i+1] = 0 and in O(1) if p[i+1] != 0

3. Refer to Tester’s code and his notes. Derive the time complexity of his solution in worst case.

Click to view

O({2}^{N}*{N}^{3}*K)

4. Test Case Bank-

Click to view

Official Input- https://pastebin.com/SvrCRxSh
Official Output- https://pastebin.com/QEXfi5J8

5. Related Problems-

My AC solution is quite different from the ones mentioned here I think.

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

I had a recursive solution for this but its not optimized. Can anyone check it and optimizw it. The problem is that I am generating more permutations than needed. Soln: 18934523

B. Petr and Permutations is really very very nice problem xD.

I have also implemented the same logic in the contest, but i don’t know about the next_permutation(), so i have got a implementation and used it in my code, i am pretty sure that it works, but the problem is i don’t know for which test-cases my code is failing. Can someone please help!
My code is: https://www.codechef.com/viewsolution/18934504

Hello everyone, please help me. I am at my wit’s end trying to figure out which test case is failing. I tried both the next_permutation as well as the Heap’s algorithm to generate the permutation and have used the check function as per the editorial. The function is checkArray. If anyone can point out the issue, I’ll be very grateful. I have tried every possible test case I can think of.

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

Use next permutation in a do- while loop and try.

@vijju123, thanks for the response. Yes I understood, that the first permutation was being excluded. But after correcting that I found something strange. The author’s code is giving a different output than expected.

For TC -
2 1
1 2

The output should be 0, author’s code is giving 1.

For TC -
2 1
2 1

I feel the output should be 1, author’s code is giving 0.

Please help me understand if I am misinterpreting the question somewhere.

Here’s my revised submission.

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

Didn’t know about that STL function. So I wrote Full Heap Algorithm! Well, nice to know a function like that exists in C++ STL.
Thanks @vijju123

1 Like

My Approach -

P.S. (xD) - Yesterday I was reading CP 3 by Steven & Felix Ch 3 And Question was 8 Queens Chess Problem and was going through the techniques of generating all 8! permutations in 1 sec.

Spoiler Alert - Bitwise Operations Are much much faster.

My approach - (Similar to Tester but didn’t used DP). My Sol 18925778 .

I used recursion to generate. And *** (val & ( 1 < < j))==0 *** To check if no j is present in Current Array.
val is Bitwise OR of 2^no of all characters present in array except zeros. And during generating all permutations only I have checked all conditions. And returned count of answers. I also stopped generating all next permutations if filling further places result in no soln.

P.P.S. - I yesterday learnt that next_permutation fn exist in STL but I didn’t strike me during contest xD.

1 Like

@vijju123 Do you really want to mention step_by_step here ??

why appling next_permutation on whole set of no just do it for no which are missing .
check my sol here https://www.codechef.com/viewsolution/18937654

5 Likes

2 1 1 2 is an Invalid input. Because 1<=2<=n does not hold.
2 1 2 1 output 0 is correct. There does not exist any i in range 1<i<=n.

1 Like

@vijju123 please correct problem links in rest of editrials. Like I have corrected this editorial.

Yes, I will. Thing is, none of the links are there working when I write them (as problems arent moved to contest page) so I have to “guess” them xD.

Lot to do today. Add TC in test case bank, fix tags. fix links xD

1 Like

Well xD. Because completely mechanic brute force has less chances of wrong logic.

Your logic cant be wrong if its just doing what the question says *insert meme here*

Great! But yes, make sure you know STL as quicker submissions are heavily rewarded at codechef.

1 Like

I am glad it helped you :slight_smile:

I think you misinterpretted the question @ruddradev. Try checking the comments at question page for clarifications.

To everybody having trouble debugging, the test cases are added in test case bank. Please have a look and try to debug now! :slight_smile: