10949  Kids in a Grid
Moderator: Board moderators
10949  Kids in a Grid
I've thinked hours of this problem..
Are there exist a O(nlogn) LCS algo?
or it can be solved by O(n^2) LCS?
Are there exist a O(nlogn) LCS algo?
or it can be solved by O(n^2) LCS?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I got Accepted with an O(p*(np)) Algorithm, where p is length of LCS. I found this algorithm in a paper with the subject: "A New Flexible Algorithm for the Longest Common Subsequence Problem".
But I think there must exist a better algorithm for this specific problem, maybe you can use the information how the strings are constructed.
But I think there must exist a better algorithm for this specific problem, maybe you can use the information how the strings are constructed.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm, that means that it would time out for high values of p, say comparing a string of 20000 'a's with a string of 10000 "ab"s, am I correct?
I don't have access to the article you mention, but is the algorithm the same as the one mentioned in Skiena's Algorithm Design Manual, par. 8.7.8, under the heading What if there are relatively few sets of matching characters??
I tried the algorithm found here http://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf, but that times out hopelessly....
I don't have access to the article you mention, but is the algorithm the same as the one mentioned in Skiena's Algorithm Design Manual, par. 8.7.8, under the heading What if there are relatively few sets of matching characters??
I tried the algorithm found here http://www.eecs.berkeley.edu/~gene/Papers/np_diff.pdf, but that times out hopelessly....
Hmm...
I used:
and get TLE
this is my input method:
Is it all right?
I used:
Code: Select all
cin>>n1>>x>>y;
x;
y;
if(x<0  y<0  x>=h  y>=w)
while(1);
this is my input method:
Code: Select all
char map[21][21];
cin>>t;
for(tt=1;tt<=t;tt++)
{
cin>>h>>w;
for(i=0;i<h;i++)
cin>>map[i];
cin>>n1>>x>>y;
cin>>s1;
xxxxx
cin>>n2>>x>>y;
cin>>s2;
xxxxx
}

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
OK, I finaly got it using the algorithm mentioned by Skiena.
For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.
So we may safely assume that the judges input doesn't contain such 'horror' cases.
For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.
So we may safely assume that the judges input doesn't contain such 'horror' cases.

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Do you mean this? " What if there are relatively few sets of matching characters?  For strings that do not contain too many copies of the same character, there is a faster algorithm. "little joey wrote:OK, I finaly got it using the algorithm mentioned by Skiena.
For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.
So we may safely assume that the judges input doesn't contain such 'horror' cases.
But there seems to be lots of matching characters.
Did you solve the problem by combining the two algorithms you've mentioned?
Where can I get the paper.Adrian Kuegel wrote:I got Accepted with an O(p*(np)) Algorithm, where p is length of LCS. I found this algorithm in a paper with the subject: "A New Flexible Algorithm for the Longest Common Subsequence Problem".
But I think there must exist a better algorithm for this specific problem, maybe you can use the information how the strings are constructed.
well,
and that some details in [1] are omitted but not omitted in [2] or in [3] .
They are hard to come by.
also I don't have access for portal.acm.org....
I think that algorithms of these papers is available,[1] Claus Rick, A New Flexible Algorithm for The Longest Common Subsequence Problem, Nordic Journal of Computing, Vol. 2, No .4, 444461.
[2] J. W. Hunt, T. G. szymanski : A Fast Algorithm for Computing Longest Common Subsequences, Comm. ACM, Vol. 20, May 1997, 350353.
[3] F. Y. L. Chin, C. K. Poon : A Fast Algorithm For Computing Longest Common Subsequences of Small Alphabet Size, Journal of Information Processing, Vol. 13, No. 4, 1990, 436469.
and that some details in [1] are omitted but not omitted in [2] or in [3] .
They are hard to come by.
also I don't have access for portal.acm.org....
Sorry For My Poor English..

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Yes.gush wrote:Do you mean this? " What if there are relatively few sets of matching characters?  For strings that do not contain too many copies of the same character, there is a faster algorithm. "little joey wrote:OK, I finaly got it using the algorithm mentioned by Skiena.
For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.
So we may safely assume that the judges input doesn't contain such 'horror' cases.
I agree, but the algorith is fast enough for the data in this problem, it seems.gush wrote:But there seems to be lots of matching characters.
No, I only used one algorithm. As you see, my time is slowest in the ranking. I'd like to hear from the problemsetter what the intended algorithm was and if would perform equally well on the type of input I mentioned.gush wrote:Did you solve the problem by combining the two algorithms you've mentioned?
I first store all the matching pairs into a vector. But there are too many pairs and I get MLE.little joey wrote:Yes.gush wrote:Do you mean this? " What if there are relatively few sets of matching characters?  For strings that do not contain too many copies of the same character, there is a faster algorithm. "little joey wrote:OK, I finaly got it using the algorithm mentioned by Skiena.
For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.
So we may safely assume that the judges input doesn't contain such 'horror' cases.I agree, but the algorith is fast enough for the data in this problem, it seems.gush wrote:But there seems to be lots of matching characters.No, I only used one algorithm. As you see, my time is slowest in the ranking. I'd like to hear from the problemsetter what the intended algorithm was and if would perform equally well on the type of input I mentioned.gush wrote:Did you solve the problem by combining the two algorithms you've mentioned?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hi gush,
You don't have to actually store all pairs first before processing them.
If you make sure you generate them in the sorted order (first by increasing x, then increasing y), you can directly 'insert' them while you generate them. Inserting, in the terms of Skiena, meaning maintaining an array of kvalues representing the paths.
You don't have to actually store all pairs first before processing them.
If you make sure you generate them in the sorted order (first by increasing x, then increasing y), you can directly 'insert' them while you generate them. Inserting, in the terms of Skiena, meaning maintaining an array of kvalues representing the paths.
Thanks. I get your idea.little joey wrote:Hi gush,
You don't have to actually store all pairs first before processing them.
If you make sure you generate them in the sorted order (first by increasing x, then increasing y), you can directly 'insert' them while you generate them. Inserting, in the terms of Skiena, meaning maintaining an array of kvalues representing the paths.
polone wrote:
I'm getting the same trouble.
I have tried it with gets() and char by char but always get RE by the same cause assert(x>=0 && y>=0 && x<H && y<W).
Could you say me how is yours parse input, please?
I don't understand what is the reason of my RE by this cause.
Thanks!
Hmm...
I used:
Code:
cin>>n1>>x>>y;
x;
y;
if(x<0  y<0  x>=h  y>=w)
while(1);
and get TLE
this is my input method:
Code:
char map[21][21];
cin>>t;
for(tt=1;tt<=t;tt++)
{
cin>>h>>w;
for(i=0;i<h;i++)
cin>>map;
cin>>n1>>x>>y;
cin>>s1;
xxxxx
cin>>n2>>x>>y;
cin>>s2;
xxxxx
}
Is it all right?
I'm getting the same trouble.
I have tried it with gets() and char by char but always get RE by the same cause assert(x>=0 && y>=0 && x<H && y<W).
Could you say me how is yours parse input, please?
I don't understand what is the reason of my RE by this cause.
Thanks!