ExactRate | Topcoder Archive

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.

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.