ConstantSegment
TCO21 Parallel 2B · 2021-04-13 · by misof
Problem Statement
N robots are waiting in a line at a robot repair facility. The robots are numbered from 0 to N-1 in the order in which they are waiting.
Each of the robots has one of M possible problems. The problems are numbered from 0 to M-1. The problem of robot i is P[i].
If two or more consecutive robots have the same problem, the workers at the repair facility are happy because they can use the same equipment and thus there are no unnecessary overheads.
At some point during the repairs you would like to have at least K consecutive robots that all have the same problem. In order to reach this goal, you can send an arbitrary subset of robots home. (The robots that remain waiting will still wait in the same relative order.)
Find out whether your goal is reachable. If it isn't, return -1. If it is, return the smallest number of robots that need to be sent home.
In order to keep the input size small, only a prefix of the array P is given, the rest is generated pseudorandomly. Please use the code or pseudocode below to generate P.
Pseudocode:
P = an empty array of length N
L = length(Pprefix)
for i = 0 to L-1:
P[i] = Pprefix[i]
state = seed
for i = L to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
P[i] = (state div 16) modulo M
------------------------------------------------------
Java:
int[] P = new int[N];
int L = Pprefix.length;
for (int i=0; i<L; ++i) P[i] = Pprefix[i];
long state = seed;
for (int i=L; i<N; ++i) {
state = (state * 1103515245 + 12345) % (1L << 31);
P[i] = (int)((state / 16) % M);
}
------------------------------------------------------
C++:
vector<int> P(N);
int L = Pprefix.size();
for (int i=0; i<L; ++i) P[i] = Pprefix[i];
long long state = seed;
for (int i=L; i<N; ++i) {
state = (state * 1103515245 + 12345) % (1LL << 31);
P[i] = (state / 16) % M;
}
Notes
- The reference solution does not depend on the input being pseudorandom, it would correctly solve any input of the given size.
Constraints
- N will be between 1 and 200,000, inclusive.
- K will be between 1 and N, inclusive.
- M will be between 1 and 10^6, inclusive.
- Pprefix will have between 0 and min(N, 200) elements, inclusive.
- Each element of Pprefix will be between 0 and M-1, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
10
3
10
{1, 4, 3, 3, 3, 3, 2, 0, 3, 9}
0
Returns: 0
You want to have at least three consecutive robots with the same problem. This is already happening: there are four consecutive robots with problem of type 3.
10
5
10
{1, 4, 3, 3, 3, 3, 2, 0, 3, 9}
0
Returns: 2
In order to have at least five consecutive robots with the same problem, you should send home robots #6 (problem of type 2) and #7 (problem of type 0).
10
6
10
{1, 4, 3, 3, 3, 3, 2, 0, 3, 9}
0
Returns: -1
In this test case it is not possible to have six or more consecutive robots with the same problem.
10
2
47
{1, 4, 5, 2, 1, 2, 3, 7, 8, 3}
4747
Returns: 1
The optimal solution here is to send just one robot home: robot #4 (problem type 1). This creates two consecutive robots with the same problem (type 2).
20
3
10
{0, 1, 2, 3, 4}
123456789
Returns: 9
The array P you should have generated is {0, 1, 2, 3, 4, 0, 5, 7, 1, 3, 5, 4, 0, 6, 3, 7, 2, 4, 6, 5}. If you wrote your own code to generate P, please watch out for integer overflow when calculating new values of the variable "state".
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConstantSegment with a public method int sendSomeHome(int N, int K, int M, vector<int> Pprefix, int seed) · 72 test cases · 2 s / 256 MB per case