PROBLEM LINK:
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 
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
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();
}
}
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 
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-
- B. Petr and Permutations- Not very related, but very, veryyyy fun xD
- B. Open Communication