OJ Board

Posted: **Mon Nov 07, 2005 9:47 am**

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

Two kids NEVER get out of the grid,

if you gets RE with assert(), there might be some errors in input processing.

Notice that
there can be a null-string, i.e. the length is 0,

Code: Select all

2
3 3
ABC
DEF
GHI
0 2 2

0 3 1

3 3
ABC
DEF
GHI
0 1 1

0 1 1

if one uses scanf("%s"), it will omit the empty-string.
also, using gets(), code should be more careful, I think.

Posted: **Mon Nov 07, 2005 10:19 am**

sorry I didn't explain my mistake

Posted: **Tue Nov 08, 2005 1:41 am**

Thanks wook!
But your case is considered in my parse input method.
Sorry but have posted my code.
I'm getting RE and can't find any bug.
Could you say me if my parse input method is wrong?

Code: Select all

struct stmv {int x,y;};
stmv movs[256];
char s1[30000], s2[30000], s[30000], m[30][30];

main ()
{
    int x, y, H, W, len1, len2, i, cases, kase;
    
    movs['E'].x=0, movs['E'].y=1;
    movs['W'].x=0, movs['W'].y=-1;
    movs['N'].x=-1, movs['N'].y=0;
    movs['S'].x=1, movs['S'].y=0;
    
    gets(s);
    sscanf(s,"%d",&cases);
    for (kase=1; kase<=cases; kase++)
    {
        gets(s);
        sscanf(s,"%d%d",&H,&W);
        for (i=0; i<H; i++) gets(m[i]);
        gets(s);
        sscanf(s,"%d%d%d",&len1,&x,&y);
        x--, y--;
        gets(s);
        for (i=0; i<len1; i++)
        {
            // With this small assert I get: Runtime Error  (SIGABRT)
            assert(x>=0 && y>=0); 
            s1[i]=m[x][y];
            x+=movs[s[i]].x;
            y+=movs[s[i]].y;
        }
        s1[len1++]=m[x][y];       
        s1[len1]=0;
        
        gets(s);
        sscanf(s,"%d%d%d",&len2,&x,&y);
        x--, y--;
        gets(s);
        for (i=0; i<len2; i++)
        {
            // With this small assert I get: Runtime Error  (SIGABRT)
            assert(x>=0 && y>=0); 
            s2[i]=m[x][y];
            x+=movs[s[i]].x;
            y+=movs[s[i]].y;
        }
        s2[len2++]=m[x][y];
        s2[len2]=0;
        
        int n=LCS(s1,s2);
        
        cout << "Case " << kase << ": " << len1-n << " " << len2-n << "\n";
    } 
}

Thanks!

Posted: **Tue Nov 08, 2005 10:06 am**

Dear Emilio,

I can't find a special miss in your input processing;

this is input procedure of my program, which got AC :

Code: Select all

	int i, x, y;
	scanf("%d %d", &h, &w);

	for(i=1; i<=h; ++i)
		scanf("%s", ma[i] + 1);

	/* first kid */
	scanf("%d", &n);
	gets(temp);
	sscanf(temp, "%d %d", &x, &y);
	gets(temp + 2);

	ip1[1] = ma[x][y];
	for(i=2; temp[i]; ++i)
	{
		switch(temp[i])
		{
		case 'N': --x; break;
		case 'S': ++x; break;
		case 'W': --y; break;
		case 'E': ++y; break;
		}

		ip1[i] = ma[x][y];
	}

for the second kid, it is same as the first kid, so it was omitted.

ma[][] is a map, ip1[1..N+1] is a string which is made of kid's step.

Hope it works.

Posted: **Tue Nov 08, 2005 7:10 pm**

Thanks another time wook!

I have sent my code with a similar parse input method as yours, and now seem that works fine. Albuit I don't understand why my parse input method don't work.
By other hand I'm getting TLE, but this is another task

. I'll try with some algorithm of your recommended papers.

Thanks one more time!

Posted: **Wed Nov 09, 2005 10:05 am**

yeah, I think that the input file used in judge includes some inappropriate blank lines or blanks

Good Luck..~~

wook

Posted: **Fri Nov 11, 2005 9:48 am**

wa....
can anyone give some input-output?
//bow

Posted: **Sun Nov 13, 2005 5:08 pm**

hmm...

WA shouldn't be the problem

I think you may have to check your algo

if the algo is correct there is hard to exist a data to result in WA

Posted: **Wed Aug 23, 2006 4:04 pm**

Hiya.

I found an useful link when googling. Right here:
http://cs.haifa.ac.il/LANDAU/courses/Seminar/Lect3.ppt
Simple and fast linear space computation of Longest common subsequences, Claus Rick, 1999

