How to find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)

Asked by on 2013-02-24T17:51:41-05:00
Actually it is a http://www.spoj.com/problems/INCSEQ/ problem.

Suppose I have an array 1,2,2,10.

The increasing sub-sequences of length 3 are 1,2,4 and 1,3,4(index based).

So, the answer is 2.

Best Answer

Answered by on 2013-02-24T19:33:22-05:00
Let:

dp[i, j] = number of increasing subsequences of length j that end at i
An easy solution is in O(n^2 * k):

for i = 1 to n do
 dp[i, 1] = 1

for i = 1 to n do
 for j = 1 to i - 1 do
 if array[i] > array[j]
 for p = 2 to k do
 dp[i, p] += dp[j, p - 1]
The answer is dp[1, k] + dp[2, k] + ... + dp[n, k].

Now, this works, but it is inefficient for your given constraints, since n can go up to 10000. k is small enough, so we should try to find a way to get rid of an n.

Let's try another approach. We also have S - the upper bound on the values in our array. Let's try to find an algorithm in relation to this.

dp[i, j] = same as before
num[i] = how many subsequences that end with i (element, not index this time) 
 have a certain length

for i = 1 to n do
 dp[i, 1] = 1

for p = 2 to k do // for each length this time
 num = {0}

 for i = 2 to n do
 // note: dp[1, p > 1] = 0 

 // how many that end with the previous element
 // have length p - 1
 num[ array[i - 1] ] += dp[i - 1, p - 1] 

 // append the current element to all those smaller than it
 // that end an increasing subsequence of length p - 1,
 // creating an increasing subsequence of length p
 for j = 1 to array[i] - 1 do 
 dp[i, p] += num[j]
This has complexity O(n * k * S), but we can reduce it to O(n * k * log S) quite easily. All we need is a data structure that lets us efficiently sum and update elements in a range: http://en.wikipedia.org/wiki/Segment_tree, http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees etc.

Your Answer
No advertising and No spamming please.
Name:
Answer: