TopCoder Statistics - Problem Statement

Problem Statement

You have two lists of numbers, X and Y, each containing exactly N elements. You can optionally apply any number of circular shifts to each list. A circular shift means removing the last element from a list and re-inserting it before the first element. For example, {1, 2, 3} would become {3, 1, 2}, and {3, 1, 2} would become {2, 3, 1}. After you apply any circular shifts, the final score is calculated as:
X[0]*Y[0] + X[1]*Y[1] + ... + X[N-1]*Y[N-1]
You are given ints Z0, A, B and M. Generate a list Z of length 2*N, using the following recursive definition:
Z[0] = Z0 MOD M
Z[i] = (Z[i-1]*A+B) MOD M (note that Z[i-1]*A+B may overflow a 32-bit integer)
Then, generate lists X and Y, each of length N, using the following definitions:
X[i] = Z[i] MOD 100
Y[i] = Z[i+N] MOD 100
Return the maximal final score you can achieve.

Definition

Class:: CircularShifts
Method:: maxScore
Parameters:: int, int, int, int, int
Returns:: int
Method signature:: int maxScore(int N, int Z0, int A, int B, int M)
(be sure your method is public)

Notes

In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.

Constraints

N will be between 1 and 60,000, inclusive.
Z0, A and B will each be between 0 and 1,000,000,000, inclusive.
M will be between 1 and 1,000,000,000, inclusive.

Examples

5

1

1

0

13

Returns: 5

Both lists contain only ones, so no matter how many shifts you perform, the score will always be 5.
4

1

1

1

20

Returns: 70

The lists are {1, 2, 3, 4} and {5, 6, 7, 8}. The maximal score is achieved by not making any shifts.
10

23

11

51

4322

Returns: 28886

The lists are (23, 4, 95, 20, 17, 94, 63, 44, 13, 96) and (87, 54, 13, 18, 61, 24, 17, 94, 53, 2).
1000

3252

3458736

233421

111111111

Returns: 2585408
60000

123121

289347322

231211112

989333333

Returns: 149230883
141

96478

24834

74860

92112

Returns: 419992
927

93846

49470

42066

57059

Returns: 2329410
1521

61983

56293

84434

40219

Returns: 4785918
1994

78455

79773

80504

86195

Returns: 5989576
762

64868

98272

84883

74677

Returns: 1941974
206

54944

20813

48180

75505

Returns: 564055
493

56315

90892

4816

17358

Returns: 1350968
539

45735

51566

73422

73587

Returns: 1733319
804

93916

36799

49452

74973

Returns: 2175089
1673

85650

68326

89940

91474

Returns: 4273672
9350

9503874

7934487

3660674

9947931

Returns: 24452943
12383

3177214

6367106

230718

3890580

Returns: 39400484
2900

1473997

737814

2537759

1515009

Returns: 7227768
6350

7342650

671941

4465920

2756759

Returns: 15742264
2053

2837520

6155327

1755869

4178847

Returns: 5254351
4421

4712083

6143442

455285

6739796

Returns: 11831901
4798

8616880

581985

4503375

4393427

Returns: 12102396
3587

8578390

9148218

7416478

9360337

Returns: 11501579
10009

5981726

7875134

9845667

9287798

Returns: 32165158
4888

520918

3952503

374250

2251693

Returns: 12177442
29869

480267264

700158560

186907370

101317025

Returns: 100104580
24389

54366000

52744399

262355769

149347619

Returns: 60145494
25002

255976755

851296105

233609756

9005748

Returns: 86055746
37189

625830472

614736655

56836707

286757301

Returns: 92100493
21718

60582090

423205571

282533858

257245028

Returns: 52797008
23195

67339838

394395522

320535084

366449188

Returns: 53315208
25786

52914674

625353717

19821201

119739950

Returns: 50764481
39558

661662853

96144446

15411304

228498317

Returns: 97413529
32044

569484867

345500226

140045599

109619693

Returns: 79637049
28022

30409811

177881381

37008727

41137821

