10307 - Killing Aliens in Borg Maze

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

Moderator: Board moderators

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

10307 - Killing Aliens in Borg Maze

Post by Even » Fri Sep 06, 2002 10:22 am

there are 1 S and at most 100 A

I find all pairs distance( include S and A )

and use Prim to find MST, minimum cost

in my method...S and A are treat as the same.

but WA..

is there any tricky??

or I misunderstand something ??

please help ~~ thank you :)

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Sorry

Post by Even » Fri Sep 06, 2002 10:28 am

stupid as me...

I find my mistake...

for there are 1 S and 100 A... there should be total 101 points

but my array size has only 100....so WA /.\

but... why WA not Rutime Error?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by cyfra » Tue Sep 10, 2002 8:42 am

Hi!

This is not the first time when program should gave RE and it gives WA.

When I m writing a program in Pascal and I turn off Range checking then it sometimes happen that if I use array[1..100] and I want to write something to [101] place it writes it there !! But there can be other varaible and the whole program whill produce Wrong Answer...

I think that programs should be tested with Range checking but on the other hand it means that they will be working a little bit slower...

And I think that's all...

Good Luck :wink:

PS.
Did you write this program in C or in Pascal ??

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

10307 Killing Aliens in Borg Maze

Post by ahanys » Tue Mar 25, 2003 2:07 pm

I have curently wrong answer and on the test data I get the correct output. May somebody give some INPUT/OUTPUT or look at the code what's wrong on it.


Thanks in advance ahanys.
[cpp]
/* @JUDGE_ID: 9072XC 10307 C++ */
#include <stdio.h>
#include <stdlib.h>

const int MAX=100;
char p[MAX+1][MAX+1];
int map[MAX+1][MAX+1];
int used[MAX+1][MAX+1];
int m[101][101];

int cena=0;


struct point {
int x;
int y;
int val;
};

int cmp(const void *a, const void *b) {
point c = *((point *)a);
point d = *((point *)b);
if (c.val > d.val) {
return 1;
} else if (c.val < d.val) {
return -1;
} else {
return 0;
}
}




point body[101];
point fronta[(MAX+7) * (MAX+7)];
int velikost;

