Next Permutation

There is Bangla editorial too.

For subtask 1:

For subtask 1 we will generate all possible permuations of length 1 to 9. The easiest way to do this is to use $next\_permutation()$ function of C++. This function can be used to generate lexicographically next permutation.

For all all subtasks:

First let's see when the solution does not exist. Let the permutation be $p[0 \dots n-1]$ and it has $d$ number of descents in it. If $d = n-1$, then this is the maximum permutation, so the next permutation doesn't exist. If $d=0$, then this is the minimum permutationa and all the other pemutations have at least one descent, so the next permutation doesn't exist in this case too. In other cases the next permutation won't exist if this is the maximum permutation among those with $d$ descents. The maximum permuation with $d$ descent is: ${N, N-1,\dots, N-d+1, 1, 2, \dots, N-d}$. This is the permutation in which the largest $d$ elements are in descending order at first and then the rest of the elements are in ascending order. In all other cases the solution exists.

Suppose we have a boolean function $f(n, x, d)$ which tells whether we can achieve $d$ descents by placing $n$ elements where the order of the element before is $x$ (i.e., if the first element is between 1 and $x-1$ the there will be a descent to the left of the first element, otherwise not). We will use this function to find the next permutation.

Suffix phase: Consider a suffix of the given permuation, we want to change only on this part. Since we want to find the smallest possible permutation, we have to keep the length of this suffix as small as possible. Let's run a loop from $i = n-2$ to$i=0$, for some $i$ we want to reorder the elements from $p[i]$ to $p[n-1]$ to achieve our goal. Let's say the solution to our problem is $q[0\dots n-1]$. Here, $p[i] < q[i]$ and from index $i$ to $n-1$, $q$ has the same elements as $p$, just in different order. Now, let's consider the elements of this suffix of $p$ one by one in ascending order. If we are consider $z$ now, then $q[i]=z$ and $z > p[i]$. Now we want to use function $f$ to check the existence of a solution, but to do that we will need to find the amount of descent we need generate in this suffix. Let, the amount of descent from $p[i]$ to $p[n-1]$ is $d$. Then we can say that the amount of descent from $q[i]$ to $q[n-1]$ must be $d$ too. But there is a case; if $p[i-1] > p[i]$ and $p[i-1] < z$, then a descent on the left is going to be reduced. This descent must be inside from $q[i]$ to $q[n-1]$ So, if $p[i-1] > p[i]$ and $p[i-1] < z$, we can increase the value of $d$ by 1. Now, if $f(n-i-1, x, d)$ is true we can say that, there is a solution using $q[i] = z$ and we can go on to next building phase to find the exact solution. But what should $x$ be? The number of elements in $p[i]$ to $p[n-1]$ which are less than $z$ + 1.

Building phase: Now we know, $q[i] = z$. Next from $j = i+1$ to $j = n-1$ we will place the elements one by one. For some $j$ we will place the smallest possible element here. By fixing an element, we can check the existence a solution using $f$ again.

If we ignore $f$ for the time being, each of the phase has complexity $O(n^2)$ per test case. These phases are same for subtask 2, 3 and 4. Now, let's see how to find the value of $f(n, x, d)$.

You may skip reading the details of subtask 2 and 3, if you just want to get an idea of the full solution

For subtask 2:

$f(n, x, d)$ function has this recurrence relation: for each $i$ $(1 \leq i \leq n)$ , OR of all $f(n-1,i, d-less(i, x))$, i.e. if at least one of them is true only then $f(n, x, d)$ is true. Here, if $i < x$, $less(i, x) = 1$ otherwise $less(i, x) = 0$.

We can do this with DP in $O(n^4)$ complexity. Notice that, the DP is same for all testcases, so the overall complexity is $O(T\cdot n^2 + n^4)$.

For subtask 3:

The DP mentioned above has 3 states, let's see if we can optimize it. Notice that, when $i < x$, we always call $f(n-1, i, d-1)$, otherwise we call $f(n-1, i, d)$. Now, suppose $g(n, x, d)$ is OR of all $f(n-1, i, d-1)$ where $1 \leq i \lt x$. And $h(n, x, d)$ is OR of all $f(n-1, i, d)$ where $x \leq i \leq n$. Here, $g$ is a prefix OR function and $h$ is a suffix OR function. Both of them can be done in $O(n^3)$ complexity. Then, $f(n,x,d) = g(n,x,d)|h(n,x,d)$। So, the complexity of $f$ becomes $O(n^3)$ too. The overall complexity becomes $O(T\cdot n^2 + n^3)$.

For subtask 4:

Now we will see how to find the value of $f(n, x, d)$ in $O(1)$ :p We have to do some case analysis. There can be $n-1$ descents among $n$ elements. But there can be $n$ descents too, depending on the value of $x$.

• First, if $d > n$ or $d < 0$, then the answer if false.
• If $d = 0$, then all of the elements will be an ascending order and the smallest element must be greater than $x$. So, if $d = 0$, then the answer is $x==1$.
• If $d=n$, then all of the elements will be an descending order and the largest element must be smaller than $x$. If $d=n$, then the answer is $x==n+1$.

In all other cases there is a solution! How? Let's place the elements in ascending order. Now if $x > 1$, then there will be a descent to the left of the first element and we have to decrease $d$ by 1. Then we will reverse the sub-array containing the last $d+1$ elements, which will create $d$ descents.

Notice that, here we have an algorithm for the building phase which works in $O(n\log{}n)$ (or $O(n)$ if you want). We have to use this in the next subtask.

For subtask 5:

Now our $f(n, x, d)$ function works in constant time. Our building phase works in linear time. The bottleneck is the suffix phase, which still works in $O(n^2)$ time. Here after fixing a suffix that starts from index $i$, we are considering all elements greater than $p[i]$ to see if there is a solution by placing this at $q[i]$. Now, here is the trick. We don't actually have to consider all elements. Instead it's sufficient to use the border cases to check the existence of a solution :p

• The smallest element which is greater than $p[i]$
• The largest element which is greater than $p[i]$
• If $i > 0$, then the smallest element which is greater than $p[i-1]$ (of couse this must be greater than $p[i]$ too)

Since we can check the existence of a solution in constant time, our whole solution becomes $O(n\log{}n)$. Here, to input the value of $x$ in $f(n,x,d)$, we will need a data structure which tells us the order of an element. This can be a Fenwick Tree or any other data structure you prefer.