152 - Tree's a Crowd

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

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

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

[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

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

[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 )...

[logan]

Can anybody send me additional input and output for problem 152?

Thank you

[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:

Code: Select all

   2   0   1   0   1   0   1   0   1   0

Hope this is helpful.

[logan]

Can anybody say me what is the hack or write another input and output?
Thank for any help

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

[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)

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

[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;
}

[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

[Carlos]

please, check your inizializing variables, such as:

Code: Select all

int result[10] = {0}; 

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