javacoder1's blog

NEED HELP IN A PROBLEM
By javacoder1, history, 10 years ago, In English

I was trying to solve subsequences http://mirror.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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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://mirror.codeforces.com/contest/597/submission/14321058 :)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

bad

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

yeeeeee

→ Reply