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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 14, 2007 5:06 pm

To mmonish, check your code with a table of all zeroes. Post your code if it passes.
Ami ekhono shopno dekhi...
HomePage

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

Post by mmonish » Sat Jul 14, 2007 5:35 pm

I check my code with a table of all zero's. it gives correct output.
Here is my code

Code: Select all

removed after AC.
Last edited by mmonish on Mon Jul 16, 2007 8:40 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 14, 2007 5:47 pm

Try the cases.

Input:

Code: Select all

3
8
17
1 4 2 3 2 2 1 6 8 5 7 6 1 8 9 2 7
9 5 4 3 1 2 3 3 4 1 1 3 8 7 4 2 7
7 9 3 1 9 8 6 5 0 2 8 6 0 2 4 8 6
5 0 9 0 0 6 1 3 8 9 3 4 4 6 0 6 6
1 8 4 9 6 3 7 8 8 2 9 1 3 5 9 8 4
0 7 6 3 6 1 5 4 2 0 9 7 3 7 2 6 0
1 6 5 7 5 4 1 2 0 0 1 4 6 0 7 1 7
7 7 7 3 3 5 9 9 8 1 8 2 6 6 0 3 8
12
17
4 0 6 1 8 9 8 4 1 4 3 9 8 8 0 8 7
7 8 3 8 3 7 1 0 7 3 4 9 6 5 1 0 9
9 6 8 3 4 8 4 9 9 2 5 5 3 3 3 7 4
3 8 0 8 8 0 6 8 1 9 8 9 7 2 2 8 2
8 9 0 7 8 1 5 8 6 1 2 4 2 5 8 6 2
6 5 3 9 2 4 6 1 8 2 1 1 9 7 6 2 9
5 2 0 0 3 9 1 8 1 9 5 3 2 5 2 5 8
6 7 7 2 2 9 4 1 9 6 9 8 2 5 5 4 9
1 2 5 0 8 3 9 3 9 6 7 9 9 7 6 9 3
5 7 6 6 5 8 2 5 4 4 1 6 1 6 3 3 5
5 3 2 8 2 5 3 6 1 8 6 2 1 4 6 2 9
1 5 0 3 6 4 9 2 9 3 4 4 0 5 9 6 3
14
16
2 8 0 7 2 2 5 9 1 0 8 5 0 7 9 0
5 3 4 1 0 4 8 5 9 2 5 4 1 3 9 5
8 2 7 9 6 1 7 7 1 9 0 3 4 1 7 5
3 3 2 4 1 2 9 0 8 7 4 5 6 8 0 7
7 4 3 1 3 6 3 0 1 9 0 4 2 9 3 1
4 8 2 0 5 5 9 3 2 8 7 4 8 1 4 3
5 5 2 6 8 9 2 9 5 9 4 5 0 5 8 8
0 1 3 2 2 2 7 0 3 1 3 3 7 0 9 5
5 8 3 7 8 3 7 9 3 9 1 8 2 8 0 1
8 4 8 6 0 9 3 0 0 8 7 6 3 5 6 5
8 3 9 4 8 3 9 7 6 4 5 8 6 1 5 5
1 9 6 4 5 4 2 5 3 2 6 8 2 6 6 3
9 4 5 6 2 5 3 5 6 6 1 4 4 6 2 6
8 2 5 5 1 0 1 5 1 7 6 0 0 2 4 3
Output:

Code: Select all

59
88
76
Hope these help.
Last edited by Jan on Sat Jul 14, 2007 10:27 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

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

Post by mmonish » Sat Jul 14, 2007 6:48 pm

>> jan
I think the maze numbers from 0 to 9. so is ur testcase is ok or not?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 14, 2007 10:28 pm

Sorry, I haven't read the description again. However, the cases are correct ( hopefully :D ) now.
Ami ekhono shopno dekhi...
HomePage

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

Post by mmonish » Mon Jul 16, 2007 8:38 pm

Now i get AC. problem on my heap implementation.
Thank u all for help.

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

Post by ayeshapakhi » Mon Jul 16, 2007 9:49 pm

:wink:

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Mon Aug 06, 2007 7:34 pm

I got TLE. How i can reduce time. Thanks in advance........

Code: Select all

#include<stdio.h>
const long max = 1000;
long value[max][max],si[max][max],sa[max][max],in,n,m;
long x[max*max],y[max*max];

void que(long h1)  //modify que
{
long h2,t1,t2;
while(h1!=0)
{
h2=(h1-1)/2;

if(value[x[h2]][y[h2]]>value[x[h1]][y[h1]])
{
t1=x[h2];t2=y[h2];
x[h2]=x[h1];y[h2]=y[h1];
x[h1]=t1;y[h1]=t2;
si[x[h1]][y[h1]]=h1;
si[x[h2]][y[h2]]=h2;
h1=h2;
}
else
break;
}

}
void coque()   //delete que
{
	long root,k,va,t1,t2;
in--;
x[0]=x[in];y[0]=y[in];
si[x[0]][y[0]]=0;
root=0;
while(root<in)
{
k=-1;
va=value[x[root]][y[root]];
if(2*root+1<in)
{
if(value[x[2*root+1]][y[2*root+1]]<va)
{va=value[x[2*root+1]][y[2*root+1]];k=2*root+1;}
}

if(2*root+2<in)
{
if(value[x[2*root+2]][y[2*root+2]]<va)
{va=value[x[2*root+2]][y[2*root+2]];k=2*root+2;}
}

if(k!=-1)
{
t1=x[root];t2=y[root];
x[root]=x[k];y[root]=y[k];
x[k]=t1;y[k]=t2;
si[x[root]][y[root]]=root;
si[x[k]][y[k]]=k;
root=k;
}
else
break;
}

}



