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

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

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

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 [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 ?/

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.