## 11081 - Strings

Moderator: Board moderators

### I am getting WA

Can someone provide some large samle data?
tanaeem
New poster

Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET

### Re: 11081 - Strings

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?

It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

### Re: 11081 - Strings

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.
kevinufo
New poster

Posts: 2
Joined: Mon Oct 08, 2007 6:16 pm

### Re: 11081 - Strings

This is my solution:

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

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

dp[k][i][j] = dp[k][i-1][j] + dp[k][i][j-1] - dp[k][i-1][j-1] //I dont take letter a[i], then don't take b[j] and I have to subtract common part that I added twice
if(a[i] == c[k])
{
dp[k][i][j] += dp[k-1][i-1][j]; //I count all the ways to make c[1..k-1] and add the letter a[i] at the end of each one
dp[k][i][j] -= dp[k-1][i-1][j-1] //I already added dp[k][i][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]
pdwd
New poster

Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 11081 - Strings

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

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11081 - Strings

@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
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am