929 - Number Maze

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

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Dec 03, 2006 6:07 am

oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...
studying @ ntu csie

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Sun Dec 03, 2006 1:37 pm

SRX wrote:oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...
by the way, you could tell us how :P :P
Miguel Oliveira

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Sun Dec 03, 2006 2:46 pm

mogers wrote:
SRX wrote:oops ........
if you read input with "scanf" , then it use 3 secs to read ,
so those who got tle shoud find a fast input way ...
by the way, you could tell us how :P :P
ok , if your language is C or C++ , then "gets" will help you :P
studying @ ntu csie

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Mon Dec 04, 2006 2:08 am

I didnt try gets because the compiler used in Portugal's constests, doesn't allow gets, we may use fgets ...
I've changed scanf to getchar and saw the diference :o very nice :D

I'm having TLE... unfortunatly i dont have time to debug right now...
I use 10 non STL queues but I'm not sure about their MAX Size (i guess that my problem is the size of the array - defined as 999)

How do you implement Queues ? I use an array. I think that a linked list saves memory but is slower.
Miguel Oliveira

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Dec 04, 2006 7:07 am

Using getchar() (and scanf()) can't reduce the overhead of function call (maximaly it is called 999x999 times).
I think SRX wanted to say like this code (It doesn't matter weither you use gets() or fgets())

Code: Select all

char buf[BUF_SIZE];
char *c;
for (i = 0; i < row; ++i) {
   fgets(buf, sizeof(buf), stdin);
   c = buf;
   for (j = 0; j < col; ++j) {
      while (*c == ' ') ++c;
      maze[i][j] = *c++ - '0';
   }
}
I use 10 non STL queues but I'm not sure about their MAX Size (i guess that my problem is the size of the array - defined as 999)
I think size 999 is too small.
How do you implement Queues ? I use an array. I think that a linked list saves memory but is slower.
I used an array.

(I hope this wouldn't be a spoiler. If it is, tell me. I'll edit my post)
----
Sory for my poor English.

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Mon Dec 04, 2006 2:00 pm

I had

Code: Select all

for (i=0;i<rows;i++) {
     for (j=0;j<cols;j++)
     {
          maze[i][j] = getchar();
          maze[i][j] -= '0';               
          getchar();           /* read   ' ' or '\n'   */
     }
}
Assuming that the input doesn't have more spaces... I forgot about the overhead :oops:

I changed the size and still got tle... i have a bug somewhere. Now I must study for exam :cry:

thank you all
Miguel Oliveira

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Wed Dec 06, 2006 8:02 pm

Finaly I had some time to problem solving :D

I was geting TLE because i forgot the smallest case (maze 1x1).
Meanwhile, my Dijkstra with a heap not STL was accepted in 8.645 secs
With 10 queue's I got accepted in 1.213 secs ... amazing :)
In this way, you don't need to queue distance information.
I couldn't avoid queueing the current distance. I think thats why I have ~twice your memory
It is much faster than using the heap (using heap(not STL) took 3 ~ 4 secs).


Someday, I'll be able to achieve your runtimes Rio... my dijkstra or queue's version take (+/-) twice your time. you're the man :D

thanks again
Miguel Oliveira

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sun Feb 11, 2007 4:28 pm

I still got a lot of WAs, please help me some tests :( thanks

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

Post by abhiramn » Sat Jun 30, 2007 9:43 am

Why is this approach wrong.

Code: Select all

#include<stdio.h>
int maze[1000][1000],cum[1000][1000];
int main()
{
	int i,j,test,m,n;
	scanf("%d",&test);
	++test;
	while(--test)
	{
		scanf("%d%d",&m,&n);
		for(i=0;i<m;++i)
			for(j=0;j<n;scanf("%d",&maze[i][j]),++j);
		cum[0][0]=maze[0][0];
		for(i=1;i<n;cum[0][i]=cum[0][i-1]+maze[0][i],++i);
		for(i=1;i<m;cum[i][0]=cum[i-1][0]+maze[i][0],++i);
		for(i=1;i<m;++i)
			for(j=1;j<n;++j)
				cum[i][j]=(cum[i-1][j]<cum[i][j-1]?cum[i-1][j]:cum[i][j-1])+maze[i][j];
		printf("%d\n",cum[m-1][n-1]);
	}
	return 0;
}

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jun 30, 2007 11:18 am

Consider this case:

Code: Select all

1
4
5
0 9 9 9 9
0 9 0 0 0
0 0 0 9 0
9 9 9 9 0
The answer should be 0, but your codes output 9.
----
Rio

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

@RIO

Post by abhiramn » Sat Jun 30, 2007 1:40 pm

Thanks a ton. Terribly stupid mistake. That code is nonsense.
Abhiram.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sat Jul 07, 2007 5:16 am

I used bfs with heap but i am getting WA.
Please anyone give me some test case.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Sat Jul 07, 2007 10:36 am

are u sure that ur heap is working properly?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sat Jul 14, 2007 3:12 pm

>>ayeshapakhi
Thanks for ur reply. I think my heap is working properly.

anyone please give me some test case.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Sat Jul 14, 2007 4:12 pm

to monish
:roll:
:wink:
:D

Post Reply

Return to “Volume 9 (900-999)”