152  Tree's a Crowd
Moderator: Board moderators
152  Tree's a Crowd
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.
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
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.
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.
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 32bit 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 bruteforce 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.
1. The last line of input "0 0 0" should not be considered as a case to check.
2. All coordinates can fit into 32bit 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 bruteforce 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.
Help! Problem 152 Tree's a crowd WA!
[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.
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.
152 (8.08.2005)
Can anybody send me additional input and output for problem 152?
Thank you
Thank you
Hi there,
INPUT:
OUTPUT:
Hope this is helpful.
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
Code: Select all
2 0 1 0 1 0 1 0 1 0
My program still get is WA but O.K. for this above input
Can anybody say me what is the hack or write another input and output?
Thank for any help
Thank for any help
Why Compile Error in 152
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 ();
}
}
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 ();
}
}
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):
UVa compiler doesn't like it. Either break it down, or use something like:
Btw, you get wrong answer for sample input (in 0.330, which is rather fast for Java submitions)
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"))...
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++;
}
152 WA, please help
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:
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');
}
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 mingwspecial) 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:
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?
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://onlinejudge.uva.es/board/viewtopic.php?t=13656

 System administrator
 Posts: 1286
 Joined: Sat Oct 13, 2001 2:00 am
 Location: Valladolid, Spain
 Contact:
please, check your inizializing variables, such as:
try it to set it like:
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).
Code: Select all
int result[10] = {0};
Code: Select all
int result[10] = {0,0,0,0,0,0,0,0,0,0};
DON'T PM ME > For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.