I was trying to solve subsequences http://codeforces.net/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 | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
I was trying to solve subsequences http://codeforces.net/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.net/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.net/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