A very interesting OA problem

Revision en4, by ShivanshJ, 2023-09-30 00:04:41

Many of my friends asked this interesting OA problem to me:

Given an array of strings $$$A$$$ of size $$$N$$$ and two integers $$$B$$$ and $$$C$$$.

Let $$$D$$$ be the number of strings of length $$$C$$$ that contains exactly $$$B$$$ of the strings in $$$A$$$ as substring.

Return $$$D$$$ mod $$$10^9+9$$$.


$$$1 \le N \le 6$$$

$$$1 \le |A[i]| \le 50$$$

All the $$$N$$$ strings are distinct

$$$0 \le B \le N$$$

$$$1 \le C \le 50.$$$

Note that if a substring belonging to set $$$A$$$ occurs multiple times in my resulting string, it is counted only once.

My approach:

Let $$$Z$$$ be the size of the alphabet $$$(26)$$$.

Let $$$dp[i][j][k][m]$$$ denote the number of strings satisfying the constraints:

1) It is of length $$$i$$$.

2) The longest suffix present in it which is a proper prefix of some string belonging to set $$$A$$$ is the substring $$$[k...i]$$$ and the string whose proper prefix is the $$$j^{th}$$$ string in set $$$A$$$, in case of multiple such strings in $$$A$$$ choose the one with longest length. In case no such suffix exists, we can put a fake "empty string" at index $$$0$$$ in set $$$A$$$ (rest of the strings are numbered from $$$1$$$ to $$$N$$$) and assume that substring is $$$[i+1 , i]$$$.

3) The substrings (belonging to set $$$A$$$) which has already been occurred is denoted by mask $$$m$$$, more formally, if the $$$w^th$$$ string in $$$A$$$ has already occurred, then $$$w^{th}$$$ bit of $$$m$$$ is set, otherwise its not.

I'll write transitions via forward style dp, if I'm adding the $$$(i+1)^{th}$$$ character, then, it might "complete" some substrings, by this I mean, some suffix which was a proper prefix of some string in $$$A$$$ before adding character will now be a complete string belonging to set $$$A$$$. Note that all such strings will be the suffix of that longest suffix.

So, some new bits in mask $$$m$$$ will be set, All this can be calculated, since we already know the longest suffix, in fact lets precalculate, $$$info[i][j][k]$$$ which gives a tuple $$$(bitmask, L, idx)$$$. If we consider the prefix of length $$$j$$$ of $$$i^{th}$$$ string in set $$$A$$$ and add character $$$k$$$ at the end, $$$w^{th}$$$ bit in bitmask is set iff, entire $$$w^{th}$$$ string in $$$A$$$ occurs as a substring in that prefix after adding character $$$k$$$, $$$L$$$ denotes the length of the longest suffix in resulting string (after adding character $$$k$$$) that is a proper prefix of $$$idx^{th}$$$ string in set $$$A$$$, this precomputation can be done naively in $$$O(N*C*Z*N)$$$.

So, after adding $$$(i+1)^{th}$$$ character (denote it by $$$c$$$), new mask is $$$info[j][i-k+1][c][0]$$$, new length of longest suffix is $$$info[j][i-k+1][c][1]$$$ so, add its contribution towards state $$$dp[i+1][info[j][i-k+1][c][3]][i+2-info[j][i-k+1][c][1]][info[j][i-k+1][c][0]]$$$.

I think the complexity would be $$$O(C*N*C*2^{N}*Z)$$$, which might pass. However, I think I'm overkilling it and there has to be simpler solution. I'm not even sure whether my solution is correct or not.

Tags dp, interesting problem, bitmask, cool problems


  Rev. Lang. By When Δ Comment
en8 English ShivanshJ 2023-09-30 00:18:29 2 Tiny change: 'i-k+1][c][3]][i+2-inf' -> 'i-k+1][c][2]][i+2-inf'
en7 English ShivanshJ 2023-09-30 00:10:03 13
en6 English ShivanshJ 2023-09-30 00:08:07 13 (published)
en5 English ShivanshJ 2023-09-30 00:06:38 2 Tiny change: 'if the $w^th$ string i' -> 'if the $w^{th}$ string i'
en4 English ShivanshJ 2023-09-30 00:04:41 4
en3 English ShivanshJ 2023-09-30 00:04:16 84 Tiny change: '$D$ mod $1e^9+9$.\n\n' -> '$D$ mod $10^9+9$.\n\n'
en2 English ShivanshJ 2023-09-30 00:01:33 2370 Tiny change: 'e 50.$\n\n\n\n\n' -> 'e 50.$\n\nMy approach:\n\nLet $dp[i][j][k][mask]\n\n\n\n\n'
en1 English ShivanshJ 2023-09-29 23:17:20 439 Initial revision (saved to drafts)