MaxPoints

SRM 772 · 2019-12-10 · by vivek1998299

SRM 772 · 2019-12-10 · by vivek1998299 · Geometry

Show categories

Class Name: MaxPoints

Return Type: int

Method Name: findMaxPoints

Arg Types: (int, vector<int>, vector<int>, long long, int, int)

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

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

4
{}
{}
-5397718
1825126330
704277911
Returns: 0

10
{}
{}
37033690
744725610
1006446954
Returns: 8

9
{}
{}
-14543480
1881105549
258158853
Returns: 3

7
{}
{}
3523883
426595919
2135945325
Returns: 4

6
{}
{}
9068082
1843826011
1103824394
Returns: 4

172)

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.

173)

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

174)

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.

175)

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)

Submissions are judged against all 179 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MaxPoints with a public method int findMaxPoints(int N, vector<int> XG, vector<int> YG, long long K, int seedX, int seedY) · 179 test cases · 2 s / 256 MB per case