TopCoder Statistics - Problem Statement

Problem Statement

NOTE: This problem statement contains subscripts and superscripts which may not display properly for plugin users.

Write a program to generate a list of random 3D points in space, and then compute the distance between the pair of closest points. Also determine how many distinct pairs of points are this exact distance apart.

Generate the random points using the following pseudo-random number generator. Starting with a given seed₀:

    seed_i+1 = (seed_i * 16807) mod (2³¹-1)

The ith random number (starting at i = 1) is given by:

    rand_i = (seed_i mod (2 * range)) - range

The 3D points are triples of 3 successive random numbers:

    (rand₁, rand₂, rand₃)
    (rand₄, rand₅, rand₆)
    (rand₇, rand₈, rand₉)
    (rand₁₀, rand₁₁, rand₁₂)
    etc...

You will be given an initial seed, the range, and N (the number of points). The random numbers produced by the generator will be between -range and range-1, inclusive. Return a int[] with two elements: the first element should be the square of the distance between the pair of closest points, and the second element should be the number of distinct pairs of points that have this same squared distance.

NOTE: Be sure to use 64-bit arithmetic for the multiply and mod in the random-number generator, and for computing squared distances.

Definition

Class:: ClosestPoints
Method:: distance
Parameters:: int, int, int
Returns:: int[]
Method signature:: int[] distance(int N, int range, int seed)
(be sure your method is public)

Notes

Ignore any duplicate points. (See example 1.)
There will be at least 2 unique points.

Constraints

N will be between 2 and 150000, inclusive.
range will be between 1 and 1000000, inclusive.
seed will be between 1 and 1000, inclusive.
The square of the distance of the closest pair of points will be less than 1000000000.

Examples

3

100

1

Returns: { 9163, 1 }

The three points are: (-93, -51, -27), (-42, 30, -28), and (44, -22, 23). The closest pair of points are the first and third, and the square of their distance is 9163. There is 1 pair of points with a squared distance of 9163.
10000

1

7

Returns: { 1, 12 }

With a range of -1 to 0, there are only 8 possible points. Ignoring duplicates, all 8 possible points are present, forming a 2x2x2 cube. The closest pairs of points are 1 unit apart, and there are 12 such pairs.
25

1

12

Returns: { 1, 9 }

This is similar to the previous example, except that only 7 of the 8 possible points exist.
646

64364

464

Returns: { 2774994, 1 }
150000

1000000

30

Returns: { 311985, 1 }
150000

233

31

Returns: { 1, 656 }
126335

6031

702

Returns: { 29, 1 }
126336

6031

702

Returns: { 29, 2 }
150000

999999

101

Returns: { 404609, 1 }
7

1

200

Returns: { 1, 5 }
6

2

201

Returns: { 2, 2 }
438

1000000

303

Returns: { 493492650, 1 }
464

1000000

303

Returns: { 493492650, 1 }
465

1000000

303

Returns: { 140153524, 1 }
15

5

504

Returns: { 5, 2 }
51001

1789

601

Returns: { 6, 1 }
150000

1

700

Returns: { 1, 12 }
150000

2

701

Returns: { 1, 144 }
150000

3

702

Returns: { 1, 540 }
150000

4

703

Returns: { 1, 1344 }
150000

5

704

Returns: { 1, 2700 }
150000

6

705

Returns: { 1, 4752 }
150000

7

706

Returns: { 1, 7644 }
150000

15

714

Returns: { 1, 77711 }
150000

15

715

Returns: { 1, 77721 }
150000

30

730

Returns: { 1, 159309 }
150000

35

735

Returns: { 1, 126970 }
150000

45

745

Returns: { 1, 74784 }
50000

1000000

75

Returns: { 1252249, 1 }
150000

1000000

597

Returns: { 311985, 2 }
150000

1000000

75

Returns: { 311985, 1 }
150000

999999

14

Returns: { 404609, 1 }
150000

1000000

750

Returns: { 704122, 1 }

Statistics

Problem Statement for "ClosestPoints"

Problem Statement

Definition

Notes

Constraints

Examples