TopCoder Statistics - Problem Statement

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

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
7

{}

{}

-4135182

693843612

1331065359

Returns: 3
4

{}

{}

-6350063

555478864

339587318

Returns: 0
8

{}

{}

3338150

291409219

1357592116

Returns: 4
8

{}

{}

40998420

1310852214

2120352632

Returns: 8
6

{}

{}

-839338

441244497

214879063

Returns: 3
10

{}

{}

53802049

746372427

11148693

Returns: 10
3

{}

{}

-832347

617612117

670188430

Returns: 0
3

{}

{}

-2377959

958328977

493822092

Returns: 0
5

{}

{}

2416905

1615344431

1351164229

Returns: 3
1

{}

{}

270

1600821543

1738095762

Returns: 1
1

{}

{}

0

95711848

599668650

Returns: 1
9

{}

{}

-33785683

1834951580

218334212

Returns: 0
2

{}

{}

0

219955786

1344690875

Returns: 1
2

{}

{}

-178

107200505

1746180042

Returns: 0
6

{}

{}

21942189

1147513626

359420493

Returns: 6
924

{}

{}

-266582955742

1825126330

704277911

Returns: 300
691

{}

{}

-241826597558

1246404244

744725610

Returns: 104
46

{}

{}

935334061

207903134

1881105549

Returns: 40
630

{}

{}

219048529972

1461741662

426595919

Returns: 587
571

{}

{}

-184271210410

395850328

1843826011

Returns: 56
720

{}

{}

-271913338035

1622919816

693843612

Returns: 98
335

{}

{}

45906724793

2003474978

555478864

Returns: 285
404

{}

{}

-79355072157

654626441

275495275

Returns: 67
951

{}

{}

-567344731934

1237198478

1694138671

Returns: 53
546

{}

{}

-167706679205

743963371

1225224201

Returns: 55
52

{}

{}

-1190021467

1187094015

929401006

Returns: 9
630

{}

{}

-159637308945

1907584714

1431586934

Returns: 150
869

{}

{}

-179289117336

1877621548

338774521

Returns: 330
336

{}

{}

-66324044495

259378522

716645608

Returns: 22
364

{}

{}

74029542657

1876344994

2013857582

Returns: 339
28

{}

{}

-180300008

1403844960

57787207

Returns: 10
533

{}

{}

171247094136

1673092160

1874874336

Returns: 514
602

{}

{}

14632367008

473079990

1103819953

Returns: 357
836

{}

{}

36642415315

1344690875

1679663255

Returns: 508
365

{}

{}

-73045467063

1746180042

2003772661

Returns: 42
806

{}

{}

210396603506

1147513626

359420493

Returns: 638
390

{}

{}

42420610834

419890461

49754650

Returns: 296
461

{}

{}

-6778233096

681914937

1969478128

Returns: 247
936

{}

{}

136418476465

316562630

214143959

Returns: 636
662

{}

{}

-173043215433

1688858184

1093818340

Returns: 165
211

{}

{}

5223478382

1414474734

2073678618

Returns: 136
933

{}

{}

315477259634

1977477707

1756919680

Returns: 761
364

{}

{}

67097150148

1232188500

1085428100

Returns: 329
717

{}

{}

120502494662

752419226

1933876879

Returns: 522
842

{}

{}

325823712816

1975998408

438591721

Returns: 744
94164

{}

{}

-5595341821682985

1825126330

704277911

Returns: 3260
90571

{}

{}

-1304392934497912

1246404244

744725610

Returns: 40256
93298

{}

{}

-4064988101318371

207903134

1881105549

Returns: 17532
95572

{}

{}

-1411745746180696

1461741662

426595919

Returns: 42839
98237

{}

{}

460013436307070

395850328

1843826011

Returns: 58958
95242

{}

{}

-254463560714937

1622919816

693843612

Returns: 51816
92051

{}

{}

-2070462593008363

2003474978

555478864

Returns: 34713
96371

{}

{}

-5184264114280586

654626441

275495275

Returns: 10147
98833

{}

{}

4615497853341402

1237198478

1694138671

Returns: 87715
92304

{}

{}

-2596874656050769

743963371

1225224201

Returns: 30250
99234

{}

{}

-3079646796565152

1187094015

929401006

Returns: 31869
92906

{}

{}

-2321461126235303

1907584714

1431586934

Returns: 33176
98221

{}

{}

-3471841306512248

1877621548

338774521

Returns: 27650
95637

{}

{}

2934888680544111

259378522

716645608

Returns: 75457
95339

{}

{}

-426945660612902

1876344994

2013857582

Returns: 50559
93918

{}

{}

2929354407554019

1403844960

57787207

