## 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.

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.

### 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

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(histogramif (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.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

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!!!!!

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

*I dont understand why compile error in my code, anybody help me plz.*

this is my code: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 = treeint a2 = tree

*[1];*

int a3 = treeint a3 = tree

*[2];*

treetree

*[0] = tree [j] [0];*

treetree

*[1] = tree [j] [1];*

treetree

*[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 (treetree [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{

if (tree

*[1] == tree [i + 1] [1])*

{

do

i++;

while (i <= u && tree{

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 && treedo

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 ();

}

}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 ();

}

}

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

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 minDistance3. 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:

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');
}
```

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://online-judge.uva.es/board/viewtopic.php?t=13656

- Carlos
- 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.