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.
10307 - Killing Aliens in Borg Maze
Moderator: Board moderators
10307 Decreasing Runtime
babor
-
junjieliang
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
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) {
car = System.in.read ();
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;
String s = ReadLn(1000);
numberOfCases = Integer.parseInt(s);
for (int i=0; i<numberOfCases; i++) {
s = ReadLn(1000);
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++) {
String s = ReadLn(1000);
for (int j=0; j<columns; j++) {
borgMaze[j] = s.charAt(j);
}
}
// search for S or A
Point []aliens = new Point[101];
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[0].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[0] = aliens[alienNumber];
queue[0].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;
}
Point []adjList = new Point[noa*noa];
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 r = adjList[begin].r;
int c = adjList[begin].c;
int act = begin++;
if (marks[adjList[act].r] == NU && marks[adjList[act].c] == NU) {
marks[r] = remaining;
marks[c] = remaining;
totalLength += adjList[act].cost;
remaining--;
} else if (marks[adjList[act].r] == NU && marks[c] != NU) {
marks[r] = marks[c];
totalLength += adjList[act].cost;
remaining--;
} else if (marks[adjList[act].c] == NU && marks[r] != NU) {
marks[c] = marks[r];
totalLength += adjList[act].cost;
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;
}
}
totalLength += adjList[act].cost;
remaining--;
}
}
System.out.println(totalLength);
}
public static void main(String args[]) {
try {
Main m = new Main();
m.solve();
} catch (Exception e) {
e.printStackTrace();
}
}
}
[/java]
[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) {
car = System.in.read ();
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;
String s = ReadLn(1000);
numberOfCases = Integer.parseInt(s);
for (int i=0; i<numberOfCases; i++) {
s = ReadLn(1000);
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++) {
String s = ReadLn(1000);
for (int j=0; j<columns; j++) {
borgMaze[j] = s.charAt(j);
}
}
// search for S or A
Point []aliens = new Point[101];
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[0].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[0] = aliens[alienNumber];
queue[0].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;
}
Point []adjList = new Point[noa*noa];
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 r = adjList[begin].r;
int c = adjList[begin].c;
int act = begin++;
if (marks[adjList[act].r] == NU && marks[adjList[act].c] == NU) {
marks[r] = remaining;
marks[c] = remaining;
totalLength += adjList[act].cost;
remaining--;
} else if (marks[adjList[act].r] == NU && marks[c] != NU) {
marks[r] = marks[c];
totalLength += adjList[act].cost;
remaining--;
} else if (marks[adjList[act].c] == NU && marks[r] != NU) {
marks[c] = marks[r];
totalLength += adjList[act].cost;
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;
}
}
totalLength += adjList[act].cost;
remaining--;
}
}
System.out.println(totalLength);
}
public static void main(String args[]) {
try {
Main m = new Main();
m.solve();
} catch (Exception e) {
e.printStackTrace();
}
}
}
[/java]
Really I create my own quicksort and get Accepted. Thank YouSpike 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.
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:
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[2]; //el cost per anar al primer node i per anar al segon
struct arbreMST* next[2];//Pot apuntar a dos nodes mRe: 10307 - Killing Aliens in Borg Maze(+100 hours with this
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: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!!
Code: Select all
1
5 9
###
#A#
# #
# ###
# S#
# ###
# #
#A#
###
Anyone with an AC program can confirm this?
Thanks in advance!
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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
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:I got WA on this problem too and I use MST too
For your sample, CDiMa, anserw should be 10 (according to problem description).
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...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.
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
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)
Born from ashes - restarting counter of problems (800+ solved problems)
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 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.
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.