## 11081 - Strings

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### 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???
If I will myself do hashing, then who will do coding !!!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

### Re: recurrence problem

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.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### Re: recurrence problem

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 ?/
If I will myself do hashing, then who will do coding !!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

### Re: recurrence problem

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.
Ami ekhono shopno dekhi...
HomePage

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

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

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

### Re: Lack of certain input?

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

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

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?

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

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### 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)?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

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.
I code, therefore I am.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:
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
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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 code, therefore I am.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### 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.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

sluga
New poster
Posts: 20
Joined: Sun Jan 22, 2006 10:48 pm
Location: Croatia
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.
A sta da radim