10653 - Bombs! NO they are Mines!!

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

Moderator: Board moderators

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

10653 - Bombs! NO they are Mines!!

Post by neno_uci » Wed May 26, 2004 12:40 am

I had 15+ RTE during the contest and I still don't get it, please try to find my error, or just try to give me a hint. This is my code:

[cpp]
#include <stdio.h>

int f1, c1, f2, c2, fil, col, mat[1000][1000];

void ReadData()
{
int n1, n2, f, c;

for (int i = 0; i <= fil - 1; i++)
for (int j = 0; j <= col - 1; j++)
mat[j] = 0;

scanf("%d", &n1);

for (int i = 1; i <= n1; i++) {

scanf("%d %d", &f, &n2);

for (int j = 1; j <= n2; j++) {

scanf("%d", &c);
mat[f][c] = -1;
}
}

scanf("%d %d", &f1, &c1);
scanf("%d %d", &f2, &c2);
}

void MakeSolu()
{
const int movfil[4] = {-1, 0, 1, 0};
const int movcol[4] = {0, 1, 0, -1};
int ax[2][1000000], ay[2][1000000], canta = 1, cantv, mov = 0, p = 0;
bool fin = false;

ax[0][0] = f1;
ay[0][0] = c1;
mat[f1][c1] = 1;

do {

p++;
cantv = 0;

for (int i = 0; i <= canta - 1; i++)
for (int j = 0; j <= 3; j++) {

int ft = ax[mov] + movfil[j];
int ct = ay[mov] + movcol[j];

if (ft >= 0 && ft < fil && ct >= 0 && ct < col)
if (mat[ft][ct] == 0) {

mat[ft][ct] = p;
ax[mov ^ 1][cantv] = ft;
ay[mov ^ 1][cantv] = ct;
cantv++;

if (ft == f2 && ct == c2)
fin = true;
}
}

mov ^= 1;
canta = cantv;

}
while (canta != 0 && !fin);

printf("%d\n", mat[f2][c2]);
}

int main()
{
scanf("%d %d", &fil, &col);

while (fil || col) {

ReadData();
MakeSolu();
scanf("%d %d", &fil, &col);
}

return 0;
}
[/cpp]

Any help would be appreciated :o

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed May 26, 2004 12:46 am

[c]int ax[2][1000000], ay[2][1000000], canta = 1, cantv, mov = 0, p = 0;[/c]
The judge cannot allocate 16 MB of memory onto the stack, which is probably the reason for your RTE.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Wed May 26, 2004 3:23 am

Thanks a lot UFP2161, that was really my mistake, I did not know that :(

I feel bad since I did not solve the task during the contest because of this stupid error.

I am very pleased with your help, thanx again :wink:

Yandry.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Wed May 26, 2004 4:11 am

I used the following structure for my Point:

typedef struct P {
int x,y;
int z;
};

(where z means its deepness in the search).... then i do a simple BFS...

altough i did get AC, it ran during 3.4 secs.... only cause i use a recycling macro as follows:

#define n() (recC!=0 ? rec[--recC] : new P() );

otherwise it gives MLE.... how did you guys solve it in less time? u usually dont use a struct? just a int[3]?

thanks...

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Wed May 26, 2004 12:54 pm

I just do a simple BFS but the points from where i go left,rigth,up or down i remember in 2 arrays(one for column,and the second for row).And update my arrays on every steps. I got AC during 1.5..sc .
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

don't get it

Post by sohel » Mon May 31, 2004 9:31 am

I used BFS and get it AC in 4.74 seconds...

Shouldn't straight forward BFS pass the time limit or is there any tricks and trade in this problem..

thanks for your help.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 31, 2004 11:10 am

No, I also use straight forward bfs and get AC in 1.4 seconds. So I guess it's all in the implementation details. Does your program terminate the bfs as soon as it knows the answer? That can be a time saver.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

i think so

Post by sohel » Mon May 31, 2004 12:54 pm

yeah,

I terminated the BFS function when the destination is reached..

btw I used STL queue to implement BFS... could that be a reason for the slower time.
:-?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 31, 2004 1:18 pm

Well, that can easily be the case. I don't know how STLs queue is implemented, but if it does memory (de)allocation on every enqueue and dequeue, it will spend a lot of time on that. I use a static array with 1Meg elements to implement the queue, with enqueue/dequeue functions inline.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon May 31, 2004 4:06 pm

I am also using stls queue.... took it out and now AC in 01.773 hehuehuahuea..... incredible... their queue sucks without optimization


from 3.4 -> 1.773

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon May 31, 2004 4:11 pm

Since the judge doesn't use any optimisation flags, using STL containers is noticably slower than "doing it yourself". Otherwise, there shouldn't be that much of a difference.

Terminating when destination is reached rarely gives that kind of speed increase. For this problem, my solution (a straightforward impl using STL queues) was about 5% faster (3.775 s instead of 4.012 s) when I terminated upon reaching destination instead of doing the full bfs.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon May 31, 2004 5:12 pm

Hello Per Austrin,

What about the following map:

1000 1000
0
0 0
0 1

(I forgot the problem description, so forgive me if there is something wrong)....

This is a 1000x1000 map without any mines...... if you do a bfs without stoping it shall go through each and every vertex. While if you skip it when you reach the end (deep=1) you get it done :)

It could have been worse if the map would have been bigger..... altough I am sure that bfs is fast cause it only visits once each vertex (1000x1000 visits)

Guilherme Silveira

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon May 31, 2004 5:22 pm

Yeah, sure, but that's not what typical judge input looks like, which is what I was talking about (though perhaps I was a bit unclear).

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon May 31, 2004 9:09 pm

i lost one point (tle) at south americans contest last year due to a problem like this.... :(

i got what you mean...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

AC

Post by sohel » Tue Jun 01, 2004 8:23 am

Removed STL - and got it AC in 3.36 seconds...
the significant part is that this problem had a time limit of 4 seconds in the real time contest.. it seems that the usage of STL is quite risky.

around 1.5 seconds was reduced by the omission of it - a significant time, I guess.

But, how did some people get AC under 1 second. Is there any different way other than BFS. :-?

Post Reply

Return to “Volume 106 (10600-10699)”