GIFTCHEF - Editorial

dynamic-programming
easy
editorial
giftchef
kmp
nov16

#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.


#2

solutions link not working


#3

you can refer this solution https://www.codechef.com/viewsolution/12062714


#4

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


#5

you can see this solution
https://www.codechef.com/submit/complete/12112951


#6

anyone plz explain the dp part of the solution!


#7

@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* 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

#8

#9

what type of dp approach is this ?


#10

nyc problem :)


#11

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