11081 - Strings

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

[sclo]

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.

[vinay]

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

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

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

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

[Jan]

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.

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

[StatujaLeha]

If I am not mistaken, for the case:
1
aaa e e

The output should be 1, right?

my solution outputs 1.

[Martin Macko]

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

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

[Cho]

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

Yes, and it's actually possible to reduce further to 2 dimensional array.

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.

[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

[Cho]

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.

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.

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]);

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

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