GIFTCHEF - Editorial

[kingofnumbers]

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 10⁹ + 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 A_i 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 F_i means the number of sub-sequences of first i elements which have value 1 and A_i is selected.

how to calculate F_i? by definition A_i is the last element of all sub-sequences counted in F_i so where is the second-last element? it could be anywhere that have distance from i at least M so F_i = segma k from 1 to i-M (F_k) + 1, we added 1 because the sub-sequence that consist of only A_i (so there’s no second last element) should be counted. note that if A_i is 0 then F_i 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(N²), 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.

[acodebreaker2]

solutions link not working

[shukrant]

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

[prakhariitd]

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

[gamer_ps2]

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

[wa_6907]

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

[forhadsidhu]

anyone plz explain the dp part of the solution!

[anshal21]

@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

[mypc107]

[r_jerry1999]

what type of dp approach is this ?

[akashjain619]

nyc problem