NoQuickGrowth | Topcoder Archive

Problem Statement

The sequence S is growing too quickly if you can point to two of its elements S[i] and S[j] with i < j such that the difference S[j] - S[i] is greater than 10*(j-i).

(Note that the difference can be negative, which is allowed. For example, the sequence {500, 400, 300, 200, 100} isn't growing too quickly.)

You are given a sequence A of N integers. You have a blaster. In each step, you can use the blaster to shoot any element of A. When you do so, you may choose an arbitrary new integer value for that element.

Return the minimum number of shots needed to turn A into a sequence that isn't growing too quickly.

In order to keep the input size small, the sequence A will be pseudorandomly generated. Please use the pseudocode below.

state = seed
for i = 0 to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    diff = state modulo (2*spread + 1)
    A[i] = i*delta + diff - spread

Definition

Class:: NoQuickGrowth
Method:: solve
Parameters:: int, int, int, int
Returns:: int
Method signature:: int solve(int N, int delta, int spread, int seed)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom input. It would correctly solve any input of the given size.

Constraints

N will be between 1 and 200,000, inclusive.
delta will be between -20 and 20, inclusive.
spread will be between 0 and 10^7, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

```
7
```
```
10
```
```
0
```
```
47
```
```
Returns: 0
```
The sequence is A = {0, 10, 20, 30, 40, 50, 60}. We do not need to use the blaster.
```
7
```
```
11
```
```
0
```
```
47
```
```
Returns: 6
```
The sequence is A = {0, 11, 22, 33, 44, 55, 66}. We have to blast at least 6 of its 7 elements. One valid solution that uses blaster six times is to turn the sequence into {22, 22, 22, 23, 23, 23, -47}.
```
7
```
```
-3
```
```
10000000
```
```
4747
```
```
Returns: 4
```
The pseudocode should produce the following sequence: A = {4262855, 5911200, 6624873, -1410345, 1378369, -6155535, -1297177}.
```
6
```
```
1
```
```
10
```
```
428341411
```
```
Returns: 0
```
The generated sequence is A = {3, 2, 5, 12, 5, 11}. This sequence does not grow too quickly anywhere, so we don't have to use the blaster at all.

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.