TopCoder Statistics - Problem Statement

Problem Statement

A high jumper is practicing for the upcoming competition. She makes a sequence of N jumps. We will number the jumps from 0 to N-1. The height of jump i is H[i]. Jump i is a success if H[i] > threshold, and it is a failure otherwise.

You are given ints S and F. Find the longest contiguous segment of her practice such that within the segment the ratio of successes to failures is exactly S:F.

Find and return {lo, hi} such that H[lo:hi] is the optimal segment. (See Notes if you aren't familiar with the H[lo:hi] notation.)

If there are multiple optimal segments, minimize lo.

In order to keep the input size small, the sequence H is pseudorandom. Follow the pseudocode given below to generate it.


H[0] = (seed * 1103515245 + 12345) modulo 2^31
for i = 1 to N-1:
    H[i] = (H[i-1] * 1103515245 + 12345) modulo 2^31

Definition

Class:: ExactRate
Method:: getLongest
Parameters:: int, int, int, int, int
Returns:: int[]
Method signature:: int[] getLongest(int N, int seed, int threshold, int S, int F)
(be sure your method is public)

Notes

You should return a int[] with two elements: element 0 is lo, element 1 is hi. These values must satisfy 0 <= lo <= hi <= N.
Jump i belongs into the segment H[lo:hi] if and only if lo <= i < hi. Note that jump number hi does not belong into this segment.
The reference solution does not depend on the input being pseudorandom.

Constraints

N will be between 1 and 500,000, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.
threshold will be between 0 and 2^31 - 1, inclusive.
S will be between 1 and N, inclusive.
F will be between 1 and N, inclusive.

Examples

12

47

1012345678

1

2

Returns: {0, 6 }

Sequence of jump heights: H = { 325621308, 263614405, 1041878298, 160854091, 1346820648, 663962433, 1031250150, 1993983527, 507736276, 118477437, 1569514866, 722640323 }. Jumps 2, 4, 6, 7 and 10 are successes. The other seven jumps are failures. The longest segment in which there are twice as many failures as successes consists of the first six jumps (0,1,2,3,4,5).
12

47

1012345678

2

1

Returns: {2, 8 }

Same sequence of jumps. Here the longest good segment contains jumps 2,3,4,5,6,7. Out of those, four are successes and two are failures.
12

47

1012345678

7

11

Returns: {0, 0 }

Whenever there is no non-empty segment with the desired ratio, return {0, 0}. This is a description of an empty segment, and among all such descriptions it has the smallest possible value lo.
500000

47

1012345678

1

1

Returns: {93575, 96685 }
500000

42

1073741824

1

1

Returns: {4814, 258832 }
500000

4242

123456

1

20

Returns: {0, 0 }
492604

1603453448

941915907

67957

52748

Returns: {7635, 128340 }
497762

914592025

798256433

805

477

Returns: {257, 495109 }
496209

55701192

1597853385

107401

313040

Returns: {13167, 493671 }
494848

1211162320

468684030

39104

10927

Returns: {5574, 455853 }
499486

904348621

1226516247

53549

72001

Returns: {339776, 465326 }
497485

1022462488

956372836

68179

54405

Returns: {70939, 193523 }
498637

1516447469

131788170

103639

6762

Returns: {11381, 342584 }
493509

1232685585

2055120873

4205

93670

Returns: {3098, 474248 }
498334

748865583

1724399624

13564

54519

Returns: {52557, 120640 }
493870

1850252337

648381050

100529

43293

Returns: {3123, 146945 }
493066

1954161971

1666794907

52264

180424

Returns: {56921, 435039 }
497057

426846078

2068705486

3434

90149

Returns: {109700, 484032 }
498169

868410822

1865002685

23228

152099

Returns: {125263, 475917 }
497716

722817743

1928083098

16681

144616

Returns: {193380, 354677 }
499728

431290411

1004784518

111740

99100

Returns: {27588, 312222 }
495149

142862177

1708430477

89

354

Returns: {378983, 494163 }
490334

1729768569

977278281

134040

112321

Returns: {2240, 248601 }
490369

294444071

34915808

171477

2857

Returns: {6910, 355578 }
490376

821830243

1045070081

10088

9348

Returns: {102663, 141535 }
495125

398789601

1891360824

5969

44412

Returns: {87320, 490368 }
497021

290040697

1807436745

4383

23378

Returns: {54628, 471043 }
498066

528413387

71308276

232585

8077

Returns: {20418, 261080 }
498104

2018619711

773766537

245218

137680

Returns: {2593, 385491 }
493512

896491225

2052107385

9013

189895

Returns: {37045, 235953 }
494293

2615526

463077229

134294

36832

Returns: {18619, 360871 }
492747

448381200

749893189

75225

40355

Returns: {197213, 474605 }
495446

811505679

1932328862

44975

408439

Returns: {1385, 454799 }
494589

1696445326

1894109777

24590

182023

Returns: {141530, 348143 }
492411

1148617376

1512876982

60259

143243

Returns: {19144, 426148 }
490413

36966277

982221903

202907

171580

Returns: {26684, 401171 }
492725

649702573

1067809548

90

91

Returns: {68603, 100640 }
497759

862595900

554189328

8

23

Returns: {0, 0 }
490238

1196581818

1268967609

78

54

Returns: {59655, 59765 }
492998

1976923607

511305630

20

64

Returns: {0, 0 }
499845

1512175815

1232468875

66

49

Returns: {3607, 3722 }
496901

972313797

2079309562

61

2

Returns: {0, 0 }
490353

853671490

1623098105

65

21

Returns: {0, 0 }
498004

450272945

1988410784

50

4

Returns: {0, 0 }
492764

1584609605

1544952264

100

39

Returns: {0, 0 }
494120

1750822649

1563368095

91

34

Returns: {0, 0 }
495624

538301532

1204196437

60

47

Returns: {201971, 202185 }
495235

938879864

1521134249

51

21

Returns: {207798, 207822 }
496835

1570294027

190283361

7

72

Returns: {0, 0 }
498767

1667571908

186737708

6

63

Returns: {0, 0 }
498304

895183525

1320304760

83

52

Returns: {0, 0 }
492730

1826276762

1766916924

65

14

Returns: {0, 0 }
492591

2058916868

1748981526

79

18

Returns: {0, 0 }
495093

738354880

608735521

36

91

Returns: {0, 0 }
499454

1203625776

1027057396

33

36

Returns: {165374, 167444 }
494041

933318049

132560718

5

76

Returns: {0, 0 }
490855

1971636361

922510580

61

81

Returns: {24845, 24987 }
490876

2090415265

1272582901

48

33

Returns: {94884, 94992 }
499227

727570682

1441461626

98

48

Returns: {0, 0 }
491049

1003911558

1590728627

80

28

Returns: {0, 0 }
490253

1861326141

1109533217

31

29

Returns: {407954, 412274 }
491332

98303578

920350134

36

48

Returns: {110263, 110522 }
492853

876756432

1165776836

76

64

Returns: {329475, 329930 }
497725

661151027

1331084905

75

46

Returns: {0, 0 }
493217

506577153

894784852

45

63

Returns: {163167, 163323 }
490471

1030737174

1245179593

69

50

Returns: {65340, 65459 }
500000

500000

500000

3

2

Returns: {0, 0 }
500000

0

0

1

1

Returns: {0, 0 }
500000

732819

3472819

1

3

Returns: {0, 0 }
500000

432343345

434454356

23453

65445

Returns: {0, 0 }
500000

47

1012345617

1

100000

Returns: {0, 0 }
500000

1234

715818053

2

1

Returns: {6615, 308787 }
500000

42

1000000000

3

2

Returns: {396312, 397427 }
500000

1234567890

1234567890

56

89

Returns: {89410, 91150 }
12

47

1012345678

6

12

Returns: {0, 6 }
500000

2147483647

2147383647

55

5555

Returns: {4271, 4373 }
500000

2147483641

2147483646

400

200

Returns: {0, 0 }
500000

1234

0

1

262144

Returns: {0, 0 }
500000

1234

1000000000

262144

262144

Returns: {98458, 100890 }
10

100

478614675

10

10

Returns: {4, 10 }
500000

500000

2147483647

10

1

Returns: {0, 0 }
12

73281

347284419

1

1

Returns: {3, 11 }
500000

325325

1073741824

60

61

Returns: {243388, 372374 }
4

0

1406932606

4

4

Returns: {2, 4 }
12

3

1012345678

1

2

Returns: {1, 7 }
500000

500000

2147483647

262144

1

Returns: {0, 0 }
500000

1768762

1872873

1

1

Returns: {58384, 58388 }

Statistics

Problem Statement for "ExactRate"

Problem Statement

Definition

Notes

Constraints

Examples