Page 2 of 3

### recurrence problem

Posted: Sun Sep 03, 2006 7:48 am
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??? ### Re: recurrence problem

Posted: Sun Sep 03, 2006 9:57 am
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??? 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  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
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 ?/ Posted: Sun Sep 03, 2006 1:54 pm
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
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
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
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
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
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
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
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
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 -> it's exactly the same with 4 dimensional array dp but that's not what i meant.

If it does really exist DP with 2 parameters which means the table size is dp? I'll be very interested to know the algorithm Posted: Thu Sep 14, 2006 5:47 am
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 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, 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 one.

fh wrote:I'm not talking about reducing the "dimension" for example, you can use 1 dimension array of size dp -> it's exactly the same with 4 dimensional array dp 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? I'll be very interested to know the algorithm It's dp, 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;
// 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;
// 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
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
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.