11081 - Strings

[tanaeem]

Can someone provide some large samle data?

[kbr_iut]

my runtime is 1.728 sec. I saw runtime like 0.152 sec in ranklist. Those who got better runtime ,can u share ur idea.
my dp is 3*N^3 with 4 recursive calls.
I think there is inclusion exclusion approach,,Have anyone found out?

thnx in advance.

[kevinufo]

Does anyone provide some hints about this problem?
I can't figure out the recurrence equation either in O(n^4) or O(n^3).
Any comment or example will help me a lot.
Thanks.

[pdwd]

This is my solution:

Let a - first string, b - second string, c - third string.
I have dp[k][j] - number of ways to make c[1..k] using letters from a[1..i] and b[1..j]

dp[0][j] = always 1 (there is only one way to make empty string - remove all letters from a and b)

dp[k][j] = dp[k][i-1][j] + dp[k][j-1] - dp[k][i-1][j-1] //I dont take letter a, then don't take b[j] and I have to subtract common part that I added twice
if(a == c[k])
{
dp[k][j] += dp[k-1][i-1][j]; //I count all the ways to make c[1..k-1] and add the letter a at the end of each one
dp[k][j] -= dp[k-1][i-1][j-1] //I already added dp[k][j-1], which includes ways in dp[k-1][i-1][j-1] and also dp[k-1][i-1][j] includes dp[k-1][i-1][j-1], so they were added twice
}
I do something similar in case b[j] == c[k]

[Jehad Uddin]

@kbr_iut
iterative dp is faster with same approach.
run time reduced to 0.256 from 1.088 sec.

[Obaida]

@kabir_iut
I used 60 x 60 x 60 x 2 Dp state and 6 recursive calls (Without Exclusion)
and my running time is .744sec