How to solve this question using BIT?
# | User | Rating |
---|---|---|
1 | tourist | 3748 |
2 | Benq | 3540 |
3 | Petr | 3470 |
4 | Radewoosh | 3355 |
5 | ecnerwala | 3347 |
6 | maroonrk | 3345 |
7 | jiangly | 3324 |
8 | scott_wu | 3313 |
9 | ainta | 3298 |
10 | boboniu | 3289 |
# | User | Contrib. |
---|---|---|
1 | 1-gon | 200 |
2 | Errichto | 197 |
3 | rng_58 | 194 |
4 | SecondThread | 186 |
5 | awoo | 185 |
6 | Um_nik | 182 |
7 | vovuh | 179 |
8 | Ashishgup | 175 |
9 | antontrygubO_o | 174 |
10 | -is-this-fft- | 173 |
How to solve this question using BIT?
Name |
---|
Auto comment: topic has been updated by vkditya0997 (previous revision, new revision, compare).
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))
Could you please explain more?
There is a copy of this problem: 597C - Subsequences, my solution using BIT: 15007060, Deemo's one: 14269844.
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!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
for more explanation https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/
Thank you so much bro
its ok brooo !!