Returns: 74889
91257

{}

{}

-1106436498863462

1673092160

1874874336

Returns: 42432
95478

{}

{}

-5466405947690982

473079990

1103819953

Returns: 6274
94908

{}

{}

5933977753947945

1344690875

1679663255

Returns: 94532
94985

{}

{}

-2836542932965727

1746180042

2003772661

Returns: 30360
94182

{}

{}

5882965105081288

1147513626

359420493

Returns: 94017
90658

{}

{}

5474005443841651

419890461

49754650

Returns: 90600
90982

{}

{}

5491236412958735

681914937

1969478128

Returns: 90786
99590

{}

{}

6585720250341734

316562630

214143959

Returns: 99470
97818

{}

{}

6344058160133058

1688858184

1093818340

Returns: 97647
96599

{}

{}

6210639544865876

1414474734

2073678618

Returns: 96524
99512

{}

{}

6560947431518269

1977477707

1756919680

Returns: 99340
91658

{}

{}

5586316883925584

1232188500

1085428100

Returns: 91623
93096

{}

{}

5741083686462042

752419226

1933876879

Returns: 92901
97830

{}

{}

6358701119654157

1975998408

438591721

Returns: 97732
100000

{}

{}

1553112382177175

1825126330

704277911

Returns: 67665
100000

{}

{}

-6478998068024219

681025033

1246404244

Returns: 1794
100000

{}

{}

1120323594257814

1535843096

65664920

Returns: 64582
100000

{}

{}

239836284821151

597310374

250979947

Returns: 58271
100000

{}

{}

4301036401137393

2135945325

978789474

Returns: 86025
100000

{}

{}

-473318200623169

1843826011

1103824394

Returns: 52977
100000

{}

{}

-3753641675995320

1622919816

693843612

Returns: 26837
100000

{}

{}

-3472926631366581

2017131939

2003474978

Returns: 29229
100000

{}

{}

1172490540228647

58260397

504499333

Returns: 64981
100000

{}

{}

-2431283419977782

1357592116

1809557715

Returns: 37811
100000

{}

{}

-3882642256015877

1310852214

2120352632

Returns: 25716
100000

{}

{}

-3829423936963408

1225224201

441244497

Returns: 26190
100000

{}

{}

-6385393703305548

1187094015

929401006

Returns: 2790
100000

{}

{}

-2287196817208471

1765136548

1907584714

Returns: 38977
100000

{}

{}

3045413283792961

1739170626

1143913283

Returns: 77802
100000

{}

{}

5321143033587252

958328977

493822092

Returns: 92294
100000

{}

{}

2138602633716819

1232264639

1932575612

Returns: 71697
100000

{}

{}

-4594823634203060

2013857582

157653347

Returns: 19488
100000

{}

{}

-1350595300130772

1403844960

57787207

Returns: 46341
100000

{}

{}

2449213530776531

599668650

1673092160

Returns: 73851
100000

{}

{}

-1613111475089445

1834951580

218334212

Returns: 44312
100000

{}

{}

-4218200995280382

1029409612

378895392

Returns: 22864
100000

{}

{}

1070924251706402

473373147

1465927042

Returns: 64242
100000

{}

{}

-4666856967601038

2003772661

29400364

Returns: 18807
100000

{}

{}

-727478627922093

1147513626

359420493

Returns: 51075
100000

{}

{}

3173381269859239

387357160

419890461

Returns: 78702
100000

{}

{}

2759876426729354

1861021903

1866743079

Returns: 75936
100000

{}

{}

1992688431270881

803068873

961330915

Returns: 70676
100000

{}

{}

2737409164525960

130925327

652930003

Returns: 75776
100000

{}

{}

4080845429747753

1093818340

1165890949

Returns: 84627
100000

{}

{}

-2714754007766667

1414474734

2073678618

Returns: 35506
100000

{}

{}

-2868826690148746

26554289

1977477707

Returns: 34232
100000

{}

{}

-3413725382104891

583786023

422119432

Returns: 29715
100000

{}

{}

4648083723684083

412266132

1117694491

Returns: 88180
100000

{}

{}

-1621652335324600

474411772

1660684919

Returns: 44265
100000

{}

{}

-5692160256232915

438591721

1166272033

Returns: 9477
100000

{}

{}

-4520289189022281

599946080

760966351

Returns: 20119
100000

{}

{}

-1163790988601218

365326399

683660210

Returns: 47765
100000

{}

{}

5092690131639731

1261400148

174243083

Returns: 91062
100000

{}

{}

4336515243021581

1852844260

1385772914

Returns: 86230
100000

{}

{}

4907136231542527

1494265486

569201407

Returns: 89826
100000

{}