I have a question. Page 33 says:
Finding the dominant matches each contour: O(min(m, (n-p))
I wonder how to implement it?

--
DJWS, a newbie in programming

Posted: **Mon Aug 28, 2006 6:52 am**

No one reply.

However it's a hard problem. I just have seen 20 people who solve.

If the reference posted above is not proper to solve this problem, please correct me. I just think the time complexity told by that reference is similar to the papar mentioned by Adrian Kuegel. And one advantage, the reference is so graphy. (filled with colorful graph

)

I still do not know how to calculate dominant matches in good reasonable time like O(min(m, (n-p)). I will keep trying to implement it since I have time.
--
DJWS, a newbie in programming

Posted: **Mon Aug 28, 2006 10:45 am**

The min(m,n-p) bound comes from the fact that there are most min(m,n-p) dominant matches per contour.

Unfortunately, most papers I have found don't mention how to get min(m,n-p) time per contour - they just state it as fact. (Getting O(m) is really easy, though). And I don't know where you can find Rick's paper online. I have full access to portal.acm.org (through school) and I don't think its there (its only on citations).

I used the algorithm mentioned in this paper:

http://www.stringology.org/event/1999/psc99p4_ps.gz

It has the same worst-case bound as Rick's algorithm, but calculates "all contours" at the same time, instead of calculating contours one at a time.

It's far less colourful and easy to read than the presentation, though

Posted: **Mon Aug 28, 2006 4:43 pm**

chrismoh wrote:Unfortunately, most papers I have found don't mention how to get min(m,n-p) time per contour - they just state it as fact. (Getting O(m) is really easy, though).

I agree you. Maybe there is a way to satisfy that condition, but having no idea about it now. Keep discussing anyway.

chrismoh wrote:And I don't know where you can find Rick's paper online. I have full access to portal.acm.org (through school) and I don't think its there (its only on citations).

In fact I have no Rick's paper though I surf hard. It seems papers are unreachable via Internet. I will seek the journal if necessary. And if I find anything in addition, I'd like to post here.

I am going to study this new paper. Thank for your help.

--
DJWS, a newbie in programming

Posted: **Fri Aug 01, 2014 4:22 pm**

How to avoid RE in this problem ??

Code: Select all

#include<bits/stdc++.h>
using namespace std;

char grid[22][22], s1[20002], s2[20002];
int t, n, m, k, x, y, l1, l2, cas = 1, mem[20001][20001];

int solve() {
	for (int i = 0; i <= l1; ++i) {
		for (int j = 0; j <= l2; ++j) {
			if (!i || !j)
				mem[i][j] = 0;
			else {
				if (s1[i - 1] == s2[j - 1])
					mem[i][j] = mem[i - 1][j - 1] + 1;
				else
					mem[i][j] = max(mem[i][j - 1], mem[i - 1][j]);
			}
		}
	}
	return mem[l1][l2];
}
int main(int argc, char **argv) {
	//freopen("a.in", "r", stdin);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; ++i)
			scanf(" %s", grid[i]);
		scanf("%d%d%d\n", &k, &x, &y);
		l1 = k;
		--x, --y;
		char c;
		s1[0] = grid[x][y];
		for (int i = 1; i <= k; ++i) {
			c = getchar();
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s1[i] = grid[x][y];
		}
		getchar();
		scanf("%d%d%d\n", &k, &x, &y);
		l2 = k;
		--x, --y;
		s2[0] = grid[x][y];
		for (int i = 1; i <= k; ++i) {
			c = getchar();
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s2[i] = grid[x][y];
		}
		l1++, l2++;
		int ln = solve();
		printf("Case %d: %d %d\n", cas++, l1 - ln, l2 - ln);
	}
	return 0;
}

Posted: **Fri Aug 01, 2014 11:24 pm**

I changed your input parsing and your code got TLE.

Instead of using a single getchar(), try:
while(getchar() != '\n');

Also read the grid one char at a time instead of as a string.

Posted: **Sat Aug 02, 2014 2:58 am**

Im sorry but is I still don't get the idea, i changed my code to this:

Code: Select all

#include<bits/stdc++.h>
using namespace std;

char grid[22][22], s1[20002], s2[20002];
int t, n, m, k, x, y, l1, l2, cas = 1, mem[20001][20001];

int solve() {
	for (int i = 0; i <= l1; ++i) {
		for (int j = 0; j <= l2; ++j) {
			if (!i || !j)
				mem[i][j] = 0;
			else {
				if (s1[i - 1] == s2[j - 1])
					mem[i][j] = mem[i - 1][j - 1] + 1;
				else
					mem[i][j] = max(mem[i][j - 1], mem[i - 1][j]);
			}
		}
	}
	return mem[l1][l2];
}
int main(int argc, char **argv) {
//	freopen("a.in", "r", stdin);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d\n", &n, &m);
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				scanf(" %c", &grid[i][j]);
		scanf("%d%d%d\n", &k, &x, &y);
		l1 = k;
		--x, --y;
		char c;
		s1[0] = grid[x][y];
		c = getchar();
		int i =1;
		while(c!='\n'){

			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s1[i] = grid[x][y];
			c = getchar();
		}
		getchar();
		scanf("%d%d%d\n", &k, &x, &y);
		l2 = k;
		--x, --y;
		s2[0] = grid[x][y];
		i=1;
		c = getchar();
		while(c!='\n'&& c!=EOF){
			if (c == 'N')
				x -= 1;
			else if (c == 'S')
				x += 1;
			else if (c == 'W')
				y -= 1;
			else
				y += 1;
			s2[i] = grid[x][y];
			c = getchar();
		}
		l1++, l2++;
		int ln = solve();
		printf("Case %d: %d %d\n", cas++, l1 - ln, l2 - ln);
	}
	return 0;
}

OJ Board

10949 - Kids in a Grid

Re: 10949 - Kids in a Grid

Re: 10949 - Kids in a Grid

Re: 10949 - Kids in a Grid