Problem Statement
You have a sequence A[0..N-1] of integers, each between 0 and MOD-1, inclusive.
You have to make exactly E edits. In each edit, you have to pick one index into A and replace that value by a new one. The new value must differ from the old one.
(Values have no memory. Thus, it is allowed to change A[2] from 42 to 47 and then in the next edit change A[2] from 47 back to 42. The only requirement is that each edit must change exactly one element of the array.)
You want to perform the E edits in such a way that the final array will contain a contiguous segment of equal values that is as long as possible. Return the length of that segment.
In order to keep the input size small, the array A is generated pseudorandomly. Please use the pseudocode below to generate it.
L = length(Aprefix)
for i = 0 to L-1: A[i] = Aprefix[i]
state = seed
for i = L to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = (state div 16) modulo MOD
Definition
- Class:
- ContiguousConstantSegment
- Method:
- produce
- Parameters:
- int, int, int[], int, int
- Returns:
- int
- Method signature:
- int produce(int N, int MOD, int[] Aprefix, int seed, int E)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input sequence being (pseudo)random.
- In each edit, the new value may be an arbitrary integer. In particular, the new values may lie outside of the range [0, MOD). See Example 3.
Constraints
- N will be between 1 and 250,000, inclusive.
- MOD will be between 1 and 250,000, inclusive.
- Aprefix will have between 1 and min(100,N) elements, inclusive.
- Each element of Aprefix will be between 0 and MOD-1, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- E will be between 0 and 250,000, inclusive.
Examples
9
10
{1, 2, 3, 2, 4, 5, 2, 2, 6}
47
0
Returns: 2
As N = length(Aprefix), we are already given the full sequence: A = {1, 2, 3, 2, 4, 5, 2, 2, 6}. We cannot make any edits. The longest contiguous segment of equal values are the two consecutive 2s at 0-based indices 6 and 7.
9
10
{1, 2, 3, 2, 4, 5, 2, 2, 6}
34424
1
Returns: 3
The same sequence as before but now we have to make exactly one edit. There are three optimal ways to do so: we can change any one of the values A[2], A[5] and A[8] to 2. In each of those cases we will obtain three consecutive 2s, so the correct return value is 3.
9
10
{1, 2, 3, 2, 4, 5, 2, 2, 6}
366122
2
Returns: 5
For the same sequence, if we are allowed two edits, the best solution is now unique (up to the order in which we make the edits): we should change A[4] and A[5] to 2. This produces a contiguous segment of 5 equal values.
4700
1
{0}
123
16
Returns: 4700
We start with a sequence of 4700 zeros. One optimal way of making the 16 edits is to alternately change A[1234] to 5678 and then back to 0. We will end with a sequence of 4700 zeros again.
20
100
{0, 42, 47}
123
6
Returns: 8
Your array A should look as follows: A = { 0, 42, 47, 53, 39, 61, 9, 28, 54, 78, 71, 7, 70, 14, 84, 53, 30, 71, 34, 96 }. Six edits are just enough to create a contiguous segment of eight equal elements with value 71.
4700
1
{0}
123
123
Returns: 4700
4700
1
{0}
2424
1
Returns: 4699
1
47
{42}
111
0
Returns: 1
1
47
{42}
1244
1
Returns: 1
250000
250
{47}
47
30000
Returns: 30170
250000
2
{0}
47
100000
Returns: 200005
2
47
{42, 42}
42
0
Returns: 2
2
47
{42, 42}
42
1
Returns: 1
2
47
{42, 42}
42
2
Returns: 2
2
47
{42, 42}
33
3
Returns: 2
55
66
{55, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 33, 61, 14, 14, 14, 14, 30, 14, 14, 14, 14, 4, 14, 14, 14, 25, 14, 14, 16, 14, 12, 46, 14, 14, 14, 14, 14, 14, 14, 60, 14, 14, 14, 14, 14, 14, 14, 5, 14, 14, 14, 14, 14}
1906624755
18
Returns: 55
10
670
{125, 424, 68, 205, 21, 270, 205, 143, 205, 205}
1453170456
5
Returns: 9
91
889
{269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 445, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269, 269}
1983527925
89
Returns: 91
88
573
{183, 386, 43, 185, 185, 79, 496, 420, 61, 229, 472, 180, 407, 4, 142, 74, 398, 94, 393, 511, 466, 382, 125, 523, 410, 104, 88, 430, 421, 563, 106, 179, 510, 487, 449, 95, 404, 537, 517, 335, 442, 201, 323, 406, 76, 94, 499, 341, 94, 258, 497, 94, 365, 30, 404, 83, 229, 528, 215, 519, 94, 313, 512, 116, 63, 293, 181, 499, 247, 414, 485, 7, 409, 240, 567, 383, 94, 345, 65, 160, 108, 244, 187, 81, 145, 94, 94, 169}
1282909328
78
Returns: 86
15
659
{306, 306, 306, 306, 306, 568, 306, 306, 306, 136, 306, 458, 630, 306, 306}
1741737939
9
Returns: 15
17
895
{24, 402, 67, 784, 427, 375, 532, 90, 353, 739, 67, 639, 642, 347, 67, 886, 856}
1600605750
7
Returns: 9
70
940
{219, 340, 410, 100, 100, 100, 100, 600, 424, 333, 100, 100, 550, 100, 100, 100, 111, 21, 318, 810, 49, 623, 223, 100, 100, 864, 536, 885, 626, 3, 35, 892, 567, 100, 50, 392, 100, 100, 100, 195, 100, 283, 691, 100, 100, 100, 100, 100, 38, 907, 100, 311, 100, 731, 318, 53, 624, 938, 452, 474, 416, 100, 100, 340, 736, 92, 259, 873, 100, 100}
650746088
16
Returns: 30
46
633
{495, 418, 418, 619, 418, 419, 418, 418, 187, 418, 438, 499, 501, 417, 351, 418, 569, 309, 418, 418, 418, 36, 418, 275, 145, 478, 401, 418, 110, 607, 34, 418, 348, 418, 418, 1, 266, 359, 418, 40, 422, 492, 331, 418, 418, 262}
230505136
52
Returns: 46
70
336
{280, 45, 45, 45, 45, 45, 45, 296, 45, 45, 45, 199, 45, 130, 45, 45, 61, 45, 190, 332, 272, 45, 45, 45, 45, 45, 164, 291, 19, 45, 45, 151, 228, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 333, 111, 101, 252, 45, 39, 195, 45, 11, 45, 45, 45, 54, 45, 45, 112, 211, 45, 44, 45, 328, 324, 45}
1474467706
26
Returns: 70
85
887
{619, 645, 572, 688, 516, 688, 765, 794, 868, 335, 381, 688, 688, 676, 688, 688, 77, 688, 688, 475, 711, 460, 301, 636, 688, 809, 688, 688, 504, 688, 688, 879, 688, 688, 688, 688, 688, 839, 845, 716, 870, 829, 437, 77, 688, 688, 391, 331, 470, 298, 164, 688, 688, 371, 688, 688, 37, 688, 688, 688, 688, 25, 688, 688, 688, 688, 280, 566, 688, 775, 542, 241, 465, 465, 688, 688, 688, 688, 688, 688, 412, 688, 688, 688, 688}
2125728832
76
Returns: 85
89
960
{518, 518, 518, 518, 139, 518, 518, 518, 518, 518, 623, 518, 518, 518, 518, 518, 518, 518, 518, 518, 518, 518, 518, 935, 518, 518, 518, 518, 518, 518, 518, 518, 518, 518, 518, 651, 518, 518, 518, 183, 518, 518, 518, 617, 518, 518, 518, 624, 518, 518, 518, 750, 274, 518, 518, 518, 518, 518, 518, 482, 518, 518, 518, 518, 518, 518, 853, 467, 183, 518, 518, 518, 810, 518, 518, 518, 518, 518, 518, 518, 518, 930, 518, 518, 518, 70, 518, 518, 409}
370362191
23
Returns: 89
47
531
{524, 476, 524, 524, 524, 226, 524, 524, 201, 511, 524, 309, 524, 12, 524, 524, 430, 99, 90, 337, 266, 237, 141, 251, 509, 524, 34, 524, 24, 524, 524, 524, 234, 250, 500, 379, 206, 524, 190, 524, 524, 524, 524, 524, 237, 433, 524}
459752443
35
Returns: 47
88
372
{119, 119, 119, 119, 119, 119, 27, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 296, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 273, 119, 119, 119, 119, 119, 119, 119, 69, 343, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 119, 245, 218, 119, 119, 119, 119, 359}
615071276
75
Returns: 88
36
509
{460, 460, 54, 148, 394, 460, 326, 460, 350, 276, 388, 460, 460, 406, 430, 460, 99, 460, 460, 460, 460, 460, 460, 460, 460, 190, 460, 460, 170, 467, 441, 460, 460, 460, 460, 272}
565175511
9
Returns: 26
45
231
{35, 133, 99, 40, 133, 206, 141, 7, 18, 62, 173, 178, 133, 109, 130, 133, 153, 16, 199, 133, 133, 91, 68, 48, 11, 78, 230, 133, 45, 133, 134, 79, 78, 111, 183, 87, 225, 12, 94, 190, 200, 166, 133, 64, 163}
851640761
25
Returns: 33
14
333
{291, 291, 34, 59, 140, 291, 291, 225, 291, 291, 49, 4, 300, 170}
1662575028
11
Returns: 14
30
945
{217, 217, 217, 217, 217, 217, 217, 217, 217, 217, 217, 779, 47, 160, 34, 217, 944, 217, 217, 217, 217, 217, 253, 899, 217, 217, 217, 278, 217, 217}
1320042049
1
Returns: 12
83
306
{209, 294, 298, 191, 169, 125, 144, 109, 172, 206, 190, 108, 70, 181, 263, 14, 15, 15, 279, 180, 15, 45, 44, 15, 15, 214, 258, 78, 94, 86, 231, 35, 109, 187, 196, 98, 254, 36, 285, 254, 15, 28, 10, 165, 287, 99, 194, 6, 70, 284, 201, 188, 118, 55, 127, 102, 15, 131, 301, 15, 202, 15, 247, 17, 84, 15, 99, 15, 15, 272, 179, 75, 24, 18, 15, 94, 91, 25, 6, 182, 107, 11, 259}
498149383
8
Returns: 14
26
816
{547, 547, 547, 429, 334, 547, 547, 547, 472, 547, 547, 547, 547, 547, 547, 427, 547, 519, 547, 547, 547, 547, 547, 547, 547, 664}
74763198
15
Returns: 26
60
727
{41, 522, 564, 564, 564, 555, 564, 353, 648, 523, 470, 564, 564, 564, 564, 564, 96, 211, 64, 564, 564, 272, 564, 600, 684, 564, 100, 564, 520, 703, 564, 564, 267, 564, 564, 564, 564, 509, 564, 564, 564, 564, 626, 626, 564, 564, 564, 564, 47, 564, 445, 373, 558, 564, 564, 721, 564, 564, 564, 564}
1893090559
5
Returns: 20
18
791
{738, 711, 573, 64, 404, 788, 404, 404, 163, 66, 175, 404, 195, 216, 404, 589, 765, 675}
1746362613
15
Returns: 18
38
499
{106, 132, 318, 261, 87, 337, 398, 418, 413, 198, 155, 295, 413, 319, 88, 369, 296, 458, 82, 157, 15, 21, 388, 275, 276, 329, 454, 363, 97, 101, 301, 42, 328, 223, 431, 285, 112, 283}
173909888
13
Returns: 15
88
6
{0, 5, 3, 2, 2, 5, 4, 2, 3, 2, 5, 1, 5, 0, 5, 2, 2, 1, 2, 3, 5, 2, 2, 2, 5, 2, 2, 2, 1, 1, 1, 1, 3, 2, 4, 2, 1, 3, 5, 2, 4, 3, 0, 0, 3, 2, 0, 0, 2, 2, 1, 5, 5, 5, 5, 2, 3, 0, 0, 2, 2, 2, 1, 0, 2, 3, 5, 1, 1, 4, 1, 3, 2, 3, 0, 1, 2, 0, 5, 3, 5, 2, 2, 2, 2, 1, 2, 2}
480601085
14
Returns: 27
78
916
{3, 14, 3, 146, 3, 3, 3, 3, 3, 84, 852, 512, 3, 3, 3, 3, 3, 3, 878, 792, 3, 190, 3, 3, 826, 341, 3, 3, 3, 3, 895, 687, 609, 3, 3, 113, 3, 3, 700, 3, 3, 3, 511, 3, 211, 3, 3, 120, 3, 3, 331, 434, 369, 3, 3, 3, 3, 3, 3, 300, 424, 3, 687, 494, 3, 254, 3, 465, 3, 827, 3, 540, 3, 3, 444, 627, 772, 337}
386610351
48
Returns: 78
81
680
{205, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 509, 573, 573, 573, 573, 573, 367, 573, 573, 573, 573, 573, 573, 573, 573, 551, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 300, 573, 573, 573, 117, 422, 573, 573, 573, 263, 573, 573, 372, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 573, 103, 573}
363055109
66
Returns: 81
41
916
{507, 741, 14, 439, 543, 582, 228, 14, 14, 308, 14, 155, 496, 692, 71, 201, 528, 408, 494, 14, 433, 688, 216, 901, 264, 14, 14, 391, 14, 387, 14, 14, 660, 528, 541, 696, 14, 800, 725, 884, 881}
1778261213
21
Returns: 31
68
456
{388, 57, 311, 250, 449, 282, 112, 133, 30, 386, 392, 294, 204, 29, 331, 392, 262, 392, 14, 341, 257, 49, 389, 70, 308, 392, 292, 237, 125, 163, 239, 186, 376, 229, 190, 35, 340, 385, 450, 212, 227, 392, 138, 63, 359, 167, 5, 392, 291, 265, 271, 349, 392, 392, 239, 56, 341, 392, 392, 226, 392, 424, 35, 126, 102, 294, 325, 392}
1025817869
16
Returns: 23
27
54
{45, 45, 45, 45, 8, 8, 45, 45, 23, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 16, 44, 45, 45, 8, 45, 45, 45}
1840443727
8
Returns: 27
54
164
{22, 80, 97, 26, 145, 145, 26, 78, 145, 145, 145, 42, 145, 88, 145, 68, 145, 145, 71, 145, 145, 145, 104, 145, 70, 145, 84, 108, 115, 145, 135, 145, 32, 145, 145, 30, 145, 87, 74, 145, 162, 145, 158, 145, 145, 7, 145, 121, 134, 145, 145, 145, 39, 145}
228292402
8
Returns: 22
85
916
{861, 652, 552, 103, 317, 116, 456, 812, 490, 603, 640, 328, 395, 465, 342, 395, 244, 174, 353, 62, 395, 160, 13, 395, 271, 583, 475, 243, 395, 310, 530, 807, 395, 395, 695, 395, 292, 395, 585, 326, 776, 395, 395, 395, 830, 395, 585, 395, 368, 891, 837, 181, 395, 907, 371, 395, 371, 663, 878, 520, 395, 395, 395, 395, 238, 518, 395, 594, 702, 279, 690, 755, 776, 107, 395, 855, 395, 21, 882, 395, 395, 395, 788, 666, 241}
1697770609
53
Returns: 79
225379
400
{79, 150, 116, 123, 382, 201, 355, 185, 235, 236}
1984206482
118209
Returns: 118569
220972
105
{101}
195732579
82459
Returns: 83349
232935
302
{197, 286}
2039351502
123614
Returns: 124097
232949
448
{180, 338, 281, 282, 37, 320, 188, 204}
1161823613
225585
Returns: 226150
206268
20800
{15420, 5095, 18233, 11538, 1642, 9594, 16136, 16117, 5274, 19030}
2019209101
35169
Returns: 35180
247740
2
{1, 1, 1, 0, 1, 0, 1, 0, 0}
96388952
176364
Returns: 247740
222486
31377
{14646, 1295, 13503, 14086}
1158402265
5503
Returns: 5509
215092
1667
{1235, 1000, 1078}
1283320413
110696
Returns: 110805
221055
2230
{2024, 1159, 299, 1824, 663, 831, 1061, 233}
1492052662
132696
Returns: 132787
222832
691
{214, 320}
589686326
201814
Returns: 202162
238330
5422
{3498, 4427, 3978, 1830, 2515, 798, 1304}
479474032
83033
Returns: 83069
229180
334
{130, 309, 51, 220, 164}
322959397
48242
Returns: 48438
215192
21
{1, 16, 0, 10}
239459293
150999
Returns: 158743
208483
6
{5}
1569066461
14095
Returns: 17125
200425
406
{88}
899830479
120387
Returns: 120748
215724
1811
{1550, 248, 1567, 1673, 212}
1934757845
20906
Returns: 20936
200769
50
{5, 42, 37}
1450407234
143003
Returns: 146101
205321
61772
{32160, 17075, 49382, 36152}
1377481704
152745
Returns: 152757
220107
2
{1, 0, 0, 0, 0, 1, 1}
422052075
44286
Returns: 88575
205418
15
{0, 8, 13, 11, 4, 9}
784501809
143957
Returns: 154591
232699
1
{0, 0}
1570733817
29465
Returns: 232699
222342
987
{110, 510, 249, 34, 14, 637, 496, 447, 85}
716179224
6902
Returns: 6925
227440
570
{256, 60, 259, 126, 108}
1174443297
137862
Returns: 138180
228835
43
{29, 5, 32}
1533112088
12670
Returns: 13042
245025
4513
{4508, 3072}
2083983488
79454
Returns: 79492
244686
1187
{751, 353, 183, 644, 552}
1906963443
48224
Returns: 48295
201983
14820
{8014, 8772, 6730, 8170, 3478, 8343, 7139}
145197697
196486
Returns: 196516
241646
11676
{6299}
1271221512
118028
Returns: 118054
218211
2740
{1178, 406}
1248462140
215125
Returns: 215240
227560
3
{2, 1}
104777245
9527
Returns: 14566
245695
45
{10, 34}
466533709
104700
Returns: 107236
222210
1
{0, 0, 0, 0}
232355229
67343
Returns: 222210
202588
42
{33, 12, 10}
2024713911
132344
Returns: 135734
249801
29
{17, 7, 17, 4}
962268816
137496
Returns: 142601
218074
20
{16, 11, 14, 1}
1416550212
26481
Returns: 28002
218613
2
{1, 0, 1, 0, 0, 0, 1, 0}
1412146829
161510
Returns: 218613
214183
828
{77, 727, 29, 325, 827, 388, 755, 24, 137, 436}
759952326
173124
Returns: 173387
205786
28503
{23177, 16696}
1185527669
158531
Returns: 158548
215640
2125
{641, 1344, 2112, 1732, 673, 121, 787, 187, 1990, 557}
387984990
123176
Returns: 123264
240167
1
{0, 0}
513559682
231931
Returns: 240167
226732
95768
{92112}
1815325890
203265
Returns: 203276
206261
10649
{10519, 5910, 7295, 2624, 7585, 6840, 9729, 3336, 2628}
915701050
105058
Returns: 105085
227537
11801
{9763, 11084, 2493, 10309, 907, 7496, 3187}
1161427947
75142
Returns: 75165
208298
4687
{1001, 2028, 2372, 3035, 1763}
1453597035
183706
Returns: 183777
215790
70
{27, 18, 33, 36, 28, 3, 42, 60, 33}
1565687970
4018
Returns: 4113
232550
198
{147, 123}
731790164
132679
Returns: 133456
208126
18038
{17065, 10773, 16687, 1378}
1637365363
86917
Returns: 86934
231184
7
{4, 0, 2, 1, 5}
417607141
108970
Returns: 127336
238280
75795
{19037, 50923, 70757, 46373, 55955, 3005, 62099, 56214}
781775577
208778
Returns: 208790
212765
14148
{1018, 9175, 679, 1048}
846785141
107193
Returns: 107216
223058
7
{3, 4, 2, 2, 4, 3, 3, 4, 0}
1797583853
815
Returns: 1006
243163
1
{0}
2068253425
966
Returns: 243163
247438
1
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
841741944
572
Returns: 247438
215638
2
{0, 1, 1, 1, 0, 0}
1438208187
950
Returns: 1906
214323
39986
{39626, 23137, 18764, 15661, 36389, 17143, 23392}
172270288
546
Returns: 549
231715
916
{747, 531, 818, 226, 620}
889428824
117
Returns: 122
224894
49357
{36571, 9778, 29090, 995, 11160, 35847, 41101, 5424, 4889, 17416}
2046595582
524
Returns: 527
228548
2183
{1085, 2117, 1932, 1290, 91, 995, 865, 1417, 1767, 753}
2017745344
181
Returns: 185
213020
19
{18, 11, 16}
464222191
402
Returns: 447
217489
16398
{13568, 2200}
88998632
379
Returns: 382
1
47
{42}
34
2
Returns: 1
1
4733
{42}
44
3
Returns: 1
3
5
{2, 2, 2 }
10
1
Returns: 2
9
10
{0, 0, 0, 0, 0, 0, 0, 0, 0 }
34424
1
Returns: 8
14
2
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1 }
1
8
Returns: 14
250000
10000
{1, 2, 3 }
55
50000
Returns: 50019
4700
1
{0 }
123
1
Returns: 4699
1
12345
{1 }
12344
1
Returns: 1
9
10
{1, 2, 3, 2, 4, 5, 2, 2, 6 }
47
250000
Returns: 9