Codeforces Round 635 Div2/E (DP solution explanation needed)

https://codeforces.com/contest/1337/problem/E
Can you explain the solution to this problem and your approach in detail and simple points? (E. Kaavi and Magic Spell)
The editorial for this problem is quite confusing and complex, the comments didn’t help either.

2 Likes

I have solved it slightly differently.

Let dp[i][j] denote the number of ways to choose the first i+1 elements of S, such that they match with T[j]...T[j+i]. If something is out of bounds, it doesn’t matter, since only the prefix has to be the same, and is considered matched.

Firstly, the base cases:
For dp[0][j], it only has to match with T[j], and we can directly check that.
So if S[0]=T[j], dp[0][j]=2, since both back and front count, Otherwise it’s 0.

Let us consider the relations for dp[i][j]
if S[i]=T[j], we can push S[i] at the front of a string that matches up with T[j+1] ... T[j+i], and has length i. The only special case is when j=m-1, That means the rest of the characters are irrelevant, since the have to match with T[m] onwards, which are all out of bounds. Since there are i ignored elements(Recall dp[i][j] has i+1 elements) we add 2^i instead, since each element could be back or front.
So our first relation, for pushing S[i] at the front is

if(S[i]==T[j]){
      if(j==m-1){
            dp[i][j]+=modpower(2,i);
      }
      else{
            dp[i][j]+=dp[i-1][j+1]
      }
}

The second relation comes when we push it at the back
Since dp[i][j] has to match up with T[j]..T[i+j], and we are pushing it at the back, S[i]=T[i+j]. If it is out of bounds, Then S[i] doesn’t matter and we can push it at the back anyways. So we can add dp[i-1][j], since previously the string matched with T[j] ... T[j+i-1] and we added S[i] to match with T[i+j]
So our relation for pushing it at the back is

if(i+j>=m or S[i]==T[i+j]){
      dp[i][j]+=dp[i-1][j];
}   

Now the final answer is
\sum_{i=m-1}^n dp[i][0]
Since for all i >=m-1, dp[i][0] indicates a matching sequence from T[0] to T[m-1]. Since the second index is 0, it starts from T[0], and since the first index is more than m-1, it has enough elements for the full prefix.

My submission link : Submission #77097244 - Codeforces

4 Likes