11081 - Strings

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

11081 - Strings

Post by Nazmul Quader Zinnuree » Sat Sep 02, 2006 4:48 pm

O(n^3) dp ? Then, what is the recurance?
or, sth other ?
Can it solved using n^2 ?

Thanks!

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Sep 02, 2006 5:29 pm

First take a string like: abc
Then compare it with third string like: abc
then ^^^^

Code: Select all

a b c
| | |
a b c
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.

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Sat Sep 02, 2006 5:45 pm

If match(above) then go if not check the second string just the same way
What does it mean ? Would you explain more elaborately.....

what is the output for

Code: Select all

aa aa aa
a a aaa
ab ac abc
Plz, explain with an example.

Thanks.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sat Sep 02, 2006 6:09 pm

For your input, my output is:

Code: Select all

10
0
2
Here i explain one example for you. Ok. :)

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;
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?

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sat Sep 02, 2006 7:22 pm

It is strange... during the contest i got ACed an n^4 algorithm, that of course, i can't get ACed now..
Impossible is nothing

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Sat Sep 02, 2006 7:41 pm

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh » Sat Sep 02, 2006 8:03 pm

Well, my rather inefficient ACed solution (I mod 10007 everywhere, instead of just doing a mod where its needed) is O(n^3).

So yes, there is an O(n^3) solution... you just need to look for it :wink:

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Sat Sep 02, 2006 8:10 pm

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 ...
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Sep 02, 2006 9:07 pm

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

To not write too much spoilers here I let the rest of the idea on you :wink:

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

TLE

Post by vinay » Sat Sep 02, 2006 9:44 pm

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?? :oops:
If I will myself do hashing, then who will do coding !!!

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Sat Sep 02, 2006 9:51 pm

ohh..
I realise that my function is same as
Marko's

then why is it TLE???
Marko can I send u my code :oops:
If I will myself do hashing, then who will do coding !!!

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Sep 02, 2006 10:15 pm

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 :oops:
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.

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

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

code

Post by vinay » Sat Sep 02, 2006 10:20 pm

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(sz1-i+sz2-j<sz3-k) 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==sz3-1) 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==sz3-1) 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 !!!

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: code

Post by Martin Macko » Sat Sep 02, 2006 10:31 pm

vinay wrote:here it goes...
IMO, your solution is O(N^4). Note the loop in your function.

Try the following input yourself:

Code: Select all

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
If it takes more than 0.2s (on 1G machine), it won't get accepted, definitely. Now it takes 0.8s.

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sun Sep 03, 2006 1:46 am

thanks Martin for your hint!
Impossible is nothing

Post Reply

Return to “Volume 110 (11000-11099)”