MaxPoints | Topcoder Archive

Problem Statement

You are given N (not necessarily distinct) points in the plane and an integer K. The points are numbered from 0 to N-1. The x and y cordinates of the point numbered i are given by X[i] and Y[i] respectively.

In this problem we use the Manhattan metric to measure distances between points. That is, the distance between (x1,y1) and (x2,y2) is abs(x1-x2) + abs(y1-y2).

Let S be a subset of the given points. Then:

Let inside(S) be the sum of all pairwise distances between points in S.
Let outside(S) be the sum of all pairwise distances between the given points that are not in S.
We say that the subset S is valid if inside(S) - outside(S) <= K.

Find and return the largest possible size of a valid subset S. If no valid subset S exists, return -1 instead.

You are given the int N, the int[] XG, the int[] YG, the long K, and the ints seedX and seedY. Use the following pseudocode to generate X and Y.

A[0] = seedX
for i=1 to N-1:
    A[i] = (A[i-1]*1103515245 + 12345) modulo 2147483648

X = XG
for i=size(XG) to N-1:
    X[i] = (A[i] modulo 2000001) - 1000000

B[0] = seedY
for i=1 to N-1:
    B[i] = (B[i-1]*1103515245 + 12345) modulo 2147483648

Y = YG
for i=size(YG) to N-1:
    Y[i] = (B[i] modulo 2000001) -  1000000

Definition

Class:: MaxPoints
Method:: findMaxPoints
Parameters:: int, int[], int[], long, int, int
Returns:: int
Method signature:: int findMaxPoints(int N, int[] XG, int[] YG, long K, int seedX, int seedY)
(be sure your method is public)

Notes

If a set is empty, the sum of pairwise distances between the points it contains is zero. The same is true for a set that contains exactly one point.

Constraints

N will be between 1 and 100,000, inclusive.
Number of elements in XG will be same as YG which will be between 0 and min(N, 100), inclusive.
Each element of XG will be between -1,000,000 and 1,000,000, inclusive.
Each element of YG will be between -1,000,000 and 1,000,000, inclusive.
K will be between -1,000,000,000,000,000,000 and 1,000,000,000,000,000,000, inclusive.
seedX will be between 0 and 2,147,483,647, inclusive.
seedY will be between 0 and 2,147,483,647, inclusive.

Examples

```
3
```
```
{1, 2, 1000}
```
```
{1, 2, 1000}
```
```
2
```
```
1
```
```
1
```
```
Returns: 2
```
The three given points are (1,1), (2,2), and (1000,1000). Consider the subset S that contains the first two points. We have inside(S) - outside(S) = 2, and as 2 <= K, this subset is valid. We can easily verify that the subset that contains all three points is not valid, hence the answer is 2.
```
3
```
```
{1, 1, 1}
```
```
{2, 2, 2}
```
```
0
```
```
1
```
```
1
```
```
Returns: 3
```
This time we are given three identical points, all three at (1,2). If we take the set S that contains all three points, we have inside(S) - outside(S) = 0 - 0 = 0, so this subset is valid (and obviously it's the biggest one).
```
3
```
```
{1, 1, 1}
```
```
{2, 2, 2}
```
```
-1
```
```
1
```
```
1
```
```
Returns: -1
```
Again we are given three identical points, all three at (1,2), but now the threshold for valid subsets is -1. With this threshold the given set of points has no valid subsets.
```
4
```
```
{}
```
```
{}
```
```
-5397718
```
```
1825126330
```
```
704277911
```
```
Returns: 0
```
The empty subset of points is valid, all other subsets are invalid. For the empty set we have inside(empty) - outside(empty) = 0 - 8898153 <= K. The four points you should generate are: (125418, -722441) (-220198, 961139) (535879, -48714) (795069, -439865)

{}

{}

-3829423936963408

1225224201

441244497

Returns: 26190

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.