Page 1 of 3
152 - Tree's a Crowd
Posted: Thu Dec 12, 2002 10:00 pm
by PMNOX
Is there any metod faster than O(N^2)?
I think that i can put all trees in table, and give them value
x + y + z, then sort them so I woulnd't have do in average case N * N compations, it should be in best case 20 times lover.
152 - Tree's a Crowd
Posted: Fri Jan 10, 2003 1:07 pm
by SMBfromRU
Please anybody hint what's up with P152!
The problem seems quite easy, if using "brute force" approach, although too slow. I tryed some variants, always getting WA.
There is some unclear things for me:
1. Should I consider last line of input (0 0 0) like an ordinary case to check?
2. May I assume all numbers in input are integer (i. e. Byte)?
3. May I be sure that number of lines in input is below 5000?
4. Some other tricks with input?
Thanx in advance.
Posted: Sun Jan 12, 2003 5:17 pm
by ec3_limz
Hi,
1. The last line of input "0 0 0" should not be considered as a case to check.
2. All coordinates can fit into 32-bit signed integer, with range -2147483648 to 2147483647.
3. There is a maximum of 5000 trees, each with an x, y, and z coordinate.
This might help a little. Do NOT consider cases where the absolute distance between two trees are more than 10. In other words, if you find that the distance between two trees are more than 10, simply ignore it and continue. I don't know why, but not ignoring such cases will cause you to get WA (which was what happened to me).
Brute force is fast enough to get AC. My brute-force program ran for about 7.5 seconds. Well, so long as it gets AC, I'm okay with any program, even if it is very inefficient.
Hope this helps.
Posted: Mon Jan 13, 2003 1:04 pm
by SMBfromRU
Thank you for your reply, ec3_limz!
I finally got AC; my mistake was trivial and stupid (as usual) - too small array for input data ([1..5000] instead of [1..5001]).
Best regards
Help! Problem 152 Tree's a crowd WA!
Posted: Sat Jun 21, 2003 4:26 am
by chunyi81
[java]import java.io.*;
import java.util.*;
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 (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}
public static void main(String[] args) throws IOException {
String line;
int[][] trees = new int[5000][3];
int[] histogram = new int[10];
int row = 0;
double distance;
while ((line = ReadLn(255)) != null) {
if (!line.equals("0 0 0")) {
StringTokenizer st = new StringTokenizer(line);
trees[row][0] = Integer.parseInt(st.nextToken());
trees[row][1] = Integer.parseInt(st.nextToken());
trees[row][2] = Integer.parseInt(st.nextToken());
row++;
}
else break;
}
for (int i = 0;i < row;i++) {
double min = 10.0;
for (int j = 0;j < row;j++) {
if (i != j) {
distance = findDist(trees[0],trees[1],trees[2],trees[j][0],trees[j][1],trees[j][2]);
if (distance < min)
min = distance;
}
}
if (min < 10.0)
histogram[(int)min]++;
}
for (int i = 0;i < histogram.length;i++) {
String s = String.valueOf(histogram);
s = setFieldWidth(s,4);
System.out.print(s);
}
System.out.println();
}
public static double findDist(int x1,int y1,int z1,int x2,int y2,int z2) {
return Math.sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)) + ((z1 - z2) * (z1 - z2)));
}
public static String setFieldWidth(String s,int width) {
while (s.length() < width)
s = s.concat(" ");
StringBuffer sb = new StringBuffer();
for (int i = s.length() - 1;i >= 0;i--)
sb.append(s.charAt(i));
return sb.toString();
}
}[/java]
Hi, I'm a newbie to ACM.
Above is my Java source code for problem 152. I do not understand why the OJ keeps on giving WA for my code because it gives the correct output for the given sample input. Does anyone have any sample test cases for me to test my program? Thanks.
Posted: Thu Aug 21, 2003 11:59 pm
by Larry
Finding the closest neighbor is O( n log n ), since you can find the Voronnoi diagram/Delaunacy Triangulation of the plane in O( n log n), and since it's a planar graph, it takes O( n )...
152 (8.08.2005)
Posted: Mon Aug 08, 2005 10:23 am
by logan
Can anybody send me additional input and output for problem 152?
Thank you
Posted: Fri Aug 12, 2005 3:55 am
by daveon
Hi there,
INPUT:
Code: Select all
20 20 0
20 20 0
20 20 2
20 20 6
20 20 12
20 20 20
20 20 30
20 20 42
20 20 56
20 20 72
20 20 90
0 0 0
OUTPUT:
Hope this is helpful.
My program still get is WA but O.K. for this above input
Posted: Sat Aug 13, 2005 5:21 pm
by logan
Can anybody say me what is the hack or write another input and output?
Thank for any help
Why Compile Error in 152
Posted: Tue May 23, 2006 1:03 am
by leo20
Hi!!!!!
I dont understand why compile error in my code, anybody help me plz.
this is my code:
import java.io.IOException;
import java.util.StringTokenizer;
class Main
{
int tree [] [] = new int [5000] [3];
static String leer ()
{
String lin = "";
char c;
try
{
while (true)
{
c = (char) System.in.read ();
if (c == '\n')
{
break;
}
lin = lin + c;
}
}
catch (IOException e)
{
return null;
}
if (lin.length () == 0)
{
return null;
}
return lin;
}
static void swap (int i, int j)
{
int a1 = tree
[0];
int a2 = tree [1];
int a3 = tree [2];
tree [0] = tree [j] [0];
tree [1] = tree [j] [1];
tree [2] = tree [j] [2];
tree [j] [0] = a1;
tree [j] [1] = a2;
tree [j] [2] = a3;
}
static sort (int l, int u)
{
if (l >= u)
return;
int i = l;
int j = u + 1;
for (;;)
{
if (tree [0] == tree [i + 1] [0])
{
if (tree [1] == tree [i + 1] [1])
{
do
i++;
while (i <= u && tree [2] < tree [l] [2]);
do
j--;
while (tree [j] [2] > tree [l] [2]);
}
else
{
do
i++;
while (i <= u && tree [1] < tree [l] [1]);
do
j--;
while (tree [j] [1] > tree [l] [1]);
}
}
else
{
do
i++;
while (i <= u && tree [i] [0] < tree [l] [0]);
do
j--;
while (tree [j] [0] > tree [l] [0]);
}
if (i > j)
break;
swap (i, j);
}
swap (l, j);
sort (l, j - 1);
sort (j + 1, u);
}
static double rango (double a1, double a2, double a3)
{
double res = Math.sqrt (Math.pow (a1, 2) + Math.pow (a2, 2) + Math.pow (a3, 2));
return res;
}
void mostrar (int v [], int d)
{
String sp = " "; //4 espacios.
for (int i = 0 ; i < d ; i++)
{
System.out.print ("" + sp.substring (0, Integer.toString (v [i]).length ()) + v [i]);
}
}
void Begin ()
{
String a;
StringTokenizer aux;
int vecinos [] = new int [10];
int c = 0;
while (!(a = leer ()).equals ("0 0 0"))
{
aux = new StringTokenizer (a);
tree [c] [0] = Integer.parseInt (aux.nextToken ());
tree [c] [1] = Integer.parseInt (aux.nextToken ());
tree [c] [2] = Integer.parseInt (aux.nextToken ());
c++;
}
sort (0, c - 1);
for (int i = 0 ; i < c - 1 ; i++)
{
boolean sw = false;
double dist = rango (tree [i] [0] - tree [i + 1] [0], tree [i] [1] - tree [i + 1] [1], tree [i] [2] - tree [i + 1] [2]);
if (tree [i] [0] == tree [i + 1] [0] && tree [i] [1] == tree [i + 1] [1] && tree [i] [2] == tree [i + 1] [2])
sw = true;
System.out.println ("DSIT -- > " + dist);
if (dist < 10)
{
if (sw)
if (dist < 1)
vecinos [0] += 2;
else
if (dist >= 1 && dist < 2)
vecinos [1] += 2;
else
if (dist >= 2 && dist < 3)
vecinos [2] += 2;
else
if (dist >= 3 && dist < 4)
vecinos [3] += 2;
else
if (dist >= 4 && dist < 5)
vecinos [4] += 2;
else
if (dist >= 5 && dist < 6)
vecinos [5] += 2;
else
if (dist >= 6 && dist < 7)
vecinos [6] += 2;
else
if (dist >= 7 && dist < 
vecinos [7] += 2;
else
if (dist >= 8 && dist < 9)
vecinos [8] += 2;
else
vecinos [9] += 2;
else
if (dist < 1)
vecinos [0]++;
else
if (dist >= 1 && dist < 2)
vecinos [1]++;
else
if (dist >= 2 && dist < 3)
vecinos [2]++;
else
if (dist >= 3 && dist < 4)
vecinos [3]++;
else
if (dist >= 4 && dist < 5)
vecinos [4]++;
else
if (dist >= 5 && dist < 6)
vecinos [5]++;
else
if (dist >= 6 && dist < 7)
vecinos [6]++;
else
if (dist >= 7 && dist <
vecinos [7]++;
else
if (dist >= 8 && dist < 9)
vecinos [8]++;
else
vecinos [9]++;
}
}
mostrar (vecinos, c - 1);
}
public static void main (String args [])
{
Main rafael = new Main ();
rafael.Begin ();
}
}
Posted: Tue May 23, 2006 2:04 am
by Darko
I wrote originally that class Main should be public, which is wrong (I just noticed mine are not public, I guess something to do with... something, no idea)
Did you even try compiling it?
- cannot reference tree from a static method (because tree is not static)
- sort is missing a return type
Those are two that you would get by just trying to compile it.
First time I saw it, I thought you got CE from UVa judge.
Next time:
1) post this in Java section
2) please use code tags
[EDIT] Ok, here's what is wrong (if you read a few posts in Java section, you would've seen it):
Code: Select all
while(!(a.leer()).equals("0 0 0"))...
UVa compiler doesn't like it. Either break it down, or use something like:
Code: Select all
while (true) {
a = leer();
aux = new StringTokenizer(a);
tree[c][0] = Integer.parseInt(aux.nextToken());
tree[c][1] = Integer.parseInt(aux.nextToken());
tree[c][2] = Integer.parseInt(aux.nextToken());
if ((tree[c][0] | tree[c][1] | tree[c][2]) == 0)
break;
c++;
}
Btw, you get wrong answer for sample input (in 0.330, which is rather fast for Java submitions)
152 WA, please help
Posted: Mon Jan 01, 2007 3:43 pm
by rickyliu
This problem seems simple. However, my brute force solution got WA. As the problem does not say explicitly, I assume the input can be in real numbers. My algorithm is as follows:
1. initialize result[] to 0 and read in all trees
2. for each tree i, find the minimum distance amongst all other trees and store it in minDistance
3. if minDistance < 10, add 1 to the corresponding bin, ie, ++result[(int) minDistance]
4. print out the result array
Did I miss something or misunderstand anything? Would anyone please provide a set of input/output for my testing - I can only find one in the forum and my program got it right. Here is my code:
Code: Select all
#include <cstdio>
#include <cmath>
#include <climits>
using namespace std;
#ifndef DBL_MAX
const double DBL_MAX = 1.7976931348623158e+308;
#endif
struct Point
{
double x, y, z;
};
Point tree[5000];
int treeNum = 0;
int result[10] = {0};
double minDistance[5000];
int main()
{
for (int i = 0; i < 5000; ++i) {
minDistance[i] = DBL_MAX;
}
while (true) {
Point & p = tree[treeNum];
scanf("%lf %lf %lf", &p.x, &p.y, &p.z);
if (p.x == 0 && p.y == 0 && p.z == 0) break;
++treeNum;
}
for (int i = 0; i < treeNum; ++i) {
for (int j = 0; j < treeNum; ++j) {
if (i == j) continue;
double xDist = tree[j].x - tree[i].x;
double yDist = tree[j].y - tree[i].y;
double zDist = tree[j].z - tree[i].z;
double distSquare = xDist * xDist + yDist * yDist + zDist * zDist;
double dist = sqrt(distSquare);
if (dist < minDistance[i]) {
minDistance[i] = dist;
}
}
if (minDistance[i] < 10) {
++result[(int) minDistance[i]];
}
}
for (int i = 0; i < 10; ++i) {
printf("%4d", result[i]);
}
putchar('\n');
}
Posted: Tue Jan 02, 2007 9:51 am
by rickyliu
I got AC but I did not feel happy. I managed to find the input and output of the judge used. I have verified this by just sending the output line and got AC. Then, I verified with my program's output and found no differences. Since my compiler (GCC 3.4.2 mingw-special) changed the variable treeNum to 0 after reading 5,000 input lines (it worked when I added -O2 to optimize the code - weird and possibly compiler's bug), I started to suspect this problem might be caused by the compiler used by the judge.
To verify my claim, I rewrote the above C++ program so that it could be compiled using a C compiler. I submitted this C program and got AC. Then, I submitted the same program but asked the judge to use C++ compiler. I got WA this time!
Could someone please explain to me why the results were different using different compilers? Here is the rewriting code:
Code: Select all
#include <stdio.h>
#include <math.h>
#include <limits.h>
#ifndef DBL_MAX
const double DBL_MAX = 1.7976931348623158e+308;
#endif
struct Point
{
double x, y, z;
};
struct Point tree[5000];
int treeNum = 0;
int result[10] = {0};
double minDistance[5000];
int main()
{
int i, j;
double xDist, yDist, zDist, distSquare, dist;
for (i = 0; i < 5000; ++i) {
minDistance[i] = DBL_MAX;
}
while (1) {
scanf("%lf %lf %lf", &tree[treeNum].x, &tree[treeNum].y, &tree[treeNum].z);
if (tree[treeNum].x == 0 && tree[treeNum].y == 0 && tree[treeNum].z == 0) break;
++treeNum;
}
for (i = 0; i < treeNum; ++i) {
for (j = 0; j < treeNum; ++j) {
if (i == j) continue;
xDist = tree[j].x - tree[i].x;
yDist = tree[j].y - tree[i].y;
zDist = tree[j].z - tree[i].z;
distSquare = xDist * xDist + yDist * yDist + zDist * zDist;
dist = sqrt(distSquare);
if (dist < minDistance[i]) {
minDistance[i] = dist;
}
}
if (minDistance[i] < 10) {
++result[(int) minDistance[i]];
}
}
for (i = 0; i < 10; ++i) {
printf("%4d", result[i]);
}
putchar('\n');
return 0;
}
152 - C++ compiler problem?
Posted: Wed Jan 03, 2007 6:15 am
by rickyliu
I submitted the same program in C and C++. Former got AC but latter got WA. Is it something wrong with the C++ compiler? For details, please read this thread:
http://online-judge.uva.es/board/viewtopic.php?t=13656
Posted: Wed Jan 03, 2007 11:45 am
by Carlos
please, check your inizializing variables, such as:
try it to set it like:
Code: Select all
int result[10] = {0,0,0,0,0,0,0,0,0,0};
Maybe the c++ compiler doesn't initialize things to 0 and, as far as i know, c or c++ are not vectorial languages, so result[10]={0} won't set all values to 0, only the first one (did you compile with -Wall options? that should throw a warning).