kstheking's blog

By kstheking, history, 4 years ago, In English

We had this question on our Internship test, and I couldn't figure out how to do it, help please

Given a string s and a number p find number of unique special strings that can be formed using the given string
A special string is a permutation of string made from a subsequence of s, whose sum of ASCII values of its characters is divisible by p
Example: s = "ab", p = "2"
answer = 1
all possible unique strings = "a","b","ab", "ba"
respective sums = 97, 98, 195, 195
reason: since there is only one number (98) which is divisible by 2 so total answer = 1
Constraints: |s| <= 20 and 1 <= p <= 200
print the answer modulo 1000000007

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

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

You can try 3D DP where :
1st state represents the current index of the string
2nd state represents the current sum of ASCII values of the subsequence chosen (It ranges from 122 to 122*n)
3rd state represents the current modulo of the subsequence ASCII sum with p
This should work because the time complexity would be n*(122*n)*p where n is |s|.
UPD : Didn't took care of the unique sunstring thing, Since the string length is <=20, backtracking approach might work out considering all the possibilities of the subsequences.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

was it on campus or off?? (OFF-TOPIC)

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

iterate though all mask from 1 to (1<<n) special string => sum of ascii values of all character in the current mask should be divisible by p(can be checked) unique string => maintain trie or set to check this all possible combination using current mask => let frequency be c1,c2....c26 (assuming alphabet size = 26) ans = (c1+c2+.....)! / c1! * c2 ! ........ c26!

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

We can find all 2^n strings and then count sum of ASCII values of character in each string. If sum is divisible by p then add the value of all possible permutation of that string to result. I think this will fit in given TL

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Special String formed is permutation of the given string not subsequnce.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Special String is "a permutation of string made from a subsequence of s". So can't we just find find all 2^n strings and then count sum of ASCII values of character in each string and find the number of permutations of this string?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        There are more than 2^n strings, just try to calculate for "abc".

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      For 'abc' -> 'a', 'b', 'c', 'ab' (permutation -'ba' ), 'bc' (permutation -'cb' ), 'ac' (permutation -'ca' ), 'abc' (permutation -'acb' , 'bca' , 'bac' , 'cab' , 'cba') =3! Am I correct?

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

        Yes this is what I was trying to say

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

          Yeah, I have generated all 2^n strings. If sum is divisible then I will add all permutation of that string into answer. For which TC it will fail?

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

You can store frequency of each character then solve it using dp with 3 states(current character, sum with mod p, current length of the string).

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

    can we find permutations of all strings @induber

    then count sum of ASCII values of character in each string. If sum is divisible by p then add the value of all possible permutation of that string to result.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Let the string s be of length 20 and having all characters distinct, then there 20! string of length 20, similarly (20C19)*19! of length 19, (20C18)*18! of length 18 and so on, So you can't find all the permutations.

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

    Would you mind elaborating your solution a bit...like the states arent clear to me !!

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

    You wouldn't be able to calculate permutations by this process. For that you must also add another parameter that will store modular inverse of products of factorials of the count of each characters we have used so far

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

      (For recursive DP)

      During recursion call you can multiply the inverse of factorial of character count and when the recursion ends(current char exceeds 'z') just return length!.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        That's a very cool approach. Thanks for sharing it!

»
4 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Try all possible subsequences and if subsequence X is good then add its number of unique permutations (Factorial of length divided by factorials of character's frequencies) to the answer, since its all possible permutation will be the answer as well.

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

    Acha cool so any how we have to generate all possible subsequence and so the TL still remains O(2^N) for N<=20 .

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

      Generate with bitmasks, it will take around one million operations which is good for one second.

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

    There can be duplicate also. So we can not directly add |x|!. We have to divide by factorial of count of each character. Like for "aab" it will be 3!/2!

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yep, I missed that case and edited the comment. Thanks.

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

Since |s| <= 20, there would be (2^20, i.e. 10^6) combinations, so just brute force every, if any subsequence is divisible by p, do some combinatrics(can be done in O(len)) to find unique permuations.

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

    it was giving TLE i got 150 marks out of 300 cz i was not able to find the intended backtracking solution :)

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Just backtrack to find every possible sums. To know unique strings whose sum is divisible by p, you just have to know how many characters it took to build this sum. Like here = "abc" and p=2, we can find 97, 98, 99, 195, 196, 197, 294 and 0 if we backtrack all possible sums. We'll just ignore 0 here. So here 98,196 and 294 are divisible by 2. 98 took 1, 196 took 2 and 294 took 3 characters . So the answer is 1! + 2! + 3! = 9

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

    what will be the time complexity of this? i do not know this kind of approach can you plz tell how will you backtrack?

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

      Complexity — O(2^n) If you don’t know what backtracking is here you can check out ->
      https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        an O(2^n)*(20+26)*(time coplexity for modular inverse) solution is what i submitted and i got TLE. Someone else also told me that backtracking worked but i still don't know how. Thank you sharing that tut and plz share the code or psude code if time permits. Thank you

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

            This code might not work if considered duplicate characters in the given string 's'.

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              Yes a person already inboxed me that issue. Then we should use vector of frequency instead of cnt.

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

            Why is backtracking faster than bitmask approach ?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          You can do some optimizations to improve runtime. Here are a few of my thoughts:

          Spoiler
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Since $$$|S|$$$ is quite small try generating all subsets and find the answer using combinatorics. Let's say current subset chooses some indices where these characters occurs -> "aaaeedd"(their order doesn't matter). If their $$$sum$$$ is divisible by $$$p$$$ then we can permute them in $$$7! / (3! * 2! * 2!)$$$ ways and add them to our answer. take care not to overcount since we need unique strings (e.g. $$$S$$$ = "abab", so choosing subset {0, 1} {0, 3}, {2, 3} are all same and should be counted only once).

PS: the above solution of mine seems correct to me but if you find anything wrong then please let me know. Thanks.

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

    How will you prevent over-counting?

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

      all we care is about the frequency of elements, so we can use unordered map or map to hash the vector of frequency or even first generate all subsets, store their frequency and use sort + unique. Then we can do the same mentioned above. I bet that i can make it work in one second.

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

I think this should work...

#include <bits/stdc++.h>
#define int long long
using namespace std;

int mod = 1e9 + 7;
vector<int> fac(22,0), freq(26,0);
int dp[202][202][22];

void precompute()
{
    fac[0] = fac[1] = 1;
    for(int i=2; i<=21; i++)
    {
        fac[i] = (fac[i-1] * i) % mod;
    }
}

int solve(int idx, int sum, int siz, string &s, int &p)
{
    if (idx == s.size()) return 0;
    if (dp[idx][sum][siz] != -1) return dp[idx][sum][siz];
    int ans = solve(idx + 1, sum, siz, s, p) % mod;
    int x = 0;
    for(int i=1; i<=freq[s[idx]- 'a']; i++)
    {
        x = (sum + i * (s[idx]))%p;
        if (x == 0) ans = (ans + ((fac[siz + i] / fac[i]) % mod) + solve(idx + 1, 0, siz + i, s, p) ) % mod;
        else ans = (ans + solve(idx + 1, x, siz + i, s, p)) % mod;
    }
    return dp[idx][sum][siz] = ans % mod;
}

int32_t main()
{
    precompute();
    string s; cin >> s;
    int p; cin >> p;
    memset(dp,-1,sizeof(dp));
    string x;
    for(int i=0; i<s.size(); i++)
    {
        if (freq[s[i] - 'a'] == 0) x.push_back(s[i]);
        freq[s[i] - 'a']++;
    }
    cout << solve(0, 0, 0, x, p);
}