vkditya0997's blog

SPOJ INCSEQ — Increasing Subsequences
By vkditya0997, history, 5 years ago, In English

How to solve this question using BIT?

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (9)
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vkditya0997 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It can be solved using dynamic programming. First use coordinate compression to get the values from 1...N Let dp[i][j] be number of subsequences of length j ending with i. Then, dp[i][j]=dp[i-1][j-1]+dp[i-2][j-1]+.....+dp[1][j-1];

This will take O(N*N*K) time.

Since a dp[i][j] is a cumulative sum of 0....i-1 we can use BIT for this purpose. We will have to make to make K BITs so that a particular state can be answered in O(logn) time. Complexity(O(N*K*logN))

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

There is a copy of this problem: 597C - Subsequences, my solution using BIT: 15007060, Deemo's one: 14269844.

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

    shift(x,i+1,get(x,i)); shift(x,0,1); I didn't get that!This is my problem ,everywhere i found that.But,couldn't understand.Please,help me,brother!

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have tried your suggested problem.I got wrong answer on test case 11.I found my bug.But,this couldn't make any sense for me.24613181 is my,wrong answer code

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for more explanation https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/

→ Reply