2
$\begingroup$

With given permutation of $1,\ldots,n$ for example (in one-line notation): 3 5 1 2 4 6.

How to find amount of ascending subsequences of length 3 in the second row of the permutation ?

There's $n!/k!(n-k)!$ of subsequences of length $k$ for the identity permutation 1 2 3 4 5 6$\cdots$n.

How to deal with this problem ?

Thanks.

  • 0
    Sounds good, could you post it or something ?:)2011-05-09

1 Answers 1

3

It can be done in O(n log n) time. Assume for every index that it's your mid element in subsequence.

Now having x smaller elements than your mid elements and y greater elements than your mid element you can make max(x,y) subsequences with selected mid point.

It can be also easily programmed.

Simply use segment tree or BIT.

for mid element m you want to check value of x:

-they are in range $<0;m-1>$

Value of y is:

$<0;n-1> - <0;m-1>$ where n is number of elements.

  • 0
    Yes, you are right, but with segment tree or binary indexed tree we can easily have answer in $O(log n)$ time for each range. So overall complexity is $O(n log n)$.2011-10-26