Page 2 of 7
Posted: Sun Dec 03, 2006 6:07 am
by SRX
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 ...
Posted: Sun Dec 03, 2006 1:37 pm
by mogers
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
Posted: Sun Dec 03, 2006 2:46 pm
by SRX
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
ok , if your language is C or C++ , then "gets" will help you
Posted: Mon Dec 04, 2006 2:08 am
by mogers
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
very nice
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.
Posted: Mon Dec 04, 2006 7:07 am
by rio
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.
Posted: Mon Dec 04, 2006 2:00 pm
by mogers
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
I changed the size and still got tle... i have a bug somewhere. Now I must study for exam
thank you all
Posted: Wed Dec 06, 2006 8:02 pm
by mogers
Finaly I had some time to problem solving
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
thanks again
Posted: Sun Feb 11, 2007 4:28 pm
by FAQ
I still got a lot of WAs, please help me some tests
thanks
Posted: Sat Jun 30, 2007 9:43 am
by abhiramn
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;
}
Posted: Sat Jun 30, 2007 11:18 am
by rio
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
@RIO
Posted: Sat Jun 30, 2007 1:40 pm
by abhiramn
Thanks a ton. Terribly stupid mistake. That code is nonsense.
Abhiram.
Posted: Sat Jul 07, 2007 5:16 am
by mmonish
I used bfs with heap but i am getting WA.
Please anyone give me some test case.
Posted: Sat Jul 07, 2007 10:36 am
by ayeshapakhi
are u sure that ur heap is working properly?
Posted: Sat Jul 14, 2007 3:12 pm
by mmonish
>>ayeshapakhi
Thanks for ur reply. I think my heap is working properly.
anyone please give me some test case.
Posted: Sat Jul 14, 2007 4:12 pm
by ayeshapakhi
