10949 - Kids in a Grid

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

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

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

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

[Adrian Kuegel]

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.

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

[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

[gush]

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?

[gush]

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.

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

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

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.

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.

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.

[gush]

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.

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.

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.

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

[gush]

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.

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