void main()
{
long i,j,X,Y,cas,cas1;

scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{
scanf("%ld %ld",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%ld",&sa[i][j]);
value[i][j]=2000000000;
si[i][j]=-1;
}
value[0][0]=sa[0][0];
in=0;
if(m>1)
{
value[0][1]=sa[0][0]+sa[0][1];
x[0]=0;y[0]=1;
sa[0][1]=0;
in=1;
}
if(n>1)
{
value[1][0]=sa[0][0]+sa[1][0];
x[in]=1;y[in]=0;
sa[1][0]=in;
in++;
que(in-1);
}
while(in!=0)
{
if(x[0]==n-1&&y[0]==m-1)
break;
X=x[0];Y=y[0];
coque();
if(Y+1<m)
if(value[X][Y+1]>value[X][Y]+sa[X][Y+1])
{
value[X][Y+1]=value[X][Y]+sa[X][Y+1];
if(si[X][Y+1]==-1)
{x[in]=X;y[in]=Y+1;
 si[X][Y+1]=in;
 in++;
que(in-1);
}
else
que(si[X][Y+1]);
}


if(Y-1>=0)
if(value[X][Y-1]>value[X][Y]+sa[X][Y-1])
{
value[X][Y-1]=value[X][Y]+sa[X][Y-1];
if(si[X][Y-1]==-1)
{x[in]=X;y[in]=Y-1;
 si[X][Y-1]=in;
 in++;
que(in-1);
}
else
que(si[X][Y-1]);
}


if(X+1<n)
if(value[X+1][Y]>value[X][Y]+sa[X+1][Y])
{
value[X+1][Y]=value[X][Y]+sa[X+1][Y];
if(si[X+1][Y]==-1)
{x[in]=X+1;y[in]=Y;
 si[X+1][Y]=in;
 in++;
que(in-1);
}
else
que(si[X+1][Y]);
}

if(X-1>=0)
if(value[X-1][Y]>value[X][Y]+sa[X-1][Y])
{
value[X-1][Y]=value[X][Y]+sa[X-1][Y];
if(si[X-1][Y]==-1)
{x[in]=X-1;y[in]=Y;
 si[X-1][Y]=in;
 in++;
que(in-1);
}
else
que(si[X-1][Y]);
}

}

printf("%ld\n",value[n-1][m-1]);

}
}  
SHAKIL

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Aug 21, 2007 7:16 am

I am going nuts with this one. At this moment, my Java code doesn't look much like Java...

Anyway - can someone tell me how big the input file is?

I assumed that it was 16MB. Being that the only way I can get some fast I/O is to read the whole thing in, I really see no room for improvement with my current approach if the input file is larger. I used a "naive" solution with dijkstra's + heap, but I think that should run in time. Well, maybe only in C...

[EDIT] Just to answer my own question - Yes, the input file is at most 16MB. I did the 10 queue thingy and optimized the crap out of poor Java and finally get it to pass. Thanks goes to Rio for the circular queue hint.

RuanZheng
New poster
Posts: 4
Joined: Fri Dec 30, 2005 5:16 pm

Post by RuanZheng » Tue Sep 04, 2007 8:54 pm

I am going to crazy for this problem :evil:
My code passed all the data on this thread, and I could not find whether there is an error with my dijkstra+heap.
More test data, please.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Sep 05, 2007 4:16 am

Post your code.
Ami ekhono shopno dekhi...
HomePage

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Wed Oct 10, 2007 9:51 pm

I think many TLEs become AC on this one in the new server.
My code was at least a factor of 7 faster.
Could be due to increased memory cache size as well.

lazyboy
New poster
Posts: 17
Joined: Tue Jul 08, 2008 3:19 am

Re: 929 - Number Maze

Post by lazyboy » Mon Jan 26, 2009 9:12 pm

I am getting RE error in this problem.
i didn't find the reason... please help me.

here is my code :

Code: Select all

Code removed
Thanks in advance.
Last edited by lazyboy on Sat Feb 07, 2009 9:12 pm, edited 2 times in total.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 929 - Number Maze

Post by newkid » Tue Jan 27, 2009 12:39 pm

I haven't gone through the full code but i found these..

Code: Select all

			if(flag[i-1][j]==0 && i>0)

Code: Select all

         if(flag[i][j-1]==0 && j>0)
The array index bound checking should be done first before accessing the array element.
you should do

Code: Select all

         if(j>0 && flag[i][j-1]==0)
same goes for the other one..
lazyboy wrote:I am getting RE error in this problem.
i didn't find the reason... please help me.
........
hmm..

lazyboy
New poster
Posts: 17
Joined: Tue Jul 08, 2008 3:19 am

Re: 929 - Number Maze

Post by lazyboy » Tue Feb 03, 2009 8:58 pm

Thanks for ur reply.

newkid wrote
"The array index bound checking should be done first before accessing the array element.
you should do"
i think this not the case. i used 'and' operation, and when both the condition returns true then the segment executes.
so this is not standing for RE.

Post Reply

Return to “Volume 9 (900-999)”