Connection Status:
Competition Arena > NoQuickGrowth

NoQuickGrowth

SRM 847 · 2023-06-22 · by misof

SRM 847 · 2023-06-22 · by misof · Dynamic Programming
Class Name: NoQuickGrowth
Return Type: int
Method Name: solve
Arg Types: (int, int, int, int)
Problem Statement

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

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

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

2)
7
-3
10000000
4747
Returns: 4

The pseudocode should produce the following sequence: A = {4262855, 5911200, 6624873, -1410345, 1378369, -6155535, -1297177}.

3)
10
10
10
4747
Returns: 4
4)
200000
10
0
42
Returns: 0
91)
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.

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

Coding Area

Language: C++17 · define a public class NoQuickGrowth with a public method int solve(int N, int delta, int spread, int seed) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous