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

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » 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.
Sorry For My Poor English.. :)

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

Post by polone » Mon Nov 07, 2005 10:19 am

sorry I didn't explain my mistake

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » 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!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » 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.
Sorry For My Poor English.. :)

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » 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 :wink: . I'll try with some algorithm of your recommended papers.

Thanks one more time!
Last edited by Emilio on Fri Nov 11, 2005 8:05 pm, edited 1 time in total.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » 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
Sorry For My Poor English.. :)

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword » Fri Nov 11, 2005 9:48 am

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

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

Post by polone » 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 :wink:

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » 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 :wink:

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » 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 :wink:

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh » 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 :wink:

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » 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. :wink:

I am going to study this new paper. Thank for your help. :D
--
DJWS, a newbie in programming :wink:

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10949 - Kids in a Grid

Post by just_yousef » 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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10949 - Kids in a Grid

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 10949 - Kids in a Grid

Post by just_yousef » 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;
}

Post Reply

Return to “Volume 109 (10900-10999)”