## 10307 - Killing Aliens in Borg Maze

Moderator: Board moderators

babor
New poster
Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm
Contact:

### 10307 Decreasing Runtime

Hai, I have got Ac this problem in 8.4 second. But I saw in Ranklist that
some people got it Ac within .01 second. Any idea for decreasing running time . What thype of Algorithm u used. Please give me hints.
babor

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
Well I can't tell you how to get to .01 seconds, but if you use an efficient algorithm you should get AC in around .1 seconds, without much explicit optimisation. Perhaps you could improve your algorithm? ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

### Compile error in 10307 Killing alliens in borg's maze!!!!!!

I have a big problem with judge compile error because I don't know what's wrong. If anybody knows what is the problem. pls Reply. Thx.
[java]
/* @JUDGE_ID: 9072?? 10307 JAVA */
import java.util.Comparator;
import java.util.Arrays;

class Point implements Comparator {
public Point(int r, int c) {
this.r = r; this.c = c;
cost = 0;
}

public Point(int r, int c, int cost) {
this.r = r; this.c = c;
this.cost = cost;
}

public int compare(Object o1, Object o2) {
if (!(o1 instanceof Point)) {
throw new ClassCastException();
}
if (!(o2 instanceof Point)) {
throw new ClassCastException();
}

Point p1 = (Point)o1;
Point p2 = (Point)o2;
if (p1.cost < p2.cost) {
return -1;
} else if (p1.cost > p2.cost) {
return 1;
}

return 0;
}

public boolean equals(Object p) {
if (!(p instanceof Point)) {
return false;
}
Point bod = (Point)p;
if ((bod.r == r) && (bod.c == c) && (bod.cost == cost)) {
return true;
}
return false;
}

public int r;
public int c;
public int cost;
};

class Main {
static String ReadLn (int maxLg) {
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";

try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n'))
break;
lin[lg++] += car;
}
} catch (Exception e) {
return (null);
}

if ((car < 0) && (lg == 0))
return (null);
return (new String (lin, 0, lg));
}

public int MAX = 100000;
public void solve() {
try {
int numberOfCases = 0;
int columns = 0;
int rows = 0;

numberOfCases = Integer.parseInt(s);
for (int i=0; i<numberOfCases; i++) {

int k = s.indexOf(' ');

String as = s.substring(0, k);
columns = Integer.parseInt(as);
as = s.substring(k+1, s.length());
rows = Integer.parseInt(as);
solveCase(columns, rows);
}
} catch (Exception e) {
e.printStackTrace();
}
}

public void solveCase(int columns, int rows) {
char [][]borgMaze = new char[rows][columns];
for (int i=0; i<rows; i++) {
for (int j=0; j<columns; j++) {
borgMaze[j] = s.charAt(j);
}
}

// search for S or A
Point []aliens = new Point;
int noa = 0; // noa = Number Of Aliens
for (int i=0; i<rows; i++) {
for (int j=0; j<columns; j++) {
if ((borgMaze[j] == 'A') || (borgMaze[j] == 'S')) {
aliens[noa++] = new Point(i, j);
}
}
}

int [][]spt = new int[noa][noa];
for (int i=0; i<noa; i++) {
spt = doDFS(borgMaze, aliens, i, noa);
}

doMST(spt);

}

