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

×

STRAB - Editorial

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

This question is marked "community wiki".

asked 21 Mar '15, 01:37

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 18:39

admin's gravatar image

0★admin ♦♦
19.8k350498541


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 ?

link

answered 23 Mar '15, 00:19

ma5termind's gravatar image

3★ma5termind
1.7k11630
accept rate: 11%

edited 23 Mar '15, 00:20

1

What are you not getting in the editorial?

(23 Mar '15, 00:26) amitpandeykgp4★
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) ma5termind3★

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?)

link

answered 25 Mar '15, 15:18

ajinkya1p3's gravatar image

5★ajinkya1p3
49238
accept rate: 26%

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$.
link

answered 23 Mar '15, 00:59

that70show's gravatar image

4★that70show
412
accept rate: 50%

edited 23 Mar '15, 01:01

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.

link

answered 23 Mar '15, 00:56

lxfind's gravatar image

4★lxfind
301147
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) saurabh0607924★

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)

link

answered 25 Mar '15, 13:28

sravy_171's gravatar image

2★sravy_171
1
accept rate: 0%

^-power of

(25 Mar '15, 15:24) sravy_1712★

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

link

answered 06 Apr '15, 20:13

mithunmk93's gravatar image

4★mithunmk93
11
accept rate: 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;
}

link

answered 17 May '15, 11:48

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

edited 17 May '15, 11:51

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

link

answered 14 Apr '16, 22:19

ps06756's gravatar image

4★ps06756
1812
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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