ColorfulStrip
SRM 842 · 2022-12-01 · by misof
Problem Statement
We have a strip of N cells. Each cell can be one of C colors. The cells of the strip are numbered from 0 to N-1, left to right. The colors are numbered from 0 to C-1. Initially, all cells have color 0.
You are going to perform a sequence of Q operations.
The operations are numbered from 0 to Q-1. In each operation you will take some contiguous segment of the strip and repaint it in a new color.
The segment for operation i will start at index QL[i], end at index QR[i], and the new color for all its cells (including both endpoints) will be QC[i].
The hash of a sequence S = { s[0], s[1], ..., s[k-1] } is the value h(S) = sum( s[i]*10^i ) modulo (10^9 + 7).
For example, the hash of the sequence {2, 10, 4} is 2 + 10*10 + 4*100 = 502, and the hash of the sequence {0, 0, 0, 0, 0, 0, 0, 0, 0, 2} is 2,000,000,000 mod (10^9 + 7) = 999,999,993.
Given a state of the strip, its color distribution is the sequence P = { p[0], p[1], ..., p[C-1] } where p[i] is the number of cells that currently have the color i. The value h(P) will be called the fingerprint.
Consider the sequence F = { f[0], f[1], ..., f[Q-1] }, where f[i] is the fingerprint after performing the i-th operation. Calculate and return the value h(F).
In order to keep the input small, all operations are pseudorandom. Please use the pseudocode below to generate them.
state = seed
for i = 0 to Q-1:
state = (state * 1103515245 + 12345) modulo 2^31
qlen = 1 + (state modulo maxL)
state = (state * 1103515245 + 12345) modulo 2^31
QL[i] = state modulo (N+1-qlen)
QR[i] = QL[i] + qlen - 1
state = (state * 1103515245 + 12345) modulo 2^31
QC[i] = state modulo C
Notes
- The pseudocode used to generate QL and QR ensures that for each i we have QL[i] <= QR[i].
- The reference solution does not depend on the input being pseudorandom. It would correctly solve any input of the same size.
Constraints
- N will be between 1 and 10^9, inclusive.
- C will be between 1 and 10^9, inclusive.
- Q will be between 1 and 250,000, inclusive.
- maxL will be between 1 and N, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
100 1 12 13 47 Returns: 111033323
There are 100 cells, 1 color, and 12 queries. As there is only one color, after each operation there will be 100 cells of color 0, so the color distribution will always be {100} and the fingerprint will always be 100. The correct return value is therefore the hash of the sequence {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}.
997 10 5 350 474747 Returns: 530787752
You should generate the following operations: QL = { 135, 800, 247, 554, 735 } QR = { 255, 969, 557, 819, 953 } QC = { 2, 3, 8, 3, 0 } The color distributions after each of these steps look as follows: after operation 0: 876, 0, 121, 0, 0, 0, 0, 0, 0, 0 after operation 1: 706, 0, 121, 170, 0, 0, 0, 0, 0, 0 after operation 2: 404, 0, 112, 170, 0, 0, 0, 0, 311, 0 after operation 3: 162, 0, 112, 416, 0, 0, 0, 0, 307, 0 after operation 4: 381, 0, 112, 197, 0, 0, 0, 0, 307, 0 The sequence of fingerprints: { 12976, 182806, 100181387, 700427152, 700208371 }.
999999973 99997 250000 923456789 12125 Returns: 728566493
2 12345 12345 2 12345 Returns: 473696403
999999973 999999998 250000 1 111 Returns: 28621520
Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ColorfulStrip with a public method int recolor(int N, int C, int Q, int maxL, int seed) · 97 test cases · 2 s / 256 MB per case