public int[] doDFS(char [][]maze, Point[] aliens, int alienNumber, int noa) {
int rows = maze.length;
int cols = maze.length;

int [][]tmpMaze = new int[rows][cols];
int []paths = new int[noa];
for (int i=0; i<noa; i++) {
if (aliens.equals(aliens[alienNumber])) {
paths = 0;
} else {
paths = MAX;
}
}

for (int i=0; i<rows; i++) {
for (int j=0; j<rows; j++) {
tmpMaze[j] = MAX;
}
}

int begin = 0;
int end = 0;
Point []queue = new Point[MAX];
int minCost = 0;
queue = aliens[alienNumber];
queue.cost = 0;
end++;

tmpMaze[queue[begin].r][queue[begin].c] = 0;

while (end > begin) {
int r = queue[begin].r;
int c = queue[begin].c;
int cost = queue[begin++].cost + 1;

if (maze[r][c] == 'S' || maze[r][c] == 'A') {
Point p = new Point(r, c);
for (int i=0; i<noa; i++) {
if (aliens.equals(p)) {
paths = cost - 1;
}
}
}

if (test(r+1, c, rows, cols) && tmpMaze[r+1][c] > cost && maze[r+1][c] != '#') {
tmpMaze[r+1][c] = cost;
queue[end++] = new Point(r+1, c, cost);
}
if (test(r-1, c, rows, cols) && tmpMaze[r-1][c] > cost && maze[r-1][c] != '#') {
tmpMaze[r-1][c] = cost;
queue[end++] = new Point(r-1, c, cost);
}
if (test(r, c+1, rows, cols) && tmpMaze[r][c+1] > cost && maze[r][c+1] != '#') {
tmpMaze[r][c+1] = cost;
queue[end++] = new Point(r, c+1, cost);
}
if (test(r, c-1, rows, cols) && tmpMaze[r][c-1] > cost && maze[r][c-1] != '#') {
tmpMaze[r][c-1] = cost;
queue[end++] = new Point(r, c-1, cost);
}

}

return paths;
}

public boolean test(int r, int c, int rows, int cols) {
if ((r >= 0 && r < rows) && (c >= 0 && c < cols)) {
return true;
}
return false;
}

public void doMST(int [][]matrix) {
int []marks = new int[matrix.length];
int noa = marks.length;
int NU = -1;

for (int i=0; i<noa; i++) {
marks[i] = NU;
}

int noe = 0;
for (int i=0; i<noa; i++) {
for (int j=0; j<noa; j++) {
if (i != j) {
adjList[noe++] = new Point(i, j, matrix[i][j]);
}
}
}
Arrays.sort(adjList, 0, noe, new Point(0, 0));

int totalLength = 0;
int begin = 0;
int remaining = noa;
while (remaining > 0 && begin < noe) {
int act = begin++;
marks[r] = remaining;
marks[c] = remaining;
remaining--;
} else if (marks[adjList[act].r] == NU && marks[c] != NU) {
marks[r] = marks[c];
remaining--;
} else if (marks[adjList[act].c] == NU && marks[r] != NU) {
marks[c] = marks[r];
remaining--;
} else if (marks[r] != marks[c]) {
int mark = marks[r];
int newMark = marks[c];
for (int i=0; i<noa; i++) {
if (marks[i] == mark) {
marks[i] = newMark;
}
}
remaining--;
}
}
System.out.println(totalLength);
}

public static void main(String args[]) {
try {
Main m = new Main();
m.solve();
} catch (Exception e) {
e.printStackTrace();
}

}
}
[/java]

Spike
New poster
Posts: 29
Joined: Mon Mar 18, 2002 2:00 am
Location: Washington State
Contact:
This is due to poor java support of the UVA judge. java.util.Arrays and java.util.Comparator are not supported by the judge. Pretty much anything not available in Java 1.2 isn't supported, and a good portion of 1.2 isn't supported as well.

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:
Spike wrote:This is due to poor java support of the UVA judge. java.util.Arrays and java.util.Comparator are not supported by the judge. Pretty much anything not available in Java 1.2 isn't supported, and a good portion of 1.2 isn't supported as well.
Really I create my own quicksort and get Accepted. Thank You

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm

### 10307 - Killing Aliens in Borg Maze(+100 hours with this!!!)

I have spent more than 100 hours in this problem, may be it's too much for me but I would like to have it accepted! I can't find why the judge is giving me WA! I don't ask you to understand my code but to find a test case which makes the algorithm fail, because I can't find the error.

I use a spanning tree which scans every 4 adjacent nodes (up, down, left and right). Then I build a minimum-path connection matrix to identify every pair of nodes (i.e. Alien with Alien) with it's minimum path length.

