I was trying to solve subsequences http://codeforces.com/problemset/problem/597/C of Testing Round #12 but could not figure out the solution.Can anyone explain the solution using binary indexed tree.
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
I was trying to solve subsequences http://codeforces.com/problemset/problem/597/C of Testing Round #12 but could not figure out the solution.Can anyone explain the solution using binary indexed tree.
Name |
---|
We will loop from 1 to N and at each step dp[i][j] will be the number of increasing subsequences of length i ending at element with value j. Let's say that the current element is a[i]. Obviously, this is a new subsequence of length 1 ending at a[i]. So we will do ++dp[1][a[i]]. Then for j from 2 to K we will do dp[j][a[i]]+=(dp[j-1][1]+dp[j-1][2]+dp[j][3]+...+dp[j-1][a[i]-1]) since we can extend every subsequence of length j-1 which ends in an element which is less that the current one :)
Here is my submission — http://codeforces.com/contest/597/submission/14321058 :)
Apologies in advance if revisiting old post is a taboo on code forces.
But I can't help wonder why did my solution resulted in a TLE
http://codeforces.com/contest/597/submission/18835377
Shouldn't this have the same time complexity with the one just mentioned?
You missed the tree.
Thanks a lot, just googled BIT online. My mind is completely blown now, now I see why some of the code contains weird x&(-x) equations.
bad
yeeeeee
One dumbass little child at our ioi team trainings posted these when my computer was free to get my contribution down. Temotoloraia so just please don't minus.
I made mistake, I'm sorry