## 11081 - Strings

Moderator: Board moderators

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### I am getting WA

Can someone provide some large samle data?

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

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

kevinufo
New poster
Posts: 2
Joined: Mon Oct 08, 2007 6:16 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.

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

### Re: 11081 - Strings

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]

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

### Re: 11081 - Strings

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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am