{}

2923955286264757

1342885026

283344821

Returns: 76999
100000

{}

{}

910967127137401

1741564256

863234009

Returns: 63132
100000

{}

{}

-5867899303825787

1882265288

1949569571

Returns: 7680
100000

{}

{}

-5184030390984648

1468068056

1457003238

Returns: 14227
100000

{}

{}

6014071574402261

1010111853

876941472

Returns: 96371
100000

{}

{}

-989803368376529

669787940

1927956375

Returns: 49103
100000

{}

{}

-3089286196420848

719404016

73341291

Returns: 32413
100000

{}

{}

-5574313470130861

698949945

793333955

Returns: 10554
100000

{}

{}

-5535249141344326

107270851

1529923205

Returns: 10962
100000

{}

{}

-4200316430082343

511831732

139674927

Returns: 23005
100000

{}

{}

1993414765436869

932915306

1282142292

Returns: 70699
100000

{}

{}

-2480987611301995

1892601089

679018827

Returns: 37380
100000

{}

{}

-6614012098695646

1486890942

521533320

Returns: 485
100000

{}

{}

118884839885209

1000884666

1873162814

Returns: 57370
100000

{}

{}

6659986169182234

783038327

15833661

Returns: 99909
100000

{}

{}

6663277009310824

1361123409

819093029

Returns: 99993
100000

{}

{}

6658462698603354

465340137

1359353955

Returns: 99967
100000

{}

{}

6644830821940920

599777009

1551291800

Returns: 99866
100000

{}

{}

6646795560737516

1021062158

2018028379

Returns: 99936
100000

{}

{}

6644571792933974

475692706

634434158

Returns: 99917
100000

{}

{}

6669126817132696

1127593668

722638051

Returns: 99995
100000

{}

{}

6666601638700486

545364653

1841645506

Returns: 99998
100000

{}

{}

6651720111371760

1236016472

2140621107

Returns: 99946
100000

{}

{}

6655682080971938

1327260479

36874038

Returns: 99952
100000

{}

{}

6635978854952229

2144675396

1346074728

Returns: 99872
100000

{}

{}

6665377022705564

870967120

1353523063

Returns: 99959
100000

{}

{}

6657752727083100

722383669

1941895970

Returns: 99942
100000

{}

{}

6638408408961796

513176006

828758017

Returns: 99874
100000

{}

{}

6651625338791668

1212911952

65070697

Returns: 99918
100000

{}

{}

-6660138829236742

1825126330

704277911

Returns: -1
100000

{}

{}

-6667306961727037

1246404244

744725610

Returns: -1
100000

{}

{}

-6661009694867618

207903134

1881105549

Returns: -1
100000

{}

{}

-6663207933092532

1461741662

426595919

Returns: -1
100000

{}

{}

-6659103420646691

395850328

1843826011

Returns: -1
100000

{}

{}

-6668547218887305

1622919816

693843612

Returns: -1
100000

{}

{}

-6660783413628008

2003474978

555478864

Returns: -1
100000

{}

{}

-6671113665399272

654626441

275495275

Returns: -1
100000

{}

{}

-6663554261970045

1237198478

1694138671

Returns: -1
100000

{}

{}

-6673182140473417

743963371

1225224201

Returns: -1
100000

{}

{}

-6666883113733681

1187094015

929401006

Returns: -1
100000

{}

{}

-6663074729057870

1907584714

1431586934

Returns: -1
100000

{}

{}

-6666605803542364

1877621548

338774521

Returns: -1
100000

{}

{}

-6673349860006499

259378522

716645608

Returns: -1
100000

{}

{}

-6666964232403818

1876344994

2013857582

Returns: -1
100000

{}

{}

-6654161144813468

1403844960

57787207

Returns: -1
100000

{}

{}

-6658069641964421

1673092160

1874874336

Returns: -1
100000

{}

{}

-6667419012204080

473079990

1103819953

Returns: -1
100000

{}

{}

-6665207773890284

1344690875

1679663255

Returns: -1
100000

{}

{}

-6668071721543556

1746180042

2003772661

Returns: -1
100

{-614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973, -614973}

{-195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290, -195290}

0

1147513626

359420493

Returns: 100
100

{64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802, 64802}

{-54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345, -54345}

-1

97874988

387357160

Returns: -1
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)
100000

{}

{}

-3829423936963408

1225224201

441244497

Returns: 26190
100000

{ }

{ }

-3829423936963408

1225224201

2147483647

Returns: 26201
100000

{ }

{ }

-1829423936963408

1225224201

441244497

Returns: 42584

Statistics

Problem Statement for "MaxPoints"

Problem Statement

Definition

Notes

Constraints

Examples