Page 2 of 3

recurrence problem

Posted: Sun Sep 03, 2006 7:48 am
by vinay
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??? :lol:

If yes, then there is another problem , I m very confused with the boundary conditions...
CAn anyone help me on that??? :oops:

Re: recurrence problem

Posted: Sun Sep 03, 2006 9:57 am
by sclo
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??? :lol:

If yes, then there is another problem , I m very confused with the boundary conditions...
CAn anyone help me on that??? :oops:
That's right.
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

Posted: Sun Sep 03, 2006 10:52 am
by vinay
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.
What empty string r u talking about ?/ :oops:

Posted: Sun Sep 03, 2006 1:54 pm
by Jan
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.

WA

Posted: Sun Sep 03, 2006 3:10 pm
by Vexorian
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.

Re: recurrence problem

Posted: Sun Sep 03, 2006 3:19 pm
by Jan
sclo wrote:The special case is needed to deal with empty strings.
I just said that there is no special case to deal with empty strings. And for Martin Macko's input the output is 896.

Lack of certain input?

Posted: Sun Sep 03, 2006 4:01 pm
by Vexorian
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.

Re: Lack of certain input?

Posted: Sun Sep 03, 2006 7:09 pm
by StatujaLeha
Vexorian wrote:If I am not mistaken, for the case:
1
aaa e e

The output should be 1, right?
my solution outputs 1.

Re: Lack of certain input?

Posted: Thu Sep 07, 2006 1:49 pm
by Martin Macko
StatujaLeha wrote:
Vexorian wrote:If I am not mistaken, for the case:
1
aaa e e

The output should be 1, right?
my solution outputs 1.
Yes, the correct answer is 1, as the empty string is also a valid subsequence of the string "aaa".

Is there away to only use 3 parameters instead of 4?

Posted: Wed Sep 13, 2006 5:25 pm
by fh
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)?

Re: Is there away to only use 3 parameters instead of 4?

Posted: Wed Sep 13, 2006 7:10 pm
by Cho
fh wrote: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: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 always think it's normal that two different implementations of exactly the same algorithm differs in a constant factor in run time.

Posted: Thu Sep 14, 2006 3:13 am
by fh
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 :)

Posted: Thu Sep 14, 2006 5:47 am
by Cho
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).
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: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[i-1][j-1][k]+dp[i-1][j][k-1], 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[i-1][j-1][k]+dp[i-1][j][k-1];
output(dp[n-1][n-1][n-1]);
Note that, dp[n-1][n-1][n-1] is all you need and the rest of the table is useless. In this case, this value can also compute with a 2D array and looping the counter carefully like this:

Code: Select all

int dp[60][60];
// some initialization
for(i=1; j<n; i++)
   for(j=n-1; j>=0; j--)
      for(k=n-1; k>=0; k--)
         dp[j][k]=dp[j-1][k]+dp[j][k-1];
output(dp[n-1][n-1]);

i see

Posted: Thu Sep 14, 2006 3:04 pm
by fh
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.

Posted: Thu Sep 21, 2006 11:20 am
by sluga
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.