int main() {
int n;
scanf("%i", &n);
for (int a=0; a<n; a++) {
int x,y;
scanf("%i %i\n", &x, &y);
for (int i=0; i<y; i++) {
gets(p);
}

int uzel = 0;
for (int c=0; c<y; c++) {
for (int d=0; d<x; d++) {
if (p[c][d] == 'A' || p[c][d] == 'S') {
if (p[c][d] == 'S') p[c][d]='A';
body[uzel].x = d;
body[uzel].y = c;
body[uzel].val = 0;
map[c][d] = uzel++;
} else {
map[c][d] = -1;
}
}
}

for (int r=0; r<uzel; r++) {// pro kazdy uzel
fronta[0] = body[r];
velikost = 1;
int akt = 0;
for (int e=0; e<y; e++)
for (int f=0; f<x; f++) used[e][f]=0;


while (velikost > akt) {
point prvni = fronta[akt++];
if (p[prvni.y][prvni.x] == 'A' && !used[prvni.y][prvni.x]) {
m[r][map[prvni.y][prvni.x]] = prvni.val;
}
used[prvni.y][prvni.x] = 1;
prvni.val++;
if (p[prvni.y][prvni.x+1] != '#') {
if (!used[prvni.y][prvni.x+1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x++;
}

}
if (p[prvni.y][prvni.x-1] != '#') {
if (!used[prvni.y][prvni.x-1]) {
fronta[velikost++] = prvni;
fronta[velikost-1].x--;
}
}
if (p[prvni.y-1][prvni.x] != '#') {
if (!used[prvni.y-1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y--;
}
}
if (p[prvni.y+1][prvni.x] != '#') {
if (!used[prvni.y+1][prvni.x]) {
fronta[velikost++] = prvni;
fronta[velikost-1].y++;
}
}
}
}

point seznam[(MAX+7) * (MAX+7)];
int pocet=0;
for (int t=0; t<uzel; t++) {
for (int u=0; u<uzel; u++) {
if (t != u && m[t] != 0) {
point p1;
p1.x = t;
p1.y = u;
p1.val = m[t];
seznam[pocet++] = p1;
}
}
}
qsort(seznam, pocet, sizeof(point), cmp);



int kused[MAX+1];

int zbyva=uzel-1;
int komponenta=1;
for (int g=0; g<uzel; g++) kused[g]=0;

for (int q=0; q<pocet; q++) {
int pridej = 0;
if (zbyva == 0) break;
if (!kused[seznam[q].x]) {
pridej = 1;
}
if (!kused[seznam[q].y]) {
pridej += 2;
}
if (kused[seznam[q].y] != 0 && kused[seznam[q].x] != 0) {
if (kused[seznam[q].y] != kused[seznam[q].x]) {
pridej = 4;
}
}

if (pridej == 1) {
kused[seznam[q].x] = kused[seznam[q].y];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 2) {
kused[seznam[q].y] = kused[seznam[q].x];
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 3) {
kused[seznam[q].x] = komponenta;
kused[seznam[q].y] = komponenta++;
cena+=seznam[q].val;
zbyva--;
} else if (pridej == 4) {
if (kused[seznam[q].y] > kused[seznam[q].x]) {
int mensi = kused[seznam[q].x];
int vetsi = kused[seznam[q].y];
for (int za=0; za<uzel; za++) {
if (kused[za]==vetsi) {
kused[za] = mensi;
}
}
} else {
int vetsi = kused[seznam[q].x];
int mensi = kused[seznam[q].y];
for (int z=0; z<uzel; z++) {
if (kused[z]==vetsi) {
kused[z] = mensi;
}
}
}
cena+=seznam[q].val;
zbyva--;
}
}

printf("%i\n", cena);
}

return 0;
}

[/cpp][/cpp]

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10307

Post by hank » Mon Jul 21, 2003 4:05 pm

I cannot understand why the answer of the following input is "11"?

Code: Select all

#####  
#AAA###
#    A#
# S ###
#     #
#AAA###
##### 

Code: Select all

and why it said , "That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3. " ?
please help me understand this "sample input"!
Thanks a lot! :D

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

Post by Per » Mon Jul 21, 2003 5:42 pm

I'm not sure what they mean by the text, but I'll show why the output is 11.

Let the borgs split once in the beginning, one group going upwards, one group going downwards, so we get (where B denotes a borg group):

Code: Select all

##### 
#ABA###
#    A#
#   ###
#     #
#ABA###
##### 
having walked a total of four steps (both groups take two steps). The groups then split again, each group taking one step left/right, and we get:

Code: Select all

##### 
#B B###
#    A#
#   ###
#     #
#B B###
##### 
having walked a total of eight steps (each of the four groups take one step). Finally, the group in the upper right walks the three steps to the last alien, and the total is now 11 steps.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jul 24, 2003 8:28 am

But what about this (first sample) case ? Second is easy. But hw can I get 8 in this case ? Could anyone explain me ?

Code: Select all

6 5
##### 
#A#A##
# # A#
#S  ##
##### 
I always get 7!!!!!

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

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

Post by Per » Thu Jul 24, 2003 9:07 am

The borgs can only split at aliens, not in arbitrary cells!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jul 24, 2003 1:30 pm

Off course - I miss this :)
Thanks

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Jul 24, 2003 4:34 pm

You can also split in the beginning, of course

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sat Jul 26, 2003 9:13 am

I try to solve this problem using MST , but I got WA. Could anyone help me and tell me some special cases ??

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

faster algorithm

Post by Faizur » Sat Jul 26, 2003 10:59 am

I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Re: faster algorithm

Post by hank » Sat Jul 26, 2003 3:15 pm

Faizur wrote:I use bfs to get the distance btw them.and then i construct kruskal mst with them.But i recieved time limit exceed. I get accepted with my kruskal implementation in other mst problems.Is there any other faster algorithm to find the shortest distance in a maze.Help me...
I think Prim algorithm is better than kruskal in this problem.
And it it fast!
You don't have to get all the distance between them.
you just get the distance if needed.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Jul 28, 2003 4:09 pm

I use BFS to calculate the distance between all nodes, then I use Prim MST.. and my solution is ranked ~66th, so it isn't so bad...

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Tue Jul 29, 2003 8:59 am

Thanks for the help. But i dont know which one will be more efficient in which case. Is there any documents or resources.Pls send me some hints

Post Reply

Return to “Volume 103 (10300-10399)”