Connection Status:
Competition Arena > ExactRate

ExactRate

SRM 824 · 2022-02-17 · by misof

SRM 824 · 2022-02-17 · by misof · Math, Sorting
Class Name: ExactRate
Return Type: int[]
Method Name: getLongest
Arg Types: (int, int, int, int, int)
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

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

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

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

3)
500000
47
1012345678
1
1
Returns: {93575, 96685 }
4)
500000
42
1073741824
1
1
Returns: {4814, 258832 }

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

Coding Area

Language: C++17 · define a public class ExactRate with a public method vector<int> getLongest(int N, int seed, int threshold, int S, int F) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous