sepiosky's blog

Extremal Permutations
By sepiosky, history, 9 years ago, In English

Hi ;) can you please help me with this problem , I think its an easy dp but i cant solve :

a permutation with numbers [1, n] is called extremal if for each i ( 1 < i < n ) one of this conditions be true :

1 : pi < pi - 1 and pi < pi + 1

2 : pi > pi - 1 and pi > pi + 1

count the number of extremal permutations with size n ( n  ≤  104 ) modulo m

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

It can be solved as DP.

Definition of DP[i][j] is 'number of extremal permutation with i numbers, j available choice'.

This can be solved as memory space O(n) cutting down memory using memory toggling.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Let dp [i][j][f] be the number of ways to place the last i numbers, such that there are j numbers left that are bigger than the last one you placed, with the constraint that the next number has to be bigger than the last if f is 1 or smaller if f is 0. Then dp [i][j][1] is equal to dp [i-1][0][0] + ... + dp [i-1][j-1][0] ans dp [i][j][0] is equal to dp [i-1][j][1] + ... + dp [i-1][i-1][1], and these sums cam be calculated quickly by making a partial sum array for dp [i-1] (technically two arrays — one for each value of f). Then the answer is dp [n][n][1]. Note that the memory can be reduced by only saving dp[i-1] rather than the entire array.

→ Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Obviously, relations between consequent elements may be only "<><><><..." or "><><><>...". Let's count the number of such permutations.

Let's define d[i][j] as number of such "zig-zag" permutations a[] of length i, and if j==0 then a[0] < a[1], if j==1 then a[0] > a[1]. Note that this relation between a[0] and a[1] definitely gives us an information about any relation (a[k], a[k+1]).

When we add new number (n+1), it's the biggest in the set. Therefroe, if it's placed to a[k] then it must be a[k] > a[k-1] and a[k] > a[k+1] (if such elements exist). The only thing remaining is to iterate over all possible positions of (n+1) in the permutations.

Suppose we place it this way: a[0] a[1] ... a[p-1] (n+1) a[p] ... a[n]. Then the number of ways we can choose such a[0] a[1]..a[n] which fits in our requirements is equal to d[p][a] * C(n, p) * dp[n-p][b], where a and b are appropriate types of permutations placed to the left and right of (n+1), respectively. We should add this result to dp[n+1][c], where c is a resulting type of permutation which is also easy to come up with.

O(n) space, O(n^2) time. Don't forget the modulo :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you check some first values (f[3]=4, f[4]=10, f[5]=32, f[6]=544) you can find that it's this, multiplied by two. So, you can take this formula:

2*a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*a(n-k),

which can be implemented in O(n^2).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    That's a very elegant formula (I think technically you're missing a division by two in it, but that's a minor detail). Here's a rough proof I wrote up of why that works.

    Observation 1: The actual numbers you are arranging do not matter as long as they are distinct — just how many there are. This is because for any strictly increasing sequence {a1, ..., an}, you can map ai to i for i = 1 to n without changing any of the relative orderings.

    Observation 2: For n > 1, call a decreasing-end extremal permutation an extremal permutation {p(1), ..., p(n)} such that p(n) < p(n-1), and an increasing-end extremal permutation an extremal permutation {p(1), ..., p(n)} such that p(n) > p(n-1). Then for any n, the number of increasing-end and decreasing-end permutations of size n are the same. Consider any increasing-end permutation {p(1), ..., p(n)} of the sequence {1, ..., n}. Then for all i from 1 to n, let p'(i) equal n + 1 — p(i). Therefore, if p(n) > p(n-1), p'(n) < p(n-1), and p' is still an extremal permutation of size n (since all relative orderings are flipped, all relative minima in p and relative maxima in p' and vice verse). So p' is a decreasing-end permutation, and for every increasing-end permutation there exists a unique decreasing-end permutation. So if there are a increasing-end permutations and b decreasing-end permutations, a <= b. Similar logic shows that every decreasing-end permutation can be mapped to a unique increasing-end permutation, so b <= a. For both of these to be true, a = b. Therefore, if f(n) is the number of extremal permutations of size n, there are f(n)/2 increasing-end extremal permutations and f(n)/2 decreasing-end extremal permutations. For n = 1, the permutation {1} will be considered both increasing-end and decreasing-end, and for n = 0 the permutation {} will be considered both increasing-end and decreasing-end.

    Now, we will try each possible placement of the number n+1 in our extremal permutation of size n+1. For each position k+1, there are k elements before n+1 and n — k elements after it. In order for the permutation to be extremal, the arrangement of the first k elements must be a decreasing-end extremal permutation of size k (there are f(k)/2 ways to do this — we will say that f(0) = 2 and f(1) = 2 for the purposes of calculation and add them as special cases later), and the arrangement of the last n — k elements must be an extremal permutation of size n — k such that p(1) < p(2) — this can be thought of as a decreasing-end permutation in reverse order, so the number of such permutations is f(n-k). Also, because of observation 1, we can arbitrarily choose which elements come before n + 1 in choose(n, k) ways. Therefore, f(n+1) = sum{k = 0 to n} f(k)/2 * f(n-k)/2 * choose(n, k), with base cases of f(0) = 2 and f(1) = 2. Then, add in special cases for 0 and 1 since we know that the actual answer is 1 for both of them.

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can you provide the link to this problem, if available?

→ Reply