ContiguousConstantSegment | Topcoder Archive

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.

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.