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

×

GIFTCHEF - Editorial

4
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Easy

PREREQUISITES:

KMP, dynamice programming

PROBLEM:

Given two strings S and F, how many ways there are to choose arbitrary number of non-overlapping substrings of S so that each substring is equal to F. output the answer modulo 109 + 7.

EXPLANATION:

let's say the length of string S is N, and the length of string F is M.

the solution which we are going to describe will consist of two parts, the first part is to calculate an array A which we are going to define below then the second part is make use of that array to calculate the final answer.

what is that array A? it's an array of length N such that each element can be either 0 or 1, if the substring of length M which ends at i is equal to string M then Ai is equal to 1, otherwise it's equal to 0.

how to calculate this array? this is a standard problem known as "string matching problem" which can be done by various algorithms, in particular it can be done in O(N+M) using KMP algorithm.

now after we calculate that array the problem is reduced to calculating the number of sub-sequences of A such that all elements of the sub-sequence are equal to 1 and no two elements of the sub-sequence have distance from each other less than M (otherwise those two elements will correspond to overlapping substrings of string S)

to calculate the number of sub-sequences we will use dynamic programming:

let Fi means the number of sub-sequences of first i elements which have value 1 and Ai is selected.

how to calculate Fi? by definition Ai is the last element of all sub-sequences counted in Fi so where is the second-last element? it could be anywhere that have distance from i at least M so Fi = segma k from 1 to i-M (Fk) + 1, we added 1 because the sub-sequence that consist of only Ai (so there's no second last element) should be counted. note that if Ai is 0 then Fi should be 0 because we only select elements of value 1.

calculating each value of F takes O(N) steps, and we need to calculate O(N) values, so overall complexity is O(N2), but if we notice that elements inside the sigma are always a prefix of F, then we can use cumulative prefix sums so we can calculate the sigma in O(1) and overall complexity of dynamic programming would be O(N)

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 24 Oct '16, 00:36

kingofnumbers's gravatar image

6★kingofnumbers ♦
194824
accept rate: 12%

edited 16 Nov '16, 13:34

admin's gravatar image

0★admin ♦♦
19.7k350498541

Can someone please explain the use of the dist array in the solution link,which is shared in one of the above comments?

(17 Nov '16, 01:09) gamer_ps21★

@forhadsidhu , consider the following code and then the given explanation-

ll doit(int pos,int sel,int n){
if(pos==n){
    return sel;
}
if(dp[pos][sel]!=-1)
    return dp[pos][sel];
ll ans=0;
if(mark[pos]){
    ans=ans+doit(pos+m,1,n)+doit(pos+1,sel,n);
}
else
    ans=ans+doit(pos+1,sel,n);
dp[pos][sel]=ans%mod;
return ans%mod;

}

  1. parameter pos represent the index at where I am at current time ,and sel represent if I have selected atleast one pattern or not.
  2. mark[i] represent that if any pattern start from ith position or not.
  3. now at every instant you have two cases , Either a pattern starts at this location or not -
  4. now if a pattern start at current position , you have two option either select current pattern and go to pos=pos+length_of_pattern , or do not select the pattern and go to position pos=pos+1 , if you select the pattern make the value of sel=1 for further calls.
  5. if pattern does not start at this position , you have only one option go to pos=pos+1
  6. when you reach at the end if sel=1 return 1 because this is a valid configuration or return 0
link

answered 20 Nov '16, 14:21

anshal21's gravatar image

4★anshal21
6068
accept rate: 7%

solutions link not working

link

answered 16 Nov '16, 14:09

acodebreaker2's gravatar image

1★acodebreaker2
1.2k11
accept rate: 19%

link

answered 16 Nov '16, 14:31

shukrant's gravatar image

4★shukrant
1214
accept rate: 22%

edited 16 Nov '16, 14:36

The dynamic programming part is same as what was used in goodsets problem of ICPC online round.

link

answered 16 Nov '16, 23:09

prakhariitd's gravatar image

6★prakhariitd
1.1k211
accept rate: 10%

link

answered 18 Nov '16, 14:08

wa_6907's gravatar image

3★wa_6907
1
accept rate: 0%

anyone plz explain the dp part of the solution!

link

answered 20 Nov '16, 10:43

forhadsidhu's gravatar image

2★forhadsidhu
1
accept rate: 0%

link

answered 21 Nov '16, 20:32

mypc107's gravatar image

2★mypc107
1
accept rate: 0%

what type of dp approach is this ?

link

answered 22 Nov '16, 00:12

r_jerry1999's gravatar image

3★r_jerry1999
1
accept rate: 0%

nyc problem :)

link

answered 23 Nov '16, 08:53

akashjain619's gravatar image

2★akashjain619
1
accept rate: 0%

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:

×15,477
×3,704
×2,085
×150
×66
×26

question asked: 24 Oct '16, 00:36

question was seen: 4,906 times

last updated: 23 Nov '16, 08:53