11081  Strings
Moderator: Board moderators

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:
11081  Strings
O(n^3) dp ? Then, what is the recurance?
or, sth other ?
Can it solved using n^2 ?
Thanks!
or, sth other ?
Can it solved using n^2 ?
Thanks!

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
First take a string like: abc
Then compare it with third string like: abc
then ^^^^
So you can check it recursively with FOR LOOP. If match(above) then go if not check the second string just the same way.
And you must count the number of return value.
Hope this will help.
Then compare it with third string like: abc
then ^^^^
Code: Select all
a b c
  
a b c
And you must count the number of return value.
Hope this will help.

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:
What does it mean ? Would you explain more elaborately.....If match(above) then go if not check the second string just the same way
what is the output for
Code: Select all
aa aa aa
a a aaa
ab ac abc
Thanks.

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
For your input, my output is:
Here i explain one example for you. Ok.
Now we got 5 from aaaa(aa aa). But if we combine them differently then it will be 10. So in memoization with indexing(e.g, memo[j]) you will get overlapping value so just return it then it will be 10. Now is it clear?
Code: Select all
10
0
2
Code: Select all
aa aa aa
1)
s1[0]>s3[0]
s1[1]>s3[1] so at the end of s3 return 1;
s2[0]>s3[1] so at the end of s3 return 1;
s2[1]>s3[1] so at the end of s3 return 1;
s1[1]>s3[0]
s2[0]>s3[1] so at the end of s3 return 1;
s2[1]>s3[1] so at the end of s3 return 1;
is there any O(n^3 ) dp for this problem . i used O(n^4) dp to get accepted during the contest which is getting TLE in the judge now . so can some one point out the O(n^3) algorithm or O(n^4) is way to go .........
thanx in advance
thanx in advance
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Denote a = a1a2...ak, b = b1b2...bm and c = c1c2...cn. My DP counts the function f(t,x,y,z) that expresses the number of ways to create string czcx+1...cn from strings axax+1...ak and byby+1...bm under assumption that the character cz is made by a character from b if t=1, or by a character from a if t=0.Riyad wrote:would u care to tell us your DP solution which runs in O(n^3) iLL be really glad to know one if u dont want to give a spoiler u can PM me ur idea , anywayz thanx for ur reply ...
To not write too much spoilers here I let the rest of the idea on you
TLE
I have a DP solution (hope n^3 ) where I hava a function f( i , j, k) which returns the number of possible ways to form the string by taking the kth character with any character in first string from ith position or with a character from second string starting from jth positon ...
I use memoization to store this value..
Unfortunately it TLE 's...
I no one has problem I may paste my code here...
can anybody suggest me something??
I use memoization to store this value..
Unfortunately it TLE 's...
I no one has problem I may paste my code here...
can anybody suggest me something??
If I will myself do hashing, then who will do coding !!!

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
I've no idea why you're getting TLE. My solution is just a straight forward memoization counting the function mentioned above. But it's rather a short recursive function with no loops and just few recursive calls.vinay wrote:ohh..
I realise that my function is same as
Marko's
then why is it TLE???
Marko can I send u my code
During the contest the solution got ACed in 0:00.834. Now it gets ACed in 0:05.256. Probably, they have a much bigger input set, now.
You can post your solution here, if you want, maybe, I'll look on it
code
here it goes...
Code: Select all
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
char s1[61],s2[61],s3[61];
int sz1,sz2,sz3,dp[61][61][61];
int fun(int i,int j,int k){
if(sz1i+sz2j<sz3k) return 0;
if(dp[i][j][k]!=1) return dp[i][j][k];
dp[i][j][k]=0;
for(int index=i;index<sz1;index++){
if(s1[index]==s3[k]){
if(k==sz31) dp[i][j][k]=(dp[i][j][k]+1)%10007;
else
dp[i][j][k]=(dp[i][j][k]+fun(index+1,j,k+1))%10007;
}
}
for(int index=j;index<sz2;index++){
if(s2[index]==s3[k]){
if(k==sz31) dp[i][j][k]=(dp[i][j][k]+1)%10007;
else
dp[i][j][k]=(dp[i][j][k]+fun(i,index+1,k+1))%10007;
}
}
return dp[i][j][k]%10007;
}
int main(){
int t;
scanf("%d",&t);
while(t){
scanf("%s%s%s",s1,s2,s3);
sz1=strlen(s1);
sz2=strlen(s2);
sz3=strlen(s3);
for(int i=0;i<=sz1;i++){
for(int j=0;j<=sz2;j++){
for(int k=0;k<=sz3;k++){
dp[i][j][k]=1;
}
}
}
printf("%d\n",fun(0,0,0)%10007);
}
return 0;
}
If I will myself do hashing, then who will do coding !!!

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: code
IMO, your solution is O(N^4). Note the loop in your function.vinay wrote:here it goes...
Try the following input yourself:
Code: Select all
1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa