# GOODPERM -Editorial

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

Simple

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

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

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

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 last = 0; last < 8; ++last) {
for (int cnt = 0; cnt < 8; ++cnt) {
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 last = 0; last < 8; ++last) {
for (int cnt = 0; cnt < 8; ++cnt) {
if (p[i] == 0) {
for (int nlast = 0; nlast < 8; ++nlast) {
if (~mask & (1 << nlast)) {
}
}
} 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

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-

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-

1 Like

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

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

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

Video solution: https://youtu.be/mEUVVsifKbQ

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.

Hereâ€™s my revised submission.

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

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

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

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