### vkditya0997's blog

By vkditya0997, history, 4 years ago, ,

How to solve this question using BIT?

• -3

 » 4 years ago, # |   0 Auto comment: topic has been updated by vkditya0997 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   0 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))
•  » » 3 years ago, # ^ |   0 Could you please explain more?
 » 3 years ago, # |   0 There is a copy of this problem: 597C - Subsequences, my solution using BIT: 15007060, Narenji58's one: 14269844.
•  » » 3 years ago, # ^ |   0 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!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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
 » 11 months ago, # |   0 for more explanation https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/
•  » » 11 months ago, # ^ |   0 Thank you so much bro
•  » » » 11 months ago, # ^ |   0 its ok brooo !!