TopCoder Statistics - Problem Statement

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) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    A.append( state modulo Alimit )

L = Lprefix
H = Hprefix
while length(L) &lt; 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)

Definition

Class:: PopChartDominance
Method:: count
Parameters:: int, int, int[], int, int[], int[], int, int, int
Returns:: int
Method signature:: int count(int N, int Q, int[] Aprefix, int Alimit, int[] Lprefix, int[] Hprefix, int minQL, int maxQL, int seed)
(be sure your method is public)

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.

Examples

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.
1

300000

{47}

48

{}

{}

1

1

24

Returns: 0
281529

272048

{}

15624

{}

{}

134967

268669

1660249968

Returns: 235752872
282858

290170

{}

3

{}

{}

8

502

39237771

Returns: 359213997
296729

299449

{}

1899

{}

{}

219

24315

142868263

Returns: 124659221
288381

282260

{}

3448

{}

{}

26

137

420679459

Returns: 488660086
281889

288951

{}

6167

{}

{}

124

213

473072173

Returns: 468903391
295332

283653

{}

3220

{}

{}

2212

199646

2078532398

Returns: 504308817
280230

288439

{}

6227

{}

{}

11

8072

1087222470

Returns: 756056247
289776

288285

{}

30

{}

{}

6

37

2046595582

Returns: 887575107
295635

296275

{}

14181

{}

{}

497

1069

1043761029

Returns: 911123692
276925

281336

{}

11206

{}

{}

19

45788

586949650

Returns: 74011395
293934

295726

{}

3655

{}

{}

1

483

1778417307

Returns: 624788840
272200

282099

{}

1

{}

{}

21

129890

863925910

Returns: 836284161
295660

295325

{}

62494

{}

{}

5

26

200513682

Returns: 762210638
298755

290383

{}

143

{}

{}

11647

64566

380485713

Returns: 901151681
279919

271765

{}

211724

{}

{}

170709

202679

346617440

Returns: 468280755
288447

286097

{}

1130

{}

{}

3288

15034

2101334812

Returns: 913211945
289584

274576

{}

4

{}

{}

9374

237905

1866519440

Returns: 714427721
296531

288478

{}

74211

{}

{}

257008

263400

490178290

Returns: 430992681
294738

278032

{}

3404

{}

{}

15

17124

1977954749

Returns: 516315575
279069

290907

{}

137306

{}

{}

503

553

1647993519

Returns: 837560686
272243

293672

{}

15

{}

{}

163420

216057

879909240

Returns: 214445777
293998

290726

{}

4

{}

{}

174460

212379

1546714289

Returns: 635229364
297888

273565

{}

7

{}

{}

26343

183387

242563618

Returns: 793737859
282840

290772

{}

386

{}

{}

726

26198

1912313258

Returns: 232667970
295418

284432

{}

1136

{}

{}

1

32808

1964529467

Returns: 457556461
287046

284348

{}

406

{}

{}

59

638

1445927722

Returns: 83619954
286303

283959

{}

195

{}

{}

12094

198874

1983527925

Returns: 121849673
290217

288294

{}

56

{}

{}

7

43

1765314531

Returns: 682691500
271974

277353

{}

22148

{}

{}

2341

72924

312614420

Returns: 783055964
288356

282750

{}

1

{}

{}

195665

238616

526066028

Returns: 125223418
286752

283123

{}

9

{}

{}

54664

215982

750893228

Returns: 937892788
299608

291794

{}

63950

{}

{}

49139

207358

1406159933

Returns: 782328148
284174

294540

{}

104

{}

{}

39107

69476

2094311409

Returns: 82259736
280913

291297

{}

12

{}

{}

48607

187253

127702674

Returns: 75879472
282928

290470

{}

5

{}

{}

628

99310

268214787

Returns: 449606846
279401

293581

{}

63

{}

{}

1

7979

1010397418

Returns: 758808091
290490

288165

{}

2485

{}

{}

33708

82353

454791749

Returns: 911938666
277831

297675

{}

37

{}

{}

36

87575

398097787

Returns: 832957340
274127

289303

{}

6949

{}

{}

13023

188624

1489995248

Returns: 464438555
295186

272952

{}

1232

{}

{}

81

1210

1371506773

Returns: 56006817
295190

293442

{}

13961

{}

{}

228611

230227

1774309568

Returns: 403490712
293847

286077

{}

1

{}

{}

25728

224672

434271713

Returns: 658599314
284388

295341

{}

9

{}

{}

30940

229196

1433250621

Returns: 889396788
295813

294727

{}

58

{}

{}

249031

271557

513342065

Returns: 679855978
277518

276507

{}

1

{}

{}

74453

85889

1241566301

Returns: 731778523
272378

271538

{}

557

{}

{}

91

432

1586454074

Returns: 865991714
299558

282146

{}

22

{}

{}

18109

158131

1286708360

Returns: 326089553
283820

273630

{}

15045

{}

{}

134650

260980

194969798

Returns: 575921991
293725

288512

{}

47823

{}

{}

30658

212615

103084142

Returns: 970811917
282881

276250

{}

14202

{}

{}

3436

18604

281126873

Returns: 765071518
285504

278742

{}

5

{}

{}

236

45708

1274375336

Returns: 105683104
270194

273741

{}

1

{}

{}

46809

228765

1427747666

Returns: 527335349
283122

299861

{}

3

{}

{}

180736

281858

32134090

Returns: 287750142
273581

270673

{}

561

{}

{}

2

65976

1646888126

Returns: 113093476
299263

295004

{}

22641

{}

{}

458

111131

162392144

Returns: 327525829
299054

272138

{}

830

{}

{}

13641

31569

386253728

Returns: 109870314
278297

297949

{}

14311

{}

{}

50

7188

127958513

Returns: 126930620
270998

288845

{}

80

{}

{}

4

15198

1787838088

Returns: 769056057
293169

283862

{}

20

{}

{}

241215

282534

1128032479

Returns: 651686916
290983

297039

{}

18

{}

{}

4

160

588301709

Returns: 775651074

Statistics

Problem Statement for "PopChartDominance"

Problem Statement

Definition

Notes

Constraints

Examples