152 - Tree's a Crowd

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

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.

SMBfromRU
New poster
Posts: 7
Joined: Wed Sep 11, 2002 9:19 am

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?

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
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
New poster
Posts: 7
Joined: Wed Sep 11, 2002 9:19 am

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

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)
{
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;
int[] histogram = new int;
int row = 0;
double distance;

while ((line = ReadLn(255)) != null) {

if (!line.equals("0 0 0")) {

StringTokenizer st = new StringTokenizer(line);
trees[row] = Integer.parseInt(st.nextToken());
trees[row] = Integer.parseInt(st.nextToken());
trees[row] = 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,trees,trees,trees[j],trees[j],trees[j]);

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
New poster
Posts: 6
Joined: Wed May 25, 2005 10:04 am

152 (8.08.2005)

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

Thank you daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
New poster
Posts: 6
Joined: Wed May 25, 2005 10:04 am

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 leo20
New poster
Posts: 3
Joined: Mon Oct 31, 2005 9:55 pm
Location: Bolivia
Contact:

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  ;
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 ;
int a2 = tree ;
int a3 = tree ;
tree  = tree [j] ;
tree  = tree [j] ;
tree  = tree [j] ;
tree [j]  = a1;
tree [j]  = a2;
tree [j]  = a3;
}

static sort (int l, int u)
{
if (l >= u)
return;
int i = l;
int j = u + 1;
for (;;)
{
if (tree  == tree [i + 1] )
{
if (tree  == tree [i + 1] )
{
do
i++;
while (i <= u && tree  < tree [l] );
do
j--;
while (tree [j]  > tree [l] );
}
else
{
do
i++;
while (i <= u && tree  < tree [l] );
do
j--;
while (tree [j]  > tree [l] );
}
}
else
{
do
i++;
while (i <= u && tree [i]  < tree [l] );
do
j--;
while (tree [j]  > tree [l] );
}
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 ;
int c = 0;
while (!(a = leer ()).equals ("0 0 0"))
{
aux = new StringTokenizer (a);
tree [c]  = Integer.parseInt (aux.nextToken ());
tree [c]  = Integer.parseInt (aux.nextToken ());
tree [c]  = 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]  - tree [i + 1] , tree [i]  - tree [i + 1] , tree [i]  - tree [i + 1] );
if (tree [i]  == tree [i + 1]  && tree [i]  == tree [i + 1]  && tree [i]  == tree [i + 1] )
sw = true;
System.out.println ("DSIT -- > " + dist);
if (dist < 10)
{
if (sw)
if (dist < 1)
vecinos  += 2;
else
if (dist >= 1 && dist < 2)
vecinos  += 2;
else
if (dist >= 2 && dist < 3)
vecinos  += 2;
else
if (dist >= 3 && dist < 4)
vecinos  += 2;
else
if (dist >= 4 && dist < 5)
vecinos  += 2;
else
if (dist >= 5 && dist < 6)
vecinos  += 2;
else
if (dist >= 6 && dist < 7)
vecinos  += 2;
else
if (dist >= 7 && dist < vecinos  += 2;
else
if (dist >= 8 && dist < 9)
vecinos  += 2;
else
vecinos  += 2;
else
if (dist < 1)
vecinos ++;
else
if (dist >= 1 && dist < 2)
vecinos ++;
else
if (dist >= 2 && dist < 3)
vecinos ++;
else
if (dist >= 3 && dist < 4)
vecinos ++;
else
if (dist >= 4 && dist < 5)
vecinos ++;
else
if (dist >= 5 && dist < 6)
vecinos ++;
else
if (dist >= 6 && dist < 7)
vecinos ++;
else
if (dist >= 7 && dist < vecinos ++;
else
if (dist >= 8 && dist < 9)
vecinos ++;
else
vecinos ++;
}
}
mostrar (vecinos, c - 1);
}

public static void main (String args [])
{
Main rafael = new Main ();
rafael.Begin ();
}
}

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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] = Integer.parseInt(aux.nextToken());
tree[c] = Integer.parseInt(aux.nextToken());
tree[c] = Integer.parseInt(aux.nextToken());
if ((tree[c] | tree[c] | tree[c]) == 0)
break;
c++;
}
Btw, you get wrong answer for sample input (in 0.330, which is rather fast for Java submitions)

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

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;
int treeNum = 0;
int result = {0};
double minDistance;

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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am
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;
int treeNum = 0;
int result = {0};
double minDistance;

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
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

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
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am