lashavi's blog

Help in counting distinct sub sequences.
By lashavi, history, 7 years ago, In English

Hello all,I was doing a hiring challenge on hackerearth and got really stuck in this problem and couldn't solve it yet.

You are given a string of length N consisting of only lowercase alphabets and two alphabets x and y. There are Q queries given and each query will be specified by two integers l and r. You have to consider the sub string [l,r] of the given string and count the total number of distinct sub sequences of the sub string which starts with x and ends with y modulo 1e9+7. 1<=N<=1e5 1<=Q<=1e5 0<=l<=r<=N-1. Example: Input: 4 aabb a b 4 0 2 1 3 2 3 0 3 Output: 3 3 0 9

Any help is appreciated. Thanks in advance.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good day to you,

firstly imagine using MO algorithm for this problem. This reduces the problem to: Dynamically Keeping the answer to the question with queries of type "append letter" and "push letter to front", and the same with delete (from back and from front).

Firstly note that these function are very similar. Appending will be (WLOG) same as pushing to front, with the difference of letters we are "thinking". Also delete will be "just" inverse of inserion.

So to the "algorithm": Imagine keeping a variable (lets cal it SUM) (WLOG keeping the same "inverse variable for last letter and pushing" — lets call it "DUAL") which means "if y will be appended, how many new answers will be added" (so note that DUAL means the same with swapped x/y and pushed-front instead of appended). This variable must be equal to Sum(2^(i)) for each "x", where i is its distance to end of current string. Also keep variable "answer".

So imagine appending a character. If it is equal to y, then we have to add SUM to answer. We also have to update DUAL by 2^|s| (where |s| means actual length of string). Now (for any character appended) multiply the SUM by 2. By this we increase the mentioned power of all "x" in the temporary string. Also, if appended character is "x", we have to add "1" to SUM (this will be the number of subsequences if new "y" will be added now).

Also note that for delete you will need modular inverse of 2, which is yet easily obtainable as "MOD/2+1"

Hope it was possible to understand at least a little bit of the solution.

Good Luck & Have Nice Day

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

    Thanks for your reply.I think I am starting to get the idea here. I came up with the same solution, just couldn't figure out what to do with l and r and wasted too much time thinking dp.

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

      The exact same question was posted by another user. I have answered it here. Also, could you please provide a link to this problem if you have one.

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

        This problems is not available for practice yet. It was asked in national instruments hiring challenge on hackerearth which ended yesterday.

        → Reply