## 10949 - Kids in a Grid

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

Moderator: Board moderators

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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....

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

little joey
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.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
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?

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
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.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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....
Sorry For My Poor English..

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
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.

little joey
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 k-values representing the paths.

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
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.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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!