11081  Strings
Moderator: Board moderators
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
 Location: IUTOIC, DHAKA, BANGLADESH
 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?
thnx in advance.
my dp is 3*N^3 with 4 recursive calls.
I think there is inclusion exclusion approach,,Have anyone found out?
thnx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11081  Strings
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.
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.
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][i1][j] + dp[k][j1]  dp[k][i1][j1] //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[k1][i1][j]; //I count all the ways to make c[1..k1] and add the letter a at the end of each one
dp[k][j] = dp[k1][i1][j1] //I already added dp[k][j1], which includes ways in dp[k1][i1][j1] and also dp[k1][i1][j] includes dp[k1][i1][j1], so they were added twice
}
I do something similar in case b[j] == c[k]
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][i1][j] + dp[k][j1]  dp[k][i1][j1] //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[k1][i1][j]; //I count all the ways to make c[1..k1] and add the letter a at the end of each one
dp[k][j] = dp[k1][i1][j1] //I already added dp[k][j1], which includes ways in dp[k1][i1][j1] and also dp[k1][i1][j] includes dp[k1][i1][j1], 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.
iterative dp is faster with same approach.
run time reduced to 0.256 from 1.088 sec.
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
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.
This may be the address of success.