11081  Strings
Moderator: Board moderators
recurrence problem
I have built up the recurrence of the form:
f(0,i,j,k) = f(0,i+1,j,k)
if(ai ==ck) f(0,i,j,k) += f(0,i+1,j,k+1)+f(1,i+1,j,k+1);
similarly
f(1,i,j,k) = f(1,i,j+1,k)
if(bj ==ck) f(1,i,j,k) += f(0,i,j+1,k+1)+f(1,i,j+1,k+1);
Is it right???
If yes, then there is another problem , I m very confused with the boundary conditions...
CAn anyone help me on that???
f(0,i,j,k) = f(0,i+1,j,k)
if(ai ==ck) f(0,i,j,k) += f(0,i+1,j,k+1)+f(1,i+1,j,k+1);
similarly
f(1,i,j,k) = f(1,i,j+1,k)
if(bj ==ck) f(1,i,j,k) += f(0,i,j+1,k+1)+f(1,i,j+1,k+1);
Is it right???
If yes, then there is another problem , I m very confused with the boundary conditions...
CAn anyone help me on that???
If I will myself do hashing, then who will do coding !!!
Re: recurrence problem
That's right.vinay wrote:I have built up the recurrence of the form:
f(0,i,j,k) = f(0,i+1,j,k)
if(ai ==ck) f(0,i,j,k) += f(0,i+1,j,k+1)+f(1,i+1,j,k+1);
similarly
f(1,i,j,k) = f(1,i,j+1,k)
if(bj ==ck) f(1,i,j,k) += f(0,i,j+1,k+1)+f(1,i,j+1,k+1);
Is it right???
If yes, then there is another problem , I m very confused with the boundary conditions...
CAn anyone help me on that???
You can define g(i,j,k) = f(0,i,j,k)+f(1,i,j,k)
g(i,j,clen)=1 for 0<=i<=alen, 0<=j<=blen
And for k<clen, the boundary condition is
f(0,alen,j,k)=f(1,i,blen,k)=0
the rest is ok with yours. Just replace it with g as needed in the case where ai==ck and bj==ck
Also, i used stl::string and it is tle, but char [61] is AC.
The special case is needed to deal with empty strings.
The formulation without the function g doesn't really work when k=clen.
Re: recurrence problem
What empty string r u talking about ?/sclo wrote: And for k<clen, the boundary condition is
f(0,alen,j,k)=f(1,i,blen,k)=0
the rest is ok with yours. Just replace it with g as needed in the case where ai==ck and bj==ck
[/qoute]
and for k==clen what will be f(0,i,j,k) or f(1,i,j,k) ???
sclo wrote: The special case is needed to deal with empty strings.
The formulation without the function g doesn't really work when k=clen.
If I will myself do hashing, then who will do coding !!!
k == clen means that the third string is generated already
So, f(0,i,j,k) = f(1,i,j,k) = 1. I think there is no empty string. So, you can forget about this.
So, f(0,i,j,k) = f(1,i,j,k) = 1. I think there is no empty string. So, you can forget about this.
Ami ekhono shopno dekhi...
HomePage
HomePage
WA
I am getting WA, when I try the inputs in the problem's prompt it returns 8 and 18.
When I try those Nazmul posted I get asif_rahman0's output, now when I try Martin Macko's input I get 7714, what output do you get in that case? Anyone has more sample input and outputs I could test?
Edit: Nevermind, my method to get rid of modulo operations was flawed.
Jan: The prompt says that empty string is a subseqence of any string.
When I try those Nazmul posted I get asif_rahman0's output, now when I try Martin Macko's input I get 7714, what output do you get in that case? Anyone has more sample input and outputs I could test?
Edit: Nevermind, my method to get rid of modulo operations was flawed.
Jan: The prompt says that empty string is a subseqence of any string.
Re: recurrence problem
I just said that there is no special case to deal with empty strings. And for Martin Macko's input the output is 896.sclo wrote:The special case is needed to deal with empty strings.
Ami ekhono shopno dekhi...
HomePage
HomePage
Lack of certain input?
If I am not mistaken, for the case:
1
aaa e e
The output should be 1, right?
but my old program returned 0 in that case and it got AC.
So, I am not understanding the problem correctly or the OJ's input should include a case like that.
1
aaa e e
The output should be 1, right?
but my old program returned 0 in that case and it got AC.
So, I am not understanding the problem correctly or the OJ's input should include a case like that.

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
Re: Lack of certain input?
my solution outputs 1.Vexorian wrote:If I am not mistaken, for the case:
1
aaa e e
The output should be 1, right?
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: Lack of certain input?
Yes, the correct answer is 1, as the empty string is also a valid subsequence of the string "aaa".StatujaLeha wrote:my solution outputs 1.Vexorian wrote:If I am not mistaken, for the case:
1
aaa e e
The output should be 1, right?
Is there away to only use 3 parameters instead of 4?
Is there away to only use 3 parameters instead of 4?
I see that the 't' is needed to diferentiate the first string a and the second string b. Is that really needed?
I saw in the problem ranklist, there are people who AC in 2.xxx secs.. it's about twice as fast as the DP talked above and I think because their DP doesn't have the 't' parameter (hence it's twice faster)?
I see that the 't' is needed to diferentiate the first string a and the second string b. Is that really needed?
I saw in the problem ranklist, there are people who AC in 2.xxx secs.. it's about twice as fast as the DP talked above and I think because their DP doesn't have the 't' parameter (hence it's twice faster)?
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
Re: Is there away to only use 3 parameters instead of 4?
Yes, and it's actually possible to reduce further to 2 dimensional array.fh wrote:Is there away to only use 3 parameters instead of 4?
I always think it's normal that two different implementations of exactly the same algorithm differs in a constant factor in run time.fh wrote:I saw in the problem ranklist, there are people who AC in 2.xxx secs.. it's about twice as fast as the DP talked above and I think because their DP doesn't have the 't' parameter (hence it's twice faster)?
I code, therefore I am.
Currently the dp table si 2*60*60*60 (it's 4 parameters: t,x,y,z)
If we can remove 't', then the table is 60*60*60 (absolutely twice faster).
I'm not talking about reducing the "dimension" for example, you can use 1 dimension array of size dp[432000] > it's exactly the same with 4 dimensional array dp[2][60][60][60] but that's not what i meant.
If it does really exist DP with 2 parameters which means the table size is dp[60][60]? I'll be very interested to know the algorithm
If we can remove 't', then the table is 60*60*60 (absolutely twice faster).
I'm not talking about reducing the "dimension" for example, you can use 1 dimension array of size dp[432000] > it's exactly the same with 4 dimensional array dp[2][60][60][60] but that's not what i meant.
If it does really exist DP with 2 parameters which means the table size is dp[60][60]? I'll be very interested to know the algorithm
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
The memory is absolutely reduced by half but the run time is not necesarily absolutely twice faster. The recurence for the dp[2][60][60][60] looks quite simple. (I didn't check whether the recurences in previous posts are correct, assuming they are.) Although I got the recurence for dp[60][60][60], it's a little complicated. Each dp[j][k] is the sum of seven (or less) different dp[p][q][r]. So, it's possible that my solution will be slower than the dp[2][60][60][60] one.fh wrote:Currently the dp table si 2*60*60*60 (it's 4 parameters: t,x,y,z)
If we can remove 't', then the table is 60*60*60 (absolutely twice faster).
fh wrote:I'm not talking about reducing the "dimension" for example, you can use 1 dimension array of size dp[432000] > it's exactly the same with 4 dimensional array dp[2][60][60][60] but that's not what i meant.
Sure, that's not what i meant too.
fh wrote:If it does really exist DP with 2 parameters which means the table size is dp[60][60]? I'll be very interested to know the algorithm
It's dp[60][60], but the run time is still O(n^3).
For example, you know dp[j][k]=dp[i1][j1][k]+dp[i1][j][k1], then you can compute dp as follow:
Code: Select all
int dp[60][60][60];
// some initialization
for(i=1; j<n; i++)
for(j=1; j<n; j++)
for(k=1; k<n; k++)
dp[i][j][k]=dp[i1][j1][k]+dp[i1][j][k1];
output(dp[n1][n1][n1]);
Code: Select all
int dp[60][60];
// some initialization
for(i=1; j<n; i++)
for(j=n1; j>=0; j)
for(k=n1; k>=0; k)
dp[j][k]=dp[j1][k]+dp[j][k1];
output(dp[n1][n1]);
I code, therefore I am.
i see
I see.. it's to save up memory: because DP goes "layer" by layer, we only need to save the latest 2 layers. Yet, the algorithm is still the same... Actually I did save memory for some DP.
I thought you had different algo that only need 2 parameters Thanks for the explanation, Cho.
I thought you had different algo that only need 2 parameters Thanks for the explanation, Cho.
Visit my script to hunt UVA problem here:
http://felixhalim.net/uva/hunting/

Felix Halim
http://felixhalim.net/uva/hunting/

Felix Halim
For those who keep on getting TLE...
I just reallized that my algorithm ( which was also O( 2 * n^3 ) ) kept on getting TLE just beacuse I used C++ strings.
I usually scanf into a buffer and than write something like:
string s = buff;
In my code, I only used the [] operator and it was TLE. Then, instead of C++ strings, I used char[] and got ACC in 7 secs.
I just reallized that my algorithm ( which was also O( 2 * n^3 ) ) kept on getting TLE just beacuse I used C++ strings.
I usually scanf into a buffer and than write something like:
string s = buff;
In my code, I only used the [] operator and it was TLE. Then, instead of C++ strings, I used char[] and got ACC in 7 secs.
A sta da radim