vkditya0997's blog

By vkditya0997, history, 8 years ago, In English

How to solve this question using BIT?

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

| Write comment?
»
8 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))

»
7 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it