Returns: 69366720
29334

630621287

332159797

212745023

573536474

Returns: 72385631
22668

240433222

247733867

19713925

4052300

Returns: 81652190
31023

391478473

850491801

627063956

1223087

Returns: 79941738
31286

103224787

187403654

416256135

607775024

Returns: 76751912
38896

34011645

1919855

605884981

576562403

Returns: 95718891
26302

390261564

538891127

28997471

64843688

Returns: 66031783
31060

17358017

653543126

364046519

36608759

Returns: 75900072
37086

103122732

38019877

179748135

196860003

Returns: 91073204
20123

91928513

331593639

51236636

102268792

Returns: 51176817
30771

163802970

641095724

656986384

389135192

Returns: 71550880
30900

335820632

108815032

31276039

29405638

Returns: 77952301
22324

33105629

294800337

324321873

531393061

Returns: 54920715
31111

368448196

178232023

297776876

15223009

Returns: 76762612
33357

682725196

378652478

299499821

216617202

Returns: 83822978
24423

584626106

58607284

359859277

106573311

Returns: 60416874
36972

308338165

7727024

10609552

106827339

Returns: 92779386
22223

525967579

458821134

57432195

51939890

Returns: 57012237
31783

414964579

276806027

43441714

20306474

Returns: 80817915
26962

167513088

239866588

326655872

852565272

Returns: 65879568
32678

32340432

127246233

17575818

635303

Returns: 108475784
58112

404246286

530848205

372200319

393637904

Returns: 143828916
60000

498749784

3780189

85140424

347198873

Returns: 148323057
53775

603655533

518703805

204561350

816297774

Returns: 135807777
59174

125212492

71337471

144663616

42102959

Returns: 145859544
58027

41165086

386991347

777508091

480937230

Returns: 142261079
52363

199788199

221896902

159343738

213317105

Returns: 129118042
50750

125396414

3481964

152792896

53096858

Returns: 122741932
60000

618617586

33056644

119166504

45698101

Returns: 147817674
53245

722363414

271950255

664488831

850358812

Returns: 131677605
60000

50881521

377976100

628551

6157622

Returns: 150382832
60000

3252

3458736

233421

111111111

Returns: 147727327
60000

96478

24834

74860

92112

Returns: 188580624
60000

384657439

384657439

999999994

928475895

Returns: 148791040
59987

59987

59987

59987

59987

Returns: 0
60000

3123

12312

12312

131232

Returns: 189076504
60000

23

11

51

4322

Returns: 187999552
60000

1

2

3

929458781

Returns: 147563238
60000

1

1

3

100

Returns: 197010000
60000

666131342

6661313

123456789

999999999

Returns: 148248144
60000

999999999

123

123

999999999

Returns: 149874710
60000

1000000000

999999993

113

999999923

Returns: 148983228
60000

3

433

53

323453

Returns: 196800249
59999

999999999

888888889

777777779

987654322

Returns: 147963665
59796

981234597

856977717

543111211

241313333

Returns: 147041218
60000

1000000000

1000000000

1000000000

1000000000

Returns: 0
60000

32452345

1451234

14321324

312453425

Returns: 151052350
60000

1

2

3

999999937

Returns: 148366844
60000

123

99347

23423

3242357

Returns: 147970298
60000

2137189

2173892

12371892

121782378

Returns: 144974976
59987

3252

3458736

233421

111111111

Returns: 147820211
60000

57

239

17

999999991

Returns: 147934006
60000

431

432414315

123432543

1000000000

Returns: 351380944
60000

1

65536

1

999999937

Returns: 147688589
60000

999999999

999999998

999999997

999999996

Returns: 157932344
60000

239

239017

23917

1000003

Returns: 150191075
60000

3

999999131

999999113

999999137

Returns: 147629209
55555

213

343432

53432

999999999

Returns: 137593876
60000

389

1572869

6291473

12582917

Returns: 147357663

Statistics

Problem Statement for "CircularShifts"

Problem Statement

Definition

Notes

Constraints

Examples