STRAB - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Istvan Nagy
Editorialist: Amit Pandey

DIFFICULTY:

Easy-Medium.

PREREQUISITES:

Counting, Dynamic Programming, Recursion.

PROBLEM:

Given strings X and Y, count the number of strings of length n which do not contain string S (X \leq S \leq Y) of length m(\leq n) as a substring.

EXPLANATION:

In this problem it is asked to count the number of strings of length n which do not contain string S (X \leq S \leq Y) of length m(\leq n) as a substring. Let H be a set of strings which are lexicographically in between X and Y inclusively that is H = \{S : |S| = m \wedge X\leq S \leq Y \}. Now define \text{dp}[i] as the number of strings of length exactly equal to i which do not contain string(s) which belong(s) to H as a substring. It is clear that if i < m then \text{dp}[i] = 26^i.

For i \geq m, define a recursive function f(S, n, i) which takes input string s, ending index n and index i which is to be filled. This function returns the number of valid strings( which are not hated ) whose last n-i letter are already fixed as S. For example f(AB, 5, 3) will return number of valid strings of length 6(assuming zero indexing and n=5) whose last 2 letters are fixed as “AB”. Also define a function V(S, len) which return 1 if string S of length len is valid else it returns 0. Note that if len < m then the string is trivially valid else we have to check X \leq S \leq Y. Further len will always be less than or equal to m by virtue of following definition of f(S, n, i) where a value greater than m is never passed to V(S, len)

Now f(S, n, i) = 24\text{dp}[i] + f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS)) + f(BS, n, i-1)\times \text{V}(BS, \min(m, \text{len}(BS)) because the ith index can be C-Z, in which case we are left with string of length i (index 0 to i-1) thats why the term 24\text{dp}[i]; or ith index can be ‘A’ in that case we have to check whether the string from ith index to min(i+m-1, n) is valid or not thats why the term f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS)) and similar expression when ith index is ‘B’. Base case will be when i=-1 in that case return 1.

Now, for i \geq m, \text{dp}[i] = f(\text{empty string} , i-1, i-1). So, the final answer to the question will be \text{dp}[n]. Refer to the editorialist code in the solution section for more detail. The worst case time complexity of this algorithm is \mathcal{O}(n 2^n).

Solution:

Setter’s solution can be found here
Tester’s solution can be found here
Editorialist’s solution can be found here

5 Likes
2

Hello All,

I spend almost 2 hours working on this problem during the contest but not able to solve it. Now , I am not able to get whatever is mentioned in the editorial. Can any body please help me ?

2 Likes
3

What are you not getting in the editorial?

1 Like
4

Thanks for writing the tutorial! I am a little confused as well.
In f(S,n,i)=24dp[i]+f(AS,n,i−1)×V(AS,min(m,len(AS))+f(BS,n,i−1)×V(BS,min(m,len(BS))
Are you trying to fill the string from left to right or right to left? I know algorithmically it does not matter, but it is confusing since the intuition is to fill from left to right, but the formula is filling from right to left (AS instead of SA).
It’s also confusing that in some places length is used (starts with 1) while in other places “index” is used (starts with 0), which makes it difficult to think consistently.

5

Edit: It is fixed now Thanks … :smiley:
The tutorial is not readable. Please edit it.

    In this problem it is asked to count the number of strings of length $n$ which do not contain string $S (X \leq S \leq Y)$ of length $m(\leq n)$ as a substring. Let $H$ be a set of strings which are lexicographically in between $X$ and $Y$ inclusively that is $H = \{S : |S| = m \wedge X\leq S \leq Y \}$. Now define $\text{dp}[i]$ as the number of strings of length exactly equal to $i$ which do not contain string(s) which belong(s) to $H$ as a substring. It is clear that if $i < m$ then $\text{dp}[i] = 26^i$.
1 Like
6

string S is filled from right to left. First you fill a character at position i and then you recurs on i-1 which is to the left of i (hence filling it right to left). Regarding the length and index, in dp[i], i is length and in f(S,n,i) i is index. Both of which can be converted to length or index by adding/subtracting 1.

7

i tried my best to get it and finally got it. Thanks amit for writing very good editorials actually it was a new class of problem for me so it took me time to attach with the idea but when i gave it a deep thought and everything become simple :slight_smile:

1 Like
8

Can anyone check my logic please.
my logic is

  1. count the number of forbidden words(X<S<Y) (=c)[using binary format…A=0,B=1]
  2. find all the words that have these words as substring (=w)[normal combinatorics]
  3. subtract it from 26^n(26^n-c*w)
9

What is the mistake in this method?

Let dp[N] be the number of valid strings of length N, and X be the number of hated strings(of length M each).

If N < M, dp[N] = 26 ^ N,

Else, dp[N] = 26 * dp[N-1] - X * dp[N-M].

Will there be some cases that will not be counted? (or counted more than once?)

2 Likes
10

^-power of

11

I must praise you for such a neat, precise and awesome editorial.Thanks brother :slight_smile:

12

@setter

can someone explain me what this does ?

FOR (mask,0,(1 << len))

        {

            bool ok = 1;

            for (int j = 0; j+m-1 < len; ++j)

            {

                int t = (mask >> j) % (1 << m);

                if (t >= maskS && t <= maskT)

                {

                    ok = 0;

                    break;

                }

            }

            R[len] += ok;

        }
13

C++ implementation of the approach mentioned in editorial :-
C++ code