Finally I use Prim's Algorithm to find the MST from this connection matrix and get the minimum cost of the Borg.

I've tried some test cases and the program gives me right answers! but the Judge doesn't, so I would appreciate very very much a test case which makes my program fail! thank you a lot!! and... here is the code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define MAXIM_MAPA 150
#define MAX_NODES 101

typedef struct arbreMST
{
int id;
char valor;	             //A=Alien, S=Start
int cost;			 //el cost per anar al primer node i per anar al segon
struct arbreMST* next;//Pot apuntar a dos nodes m``````

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 10307 - Killing Aliens in Borg Maze(+100 hours with this

danifart wrote:I have spent more than 100 hours in this problem, may be it's too much for me but I would like to have it accepted! I can't find why the judge is giving me WA! I don't ask you to understand my code but to find a test case which makes the algorithm fail, because I can't find the error.

I use a spanning tree which scans every 4 adjacent nodes (up, down, left and right). Then I build a minimum-path connection matrix to identify every pair of nodes (i.e. Alien with Alien) with it's minimum path length.

Finally I use Prim's Algorithm to find the MST from this connection matrix and get the minimum cost of the Borg.

I've tried some test cases and the program gives me right answers! but the Judge doesn't, so I would appreciate very very much a test case which makes my program fail! thank you a lot!!
I'm using an algo similiar to yours and get WA too.I use kruskal's instead of prim's and made several tests and think that I've implemented it right. Anyway I'm not entirely sure what should be the right answer for:

Code: Select all

``````1
5 9
###
#A#
# #
# ###
#  S#
# ###
# #
#A#
###
``````
my prog answers 10 but I feel that the judge would expect 11...
Anyone with an AC program can confirm this?

Ciao!!!

Claudio

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I got WA on this problem too and I use MST too For your sample, CDiMa, anserw should be 10 (according to problem description). If answer should be 11, it means, that Borgs cannot divide into small groups at begin of search, what is of course not consistent with sample input 2. 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)

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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Dominik Michniewski wrote:I got WA on this problem too and I use MST too For your sample, CDiMa, anserw should be 10 (according to problem description).
Well. I wasn't all that sure... the problem description tells that borgs can divide into smaller group at start and at each alien. In my sample input I wasn't sure if the borgs could logically split but share a common path for some steps. I mean, they start walking toghether and their paths physically split at some point later!
Dominik Michniewski wrote:If answer should be 11, it means, that Borgs cannot divide into small groups at begin of search, what is of course not consistent with sample input 2. In sample inputs there are 2 distinct paths towards different groups of aliens. In my sample input the first steps aren't distinct... anyway Larry sorted that out so I'm failing somewhere else...

thanks for the replies!!! Ciao!!!

Claudio

P.S. well, other suggestions of possible errors and sample inputs/outputs are still welcome Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Maybe someone who got Accepted on this problem can post our correct answer for CDiMas input ?

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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Dominik Michniewski wrote:Maybe someone who got Accepted on this problem can post our correct answer for CDiMas input ?

Best regards
DM
That's what Larry did! Both his and my AC solution give 10.

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm
Thank you everybody for your answers. I found my mistake in my code, I misunderstood the problem and made the Borgs split in a maximum of two groups at the start or at an Alien instead of splitting in N groups. I think now that my algorithm is correct (it yields 10 in the CiDMA test case) with one exception. I don't consider that the Borg group is formed by 100 individuals. Does it mean that for every splitted group I have to store the number of individuals which form this group?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You can ignore the size of the group.
Since you need at most n Borg to kill n Aliens, you need at most 100 Borg to kill 100 Aliens, which is the maximum number of Aliens in a maze. What is mentioned in the problem is that there are at least 100 Borg, so you don't have to worry about it. For all practical purposes the groupsize can be considered infinite.

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm
mmmmmm, yeah that's right....but then... Who can break my code??