PopChartDominance
SRM 832 · 2022-06-24 · by misof
Problem Statement
Recently, the artist Kate Bush made history: thanks to her song being featured in Stranger Things her old song became a #1 hit in the charts, a stunning 44 years since her previous #1 hit. This inspired us to write a problem about pop charts statistics.
Who were the dominant artists in the sixties? How can we tell? One necessarily imprecise but really simple way of measuring dominance within a time interval is to look at the artist's first and last #1 hit within that period. The farther apart they are, the longer the artist was popular in that period.
We will consider a period of N days, numbered from 0 to N-1. You will be given a sequence A[0..N-1]: for each day i, A[i] is the ID of the artist who was on top of the charts that day.
Let set(A) denote the set of distinct values that appear in A.
A half-open interval [lo, hi) consists of all i such that lo <= i < hi.
Given an interval [lo, hi) and an artist x, the dominance of artist x within [lo, hi) is calculated as follows:
- If there is no t in [lo, hi) such that A[t] = x, the dominance is 0.
- If there is one or more such t, let tmax and tmin be the largest and smallest among them. Then, the dominance is (tmax-tmin).
(Note that an artist must have a #1 hit on at least two distinct days within the given interval in order to have a positive dominance. A single day still only yields zero dominance.)
You will be given two arrays L and H, each of length Q.
For each valid i, consider the interval [ L[i], H[i] ). For each artist in set(A), calculate their dominance within this interval. Let ans[i] be the sum of those dominances.
Let TOTAL be the sum of (i+1)*ans[i] over all i. Return TOTAL modulo (10^9 + 7).
----------------------------------------------------------
As we need to keep the input size small, the input will be generated pseudorandomly. Please follow the pseudocode below to generate the arrays A, L, H.
(The pseudocode takes the provided prefixes of A, L, H. The rest of A is filled with pseudorandom values from [0,Alimit) and the rest of L and H is filled with pseudorandom queries whose lengths are between minQL and maxQL, inclusive.)
state = seed
A = Aprefix
while length(A) < N:
state = (state * 1103515245 + 12345) modulo 2^31
A.append( state modulo Alimit )
L = Lprefix
H = Hprefix
while length(L) < Q:
state = (state * 1103515245 + 12345) modulo 2^31
ql = minQL + (state modulo (maxQL-minQL+1))
state = (state * 1103515245 + 12345) modulo 2^31
lo = state modulo (N-ql+1)
L.append(lo)
H.append(lo+ql)
Notes
- The reference solution does not depend on the assumption that the input is pseudorandom.
Constraints
- N will be between 1 and 300,000, inclusive.
- Q will be between 1 and 300,000, inclusive.
- Aprefix will have between 0 and min(100, N) elements, inclusive.
- Each element of Aprefix will be between 0 and Alimit-1, inclusive.
- Alimit will be between 1 and 300,000, inclusive.
- Lprefix will have between 0 and min(100, Q) elements, inclusive.
- Hprefix will have the same number of elements as Lprefix.
- For each valid index i we will have 0 <= Lprefix[i] < Hprefix[i] <= N.
- minQL and maxQL will satisfy 1 <= minQL <= maxQL <= N.
- seed will be between 0 and 2^31 - 1, inclusive.
7
2
{10, 20, 30, 40, 50, 60, 70}
100
{0, 3}
{7, 5}
1
7
47
Returns: 0
Seven days, two queries. As A = {10, 20, 30, 40, 50, 60, 70}, there was no artist with more than one day on top of the charts. Thus, for each query interval and each artist their dominance is zero. This means that ans[0] = ans[1] = 0 and TOTAL = 1*ans[0] + 2*ans[1] = 0.
9
5
{10, 20, 10, 30, 10, 20, 10, 40, 30}
100
{0, 0, 5, 0, 3}
{9, 9, 9, 5, 8}
1
9
47
Returns: 71
Again, the entire A, L, H are given, nothing is pseudorandom. Each of the first two queries asks about the entire array A. In this array, artist 10 has dominance 6, artist 20 has dominance 4, artist 30 has dominance 5 and artist 40 has dominance 0. The third query asks about the segment {20, 10, 40, 30}. Everyone' dominance is zero. The fourth query asks about {10, 20, 10, 30, 10}. Artist 10 has dominance 4. The fifth query asks about {30, 10, 20, 10, 40}. Again, only artist 10 has a non-zero dominance: 2. Thus, TOTAL is 1*(6+4+5+0) + 2*(6+4+5+0) + 3*(0+0+0+0) + 4*(4+0+0+0) + 5*(2+0+0+0) = 71.
30
10
{4, 7, 5, 18}
20
{0, 5}
{30, 18}
3
10
47
Returns: 189
Most of A, L, H are generated pseudorandomly. For reference, their correct contents are given below. A = { 4, 7, 5, 18, 8, 5, 18, 11, 8, 13, 10, 7, 16, 17, 6, 3, 0, 1, 2, 15, 12, 13, 10, 15, 16, 13, 18, 15, 0, 9 } L = { 0, 5, 1, 21, 5, 13, 13, 25, 13, 21 } H = { 30, 18, 6, 24, 14, 20, 18, 28, 22, 28 } Below is the full list of situations when some artist has a positive dominance: in interval [0,30) artist 0 has dominance 12 in interval [0,30) artist 5 has dominance 3 in interval [0,30) artist 7 has dominance 10 in interval [0,30) artist 8 has dominance 4 in interval [0,30) artist 10 has dominance 12 in interval [0,30) artist 13 has dominance 16 in interval [0,30) artist 15 has dominance 8 in interval [0,30) artist 16 has dominance 12 in interval [0,30) artist 18 has dominance 23 in interval [1,6) artist 5 has dominance 3 in interval [21,28) artist 13 has dominance 4 in interval [21,28) artist 15 has dominance 4
300000
300000
{}
100000
{}
{}
1
300000
4747
Returns: 34267726
300000
300000
{}
1
{}
{}
2
2
424242
Returns: 149685
The array A contains 300,000 zeros. Each query has length 2. The answer to each query is 1. Thus, TOTAL = 1+2+...+300000 = 45000150000. Remember to compute TOTAL modulo 10^9 + 7 and watch out for integer overflows.
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PopChartDominance with a public method int count(int N, int Q, vector<int> Aprefix, int Alimit, vector<int> Lprefix, vector<int> Hprefix, int minQL, int maxQL, int seed) · 66 test cases · 2 s / 256 MB per case