Find the total number of increasing subsequence of length k

Question

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. Problem LINK

I want a better solution using BIT tree which could improve my solution. I Have tried using BIT tree but is giving me time limit exceeded error.

Here is BIT implementation Code.

I have also tried direct approach

for (i = 1; i<n;i++) 
  dp[i, 1] = 1

for (i = 1; i<n;i++) 
  for (j = 0; j<i-1;j++) 
    if array[i] > array[j]
     for (p = 2; p<k;p++) 
        dp[i, p] += dp[j, p - 1]

Please help me

@AerofoilKite i have tried using BIT but still i am getting TLE error — QWE, Dec 14 '14 at 06:56

Shahriar · Accepted Answer · 2014-12-14T07:26:20.693

Hope this will help..

int dp[51][100001];

void update(int bit[], int idx, int val){
for(int x = idx;x <= 100000;x += x & -x){
    bit[x] += val;
    if(bit[x] >= MOD) bit[x] -= MOD;
}
}

int query(int bit[], int idx){
int ret = 0;

    for(int x = idx;x > 0;x -= x & -x){
        ret += bit[x];
        if(ret >= MOD) ret -= MOD;
    }

return ret;
}

int main(){
    int N,K;

    scanf("%d %d",&N,&K);

int ans = 0;

    for(int i = 0,x;i < N;++i){
        scanf("%d",&x);

        for(int k = K;k > 1;--k)
            update(dp[k],x + 1,query(dp[k - 1],x));

        update(dp[1],x + 1,1);
    }

    printf("%d\n",query(dp[K],100000));

    return 0;
}

Explanation:

input: 1
For input 1:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   
0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 // update for X=2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

input: 1 2
For input 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 2 0 0 0 2 0 0 0 0 0 0 0  // update for X=3, length 1; got 2 increasing subsequence  with length 1
0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0  // update for X=3, length 2;  got 1 increasing subsequence  with length 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

input: 1 2 2
For input 2:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 2 3 0 0 0 3 0 0 0 0 0 0 0  // update for X=3, length 1; got 3 increasing subsequence  with length 1
0 0 0 2 2 0 0 0 2 0 0 0 0 0 0 0  // update for X=3, length 2; got 2 increasing subsequence  with length 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  // But you have no increasing subsequence with length 3

input 1 2 2 10
For input 10:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  
0 0 1 2 3 0 0 0 3 0 0 1 1 0 0 0  // update for X=11, length 1
0 0 0 2 2 0 0 0 2 0 0 3 3 0 0 0  // update for X=11, length 2
0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0  // update for X=11, length 3;  got 2 increasing subsequence  with length 3; tihs is calculate with help of length 2

Every time, you take a value.. calculate how many increasing subsequence you have found and update gradually for length 3,2,1

are you getting the correct answer !!!! please explain what have you done — QWE, Dec 14 '14 at 07:00
Suppose, you need increasing subsequences with length 3. Take each input update DP[3] for next value with what you have with length 2 with input.. — Shahriar, Dec 14 '14 at 07:06
please explain in brief about your algorithm , update you answer with a good explanation — QWE, Dec 14 '14 at 07:22
When i take 10 as input.. i check how many subsequence i already have with value less than 10.. then i will update for length 3 with result from length 2. because adding 10 with length 2 will produce length 3.. — Shahriar, Dec 14 '14 at 07:36

Find the total number of increasing subsequence of length k

1 Answers1