Connection Status:
Competition Arena > ProductThreshold

ProductThreshold

2018 TCO Fun 3A · 2018-04-20 · by misof

2018 TCO Fun 3A · 2018-04-20 · by misof · Simple Math, Simple Search, Iteration
Class Name: ProductThreshold
Return Type: long
Method Name: subarrayCount
Arg Types: (int, int, vector<int>, int, int)
Problem Statement

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

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

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

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

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

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

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

Coding Area

Language: C++17 · define a public class ProductThreshold with a public method long long subarrayCount(int N, int limit, vector<int> Aprefix, int spread, int offset) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous