ProductThreshold | Topcoder Archive

Problem Statement

You are given an array A that contains N integers, and a positive int limit.

We will use the term subarray to denote any non-empty contiguous segment of the array A. Two subarrays are distinct if they start or end at a different index in A. (Distinct subarrays may contain the same sequence of elements.)

A subarray is called modest if the product of all its elements doesn't exceed limit. Note that a subarray with a negative product is always modest.

Count and return the number of distinct modest subarrays in the given array A.

To keep the input small, the array A is given in the following format: You are given a non-empty int[] Aprefix and ints spread and offset. Use the following pseudocode to generate A:

p = length( Aprefix )
for i = 0 .. p-1:
    A[i] = Aprefix[i]
seed = abs( A[p-1] )
for i = p .. N-1:
    seed = (seed * 1103515245 + 12345) modulo 2^31
    A[i] = (seed modulo spread) + offset

Definition

Class:: ProductThreshold
Method:: subarrayCount
Parameters:: int, int, int[], int, int
Returns:: long
Method signature:: long subarrayCount(int N, int limit, int[] Aprefix, int spread, int offset)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator.
The last two constraints imply that all elements of A will always be between -10^9 and 10^9, inclusive.

Constraints

N will be between 1 and 100,000, inclusive.
limit will be between 1 and 10^9, inclusive.
Aprefix will contain between 1 and min(N,500) elements, inclusive.
Each element of Aprefix will be between -10^9 and 10^9, inclusive.
spread will be between 1 and 2*10^9 + 1, inclusive.
offset will be greater than or equal to -10^9.
spread-1+offset will be less than or equal to 10^9.

Examples

```
5
```
```
5
```
```
{1,2,3,-4,5}
```
```
1
```
```
1
```
```
Returns: 13
```
We are given the entire sequence A in the array Aprefix. Modest subarrays are subarrays with product not exceeding 5. All 8 subarrays that contain the element -4 are modest. Additionally, subarrays {1}, {1,2}, {2}, {3}, and {5} are modest. That gives us a total of 13 modest subarrays.
```
10
```
```
8
```
```
{2,2,2,2,2,2,2,2,2,2}
```
```
1
```
```
47
```
```
Returns: 27
```
Each subarray of length 1, 2, or 3 is modest. No other subarray is modest.
```
20
```
```
999888777
```
```
{47}
```
```
7654321
```
```
1
```
```
Returns: 21
```
The array A you should generate looks as follows: {47, 4139827, 3367492, 890643, 113351, 7314474, 5690828, 5571137, 3860068, 2551091, 3662623, 379062, 3134150, 5405018, 2518354, 5390370, 4216741, 5130660, 4174938, 2342215}. Each one-element subarray is modest, and the subarray {47, 4139827} is also modest.
```
5
```
```
8
```
```
{3,0,3,0,3}
```
```
47
```
```
47
```
```
Returns: 15
```
Each subarray of the array {3,0,3,0,3} has a product that does not exceed 8.
```
1000
```
```
1
```
```
{-1}
```
```
1
```
```
2
```
```
Returns: 1000
```
This array looks as follows: {-1, 2, 2, 2, 2, ...}. Only the substrings that contain the element at index 0 are modest.
```
100
```
```
47
```
```
{1}
```
```
1
```
```
1
```
```
Returns: 5050
```

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.