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

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

recurrence problem

Post by vinay » 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??? :lol:

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

Post by sclo » 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??? :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.

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

Re: recurrence problem

Post by vinay » 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 ?/ :oops:
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:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

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

WA

Post by Vexorian » 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.

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

Re: recurrence problem

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

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

Lack of certain input?

Post by Vexorian » 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.

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

Re: Lack of certain input?

Post by StatujaLeha » 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.

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

Post by Martin Macko » 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".

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

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

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

Post by Cho » 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.
I code, therefore I am.

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

Post by fh » 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[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

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

Post by Cho » 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[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.

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

i see

Post by fh » 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.
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

Post by sluga » 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.
A sta da radim

Post Reply

Return to “Volume 110 (11000-11099)”