javacoder1's blog

NEED HELP IN A PROBLEM
By javacoder1, history, 9 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

»
9 years ago, # |
  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
»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

bad

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

yeeeeee

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply