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}.
10
10
10
4747
Returns: 4
200000
10
0
42
Returns: 0
200000
10
47
47
Returns: 197045
200000
9
47
47
Returns: 160253
200000
-9
10
235
Returns: 444
200000
11
100
324545
Returns: 199980
200000
-11
1
244
Returns: 0
200000
-11
11
32535
Returns: 381
14
0
8
1948501517
Returns: 1
31
9
8
1660249968
Returns: 15
49
11
12
1797583853
Returns: 44
16
11
4
2068253425
Returns: 13
10
-11
5
1836955051
Returns: 0
25
-9
8
1542245923
Returns: 0
25
11
8
1607036031
Returns: 20
48
9
8
841741944
Returns: 24
12
10
5
420679459
Returns: 6
47
0
8
1085916001
Returns: 4
183181
-10
3
1438208187
Returns: 0
187161
0
11
473072173
Returns: 27480
193653
-9
5
1229727803
Returns: 0
187830
-11
8
1123519141
Returns: 0
191696
-9
9
172270288
Returns: 0
195857
9
9
1698564564
Returns: 112894
188527
-10
8
948917258
Returns: 0
199868
11
10
889428824
Returns: 199859
192447
0
4
640818900
Returns: 0
194545
11
2
355519765
Returns: 194540
182444
9
8
2046595582
Returns: 101092
194274
9
12
142514072
Returns: 121571
199916
9
10
2026408624
Returns: 118906
190321
-11
0
1043761029
Returns: 0
186925
9
6
790342737
Returns: 92983
185789
0
3
549224465
Returns: 0
183224
10
11
1477705088
Returns: 174486
197281
0
1
1146177193
Returns: 0
194546
11
10
525600088
Returns: 194537
193568
11
5
88998632
Returns: 193561
188658
11
2
778158833
Returns: 188653
196766
-11
7
863925910
Returns: 0
196210
-9
7
42895311
Returns: 0
182419
10
2
1453170456
Returns: 145446
181529
-9
3
263002937
Returns: 0
192410
11
0
380485713
Returns: 192409
189919
11
8
1321413367
Returns: 189910
187835
-9
11
649419618
Returns: 2076
198020
-9
12
1173215853
Returns: 4780
198705
11
9
2109919775
Returns: 198696
191230
-9
0
492182829
Returns: 0
193548
0
5
1300568894
Returns: 0
198491
-11
12
2101334812
Returns: 1890
199584
10
1
502796335
Returns: 132609
195114
-10
12
1948911863
Returns: 3134
180585
0
12
284290351
Returns: 30341
189425
-11
11
2105402687
Returns: 319
196462
11
12
1052781061
Returns: 196452
191540
-11
5
716905769
Returns: 0
195157
11
9
421704849
Returns: 195148
195055
0
4
102151484
Returns: 0
198356
10
10
1232890504
Returns: 188046
181339
-11
4
2073107849
Returns: 0
192573
11
11
468300517
Returns: 192564
197067
-10
9
2050067571
Returns: 0
197601
-10
12
1554617535
Returns: 3256
198955
9
6
879909240
Returns: 99088
182996
11
8
1309953612
Returns: 182987
193273
9
8
1546714289
Returns: 107163
183565
-11
1
1830200175
Returns: 0
191813
-17
1139
1683014802
Returns: 153362
188778
-4
50
898538742
Returns: 79941
195237
-1
15408
1363446327
Returns: 187936
181794
-11
256822
2642986
Returns: 179342
180901
7
15366
1106908031
Returns: 177255
189632
-14
319
729061624
Returns: 125858
193863
1
30343
1007203776
Returns: 189127
196493
16
50010
1344280466
Returns: 196352
198179
-19
461017
1983527925
Returns: 195823
198294
-9
1839232
183808378
Returns: 197032
185951
19
18
2082862941
Returns: 185947
193468
-17
123
755530463
Returns: 92341
199593
5
0
597387838
Returns: 0
182385
15
2051
1650855086
Returns: 182349
196361
9
915616
526066028
Returns: 195446
196752
5
4
1805133931
Returns: 14252
193498
15
5
2141323295
Returns: 193495
195591
8
311282
1698673775
Returns: 194474
197187
12
954
844576579
Returns: 197148
190367
5
2
2094311409
Returns: 0
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.
200000
5
9000
123123
Returns: 193338
200000
10
100000
123456
Returns: 199123
200000
20
10000000
428341411
Returns: 199173
200000
10
1245
12456
Returns: 199028