Page 1 of 3

10949 - Kids in a Grid

Posted: Sun Oct 30, 2005 2:57 pm
by polone
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?

Posted: Sun Oct 30, 2005 3:02 pm
by Adrian Kuegel
I got Accepted with an O(p*(n-p)) 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.

Posted: Sun Oct 30, 2005 9:40 pm
by little joey
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....

Posted: Mon Oct 31, 2005 12:03 pm
by polone
Hmm...

I used:

Code: Select all


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: 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
}
Is it all right?

Posted: Mon Oct 31, 2005 12:56 pm
by Adrian Kuegel
little joey wrote: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?
On the case you mentioned, my program takes 3 seconds on my computer, so I guess it would be approximately 9 seconds in the online judge.

Posted: Mon Oct 31, 2005 3:26 pm
by little joey
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.

Posted: Tue Nov 01, 2005 12:25 am
by Andrey Mokhov
Hmm... I don't beleive this is the right way to solve the problem... I thought about the O(np) algorithm during contest but... Hope the problem is better and we have to get some information out of the way strings are constructed.

Looking forward to see time of Rujia Liu's solution in the ranklist :)

Posted: Sat Nov 05, 2005 4:41 am
by gush
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.
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. "

But there seems to be lots of matching characters.

Did you solve the problem by combining the two algorithms you've mentioned?

Posted: Sat Nov 05, 2005 4:49 am
by gush
Adrian Kuegel wrote:I got Accepted with an O(p*(n-p)) 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.
Where can I get the paper.

Posted: Sat Nov 05, 2005 6:52 am
by wook
well,
[1] Claus Rick, A New Flexible Algorithm for The Longest Common Subsequence Problem, Nordic Journal of Computing, Vol. 2, No .4, 444-461.

[2] J. W. Hunt, T. G. szymanski : A Fast Algorithm for Computing Longest Common Subsequences, Comm. ACM, Vol. 20, May 1997, 350-353.

[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, 436-469.
I think that algorithms of these papers is available,
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....

Posted: Sat Nov 05, 2005 10:11 am
by little joey
gush wrote:
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.
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. "
Yes.
gush wrote:But there seems to be lots of matching characters.
I agree, but the algorith is fast enough for the data in this problem, it seems.
gush wrote:Did you solve the problem by combining the two algorithms you've mentioned?
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.

Posted: Sun Nov 06, 2005 2:52 am
by gush
little joey wrote:
gush wrote:
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.
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. "
Yes.
gush wrote:But there seems to be lots of matching characters.
I agree, but the algorith is fast enough for the data in this problem, it seems.
gush wrote:Did you solve the problem by combining the two algorithms you've mentioned?
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.
I first store all the matching pairs into a vector. But there are too many pairs and I get MLE.

Posted: Sun Nov 06, 2005 9:45 am
by little joey
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 k-values representing the paths.

Posted: Sun Nov 06, 2005 1:21 pm
by gush
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 k-values representing the paths.
Thanks. I get your idea. :)

Posted: Mon Nov 07, 2005 12:46 am
by Emilio
polone wrote:
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!