ContiguousConstantSegment
SRM 828 · 2022-04-22 · by misof
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
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.
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.
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ContiguousConstantSegment with a public method int produce(int N, int MOD, vector<int> Aprefix, int seed, int E) · 114 test cases · 2 s / 256 MB per case