gagannagpal68's blog

Any combinatorics solution rather than DP?
By gagannagpal68, history, 3 years ago, In English

Given a string s and a number k. You need to tell count of distinct string of length k. s.t. k is a subset of s.

Eg 1. "aaabb" 2 => 4 (aa bb ab ba)

  1. "aabbcc" 2 => 9( aa ab ac ba bb bc ca cb cc)

  2. "abbcc" 2 => 8( same as #2 but aa can't be formed

I can create a dp of state index and mask where mask is of base 26 and rest is straightforward. Please help me in finding some combinatorics approach of solving it.

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

Comments Comments (25)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).

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

I have something want to say.

I have another dp state that dp[26][len] means the distinct string of length len where we have used which alpha. Transition is simple dp[i+1][len+c] <- dp[i][len] * C(len+c, c)

And I have another problem related with your problem. Here it is . The difference is that we must use all the char in the original string. Hope you enjoy solve this problem.

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

    Could you please elaborate the transition a little? Particularly, what is c?

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

      I guess, C is a binomial coefficient, that is $$$C(n, k) = C_n^k = \left(^n_k\right) = \frac{n!}{k!\cdot(n-k)!}$$$

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

        Yes, the big C does represent the n choose k. But I meant what does len+c stand for?

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

          Ah, yes, sorry. The answer is here.

          small c is iterating variable for 0...freq[i] (assuming i is ith char in alphabets).

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

    Can you please elaborate how to solve the problem from CSES that you have given the link?

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

      There are several ways to solve it.

      First you can read the paper of Sequences with Adjacent Elements Unequal

      Second you can use include-exclude principle with dp

      Third you can read https://arxiv.org/pdf/1306.6232.pdf and related with generalized laguerre polynomials.

      All of them may have connections with other methods

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

    Makes sense. small c is iterating variable for 0...freq[i] (assuming i is ith char in alphabets). Right?

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

i guess its classic application of E.G.F.
lets set of characters be $$$a_i,f_i $$$, here $$$f_i$$$ represents the frequency
your answer will be
$$$ [x^k] \prod_{i} (\sum_{j=0}^{f_i}\frac{x^j}{j!})$$$
here $$$\sum_{j=0}^{f_i}\frac{x^j}{j!} $$$ is generating function for character $$$a_i$$$ with frequenccy $$$f_i$$$

multiply by k! as we are using coeffiecient of $$$x^k$$$

like for first example answer is $$$2! \times [ \frac{1}{2!} + \frac{1}{1!} + \frac{1}{2!} ]$$$
which is equal to 4.

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

    It's not making sense. Can you also write the example answer for case #2 and #3 ? That will help.

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

I have a dp + combinatorics solution

let dp[i] denote the number of strings of length i, we have parsed till the jth alphabet. Lets say we take l number of jth alphabet 

dp[i]+=dp[i-l]*nCr(i,l);
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    J is not used anywhere — are we considering sum(nCr for l = 1..J))? k is not used anywhere — answer is the same for every k?

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

      No means actually it is dp[i][j] but you can compress the 2D DP into only dp[i] in knapsack right ? Also final answer is dp[k].

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Still no clue
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Not sure what you are not getting, maybe this code can help.

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

            Yep, thanks! This makes it all clear. For every d[i] you count how many times you can add some letter L = 1..freq(letter) times, using previously calculated dp[i-L] for previous letters. This looks like O(k*length(s)) solution.

            → Reply