_Untrackable_'s blog

subsequences of a string
By _Untrackable_, history, 18 months ago, In English

Is there any way to tell the no of subsequences of a given string with all unique elements.. I had used recursion but gets TLE. anyone have any optimal answer?

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

use pnc

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one step back again?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C had bad problem Statement:(

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I will tag you after every good contest:),why that post got deleted

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        the owner of that post deleted the post.

        if you want to have good contests, you need to solve more problems rated 1700+.

        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am getting comfortable with 1800,then also I should do 1700?

          → Reply
          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            no no. but i doubt if you are really comfortable with 1800 rated problems, else why is your rating hasn't increased yet.

            → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i am unable to reply back on codeforces currently

it says-"daily quota of 3 recepeints exceeded"

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Count the number of appearances of each character, let's store them in an array $$$c$$$, such that $$$c_1$$$ is the number of a's, $$$c_2$$$ is the number of b's, and so on. Now, for each character, we can either choose one of its appearances and add it into a subsequence, or not add the character at all. So we have $$$c_i+1$$$ possibilities for character $$$i$$$. Now we just multiply the number of possibilities for each character and we get the result.

→ Reply