TopCoder Statistics - Problem Statement

Problem Statement

This problem has a non-standard time limit: 5 seconds.

A number x in a list of integers is called lonely if no other number y in the list satisfies |x-y| <= k. That is, each other number differs from a lonely number by more than k. For example, if k=10, the only lonely number in the list {1,30,47,1,20,17} is 47.

A list of integers is called happy if there are no lonely numbers in the list.

A sublist of a list is a contiguous subsequence of the list. For example, {3,4,5} is a sublist of {1,2,3,4,5,6}, but {2,4,6} is not a sublist of {1,2,3,4,5,6}.

You are given a list of integers (in a format that is specified below) and an int m. Find and return the smallest k such that the given list has a happy sublist of length at least m.

The list of integers is provided in the following way: You are given an int len, a int[] init, and ints a, b, c, and d. Use the following pseudocode to generate the list:

input: len, init, a, b, c, d.

arr = array of length len
for i = 0,...,len(init)-1:
   arr[i] = init[i]
for i = len(init),...,len-1:
   arr[i] = (arr[i-1] * a + b * i + c) % d

Be careful of overflow, and also note that these indices are 0-based.

Definition

Class:: FindingFriends
Method:: shortestDistance
Parameters:: int, int[], int, int, int, int, int
Returns:: int
Method signature:: int shortestDistance(int len, int[] init, int a, int b, int c, int d, int m)
(be sure your method is public)

Notes

The judge solution does not depend on any properties of the random number generator.

Constraints

len will be between 2 and 100,000 inclusive.
init will have between 1 and min(len, 2,500) elements, inclusive.
Each element of init will be between 0 and 10^9, inclusive.
d will be between 1 and 10^9, inclusive.
a,b,c will be between 0 and d-1, inclusive.
m will be between 2 and len, inclusive.

Examples

6

{8,1,10,2,9,7}

12

34

56

78

2

Returns: 1

The generated array is {8,1,10,2,9,7} There is no happy sublist if k=0. The sublist {1,10,2,9} is one of the happy sublists if k=1. This sublist is long enough, so k=1 is our answer.
7

{1}

1

0

0

12345678

5

Returns: 0

The generated array is {1,1,1,1,1,1,1}.
12

{0}

1

0

1

6

3

Returns: 0

The generated array is {0,1,2,3,4,5,0,1,2,3,4,5}.
10

{3,4,5}

23

34

35

46

4

Returns: 4

The generated array is {3,4,5,22,33,44,9,20,31,42}.
2

{0,1000000000}

0

0

0

1

2

Returns: 1000000000
5

{1,2,1000,3,4}

9

8

7

10

3

Returns: 996
100000

{967948965}

758179342

788391896

28648718

999999937

3

Returns: 59543

Be careful of overflow when generating the array.
100000

{969769977}

892807425

218993030

985396588

999999937

3

Returns: 56643
100000

{50770694}

278244685

430807311

205127273

999999937

3

Returns: 60981
100000

{494271445}

808264505

421210906

913683270

999999937

3

Returns: 66645
100000

{79730525}

985954476

547473567

758163349

999999937

3

Returns: 57136
100000

{472601822}

717318738

523677784

609914795

999999937

3

Returns: 68659
100000

{53609147}

91954516

985157919

227319910

999999937

3

Returns: 59645
100000

{218195601}

343960584

357061531

678448293

999999937

3

Returns: 59597
100000

{985402525}

171829668

899668650

509072327

999999937

3

Returns: 61280
100000

{239588393}

448726432

634812626

590444692

999999937

3

Returns: 59174
100000

{339740654}

486737833

348893917

262181220

999999937

3

Returns: 54651
100000

{963148541}

612337349

893317784

185645392

999999937

3

Returns: 56170
100000

{63296361}

139799835

22141475

860679592

999999937

3

Returns: 65441
100000

{645621447}

953290116

346062285

192675931

999999937

3

Returns: 65194
100000

{282417202}

975420148

727542962

180159197

999999937

3

Returns: 61042
100000

{298524812}

152195092

876601112

508484387

999999937

2278

Returns: 65638
100000

{583118191}

59358248

142419703

876477571

999999937

4904

Returns: 58789
100000

{574653553}

195026791

795358747

278211391

999999937

319

Returns: 52631
100000

{70758685}

878625974

948311856

358693913

999999937

16553

Returns: 60097
100000

{10636815}

16044718

14493360

2623317

43834136

707

Returns: 2976
100000

{69238668}

20876034

43199167

6765987

52233600

7786

Returns: 2910
100000

{849044171}

472960285

236755000

315473273

506015086

17356

Returns: 27682
100000

{523206372}

29074006

37687889

5858666

50667710

802

Returns: 2815
100000

{85281251}

222246406

33095469

148793106

241330110

247

Returns: 15414
100000

{702487889}

726122607

686492721

703984838

838884143

143

Returns: 48714
1000

{498982001}

41076756

454360594

457336854

604510306

13

Returns: 2131714
1000

{9637259}

634678109

240328182

120507351

773149892

14

Returns: 2662744
1000

{496512161}

227828527

19889254

29266584

348065710

30

Returns: 1253624
100000

{478131626}

39153747

49118685

67082383

154660506

22

Returns: 7011
100000

{565990974}

168649977

191924440

138092623

192724723

100000

Returns: 373269838
100000

{206218711}

161126442

135436263

320673845

855070471

445

Returns: 58276
100000

{481110741}

578689415

677793254

11221003

783835992

8369

Returns: 45627
50

{1000000000}

123

234

345

456

50

Returns: 999999559
100000

{638431622}

55567233

389583441

98764188

585757587

5385

Returns: 35256
100000

{494091742}

603474226

587583787

92076032

634428079

5112

Returns: 39176
100000

{921664373}

649435337

824290586

43068287

855615199

14370

Returns: 48436
100000

{919581414}

8387477

171993791

197026830

199405345

692

Returns: 12562
100000

{898662917}

128903834

92312617

97959835

165956250

2529

Returns: 9420
100000

{139450596}

75427346

762593037

78071146

790599969

61

Returns: 43271
100000

{230013366}

595316221

188095478

161603044

713991299

4

Returns: 38276
100000

{62617747}

279987311

359287575

578914444

819358394

97

Returns: 50382
100000

{306263902}

520457744

571163478

619428556

659046030

6652

Returns: 34590
100000

{89565748}

13586552

10606296

15316629

27840107

2

Returns: 41
100000

{351967584}

19351143

10741680

22941721

50111230

61

Returns: 3010
100000

{973854512}

707819589

439150132

459379470

951961145

16466

Returns: 61834
100000

{973854512}

707819589

439150132

459379470

951961145

83000

Returns: 63488

Statistics

Problem Statement for "FindingFriends"

Problem Statement

Definition

Notes

Constraints

Examples