You are not logged in. Please login at www.codechef.com to post your questions!

×

# STRAB - Editorial

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

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

This question is marked "community wiki".

asked 21 Mar '15, 01:37

25911522
accept rate: 0%

19.8k350498541

 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 ? answered 23 Mar '15, 00:19 1.7k●1●16●30 accept rate: 11% 1 What are you not getting in the editorial? (23 Mar '15, 00:26) 1 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 :) (23 Mar '15, 19:04)
 2 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?) answered 25 Mar '15, 15:18 492●3●8 accept rate: 26%
 1 Edit: It is fixed now Thanks .. :D 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$.  answered 23 Mar '15, 00:59 41●2 accept rate: 50%
 0 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. answered 23 Mar '15, 00:56 4★lxfind 301●1●4●7 accept rate: 14% 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. (23 Mar '15, 01:00)
 0 Can anyone check my logic please. my logic is 1. count the number of forbidden words(X
 0 I must praise you for such a neat, precise and awesome editorial.Thanks brother :) answered 06 Apr '15, 20:13 1●1 accept rate: 0%
 0 @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; } answered 17 May '15, 11:48 55●6 accept rate: 0%
 0 C++ implementation of the approach mentioned in editorial :- C++ code answered 14 Apr '16, 22:19 4★ps06756 18●1●2 accept rate: 9%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,168
×1,672
×345
×124
×2

question asked: 21 Mar '15, 01:37

question was seen: 3,537 times

last updated: 14 Apr '16, 22:19