TopCoder Statistics - Problem Statement

Problem Statement

You are given an integer sequence A and an int N that is a power of 2. All elements of A are between 0 and N-1, inclusive.

You can now choose an integer B which is between 0 and N-1, inclusive. This integer determines a new sequence C defined as follows: For each valid i, C[i] = (A[i] xor B).

Given the sequence C, we will count the pairs of indices (i,j) such that both i<j and C[i]<C[j]. Compute and return the largest result we can obtain.

You are given the int N. You are also given ints sz, A0, A1, P, Q, and R. Use the following pseudocode to generate the sequence A:

A[0] = A0;
A[1] = A1;
for (i = 2; i &lt; sz; i++) {
    A[i] = (A[i - 2] * P + A[i - 1] * Q + R) modulo N;
}

Definition

Class:: XorSequence
Method:: getmax
Parameters:: int, int, int, int, int, int, int
Returns:: long
Method signature:: long getmax(int N, int sz, int A0, int A1, int P, int Q, int R)
(be sure your method is public)

Notes

Watch out for integer overflow when generating the sequence A.

Constraints

N will be between 2 and 1,073,741,824 (2^30), inclusive.
N will be a power of 2.
sz will be between 2 and 131,072, inclusive.
A0 will be between 0 and N-1, inclusive.
A1 will be between 0 and N-1, inclusive.
P will be between 0 and N-1, inclusive.
Q will be between 0 and N-1, inclusive.
R will be between 0 and N-1, inclusive.

Examples

4

6

3

2

0

1

3

Returns: 8

Using the provided pseudocode you should compute that A={3,2,1,0,3,2}. For B=3 we then get C={0,1,2,3,0,1}. For this C there are 8 pairs (i,j) such that i<j and C[i]<C[j]. These are the 8 pairs: (0,1), (0,2), (0,3), (0,5), (1,2), (1,3), (2,3), and (4,5). No other choice of B produces more than 8 pairs.
8

8

2

5

3

1

4

Returns: 13

A={2,5,7,2,3,5,2,5}.
8

7

3

0

1

2

4

Returns: 12

A={3,0,7,2,7,4,3}.
32

15

7

9

11

2

1

Returns: 60

A={7,9,0,4,9,31,2,26,11,21,4,16,13,11,6}.
131072

131072

7

7

1

0

0

Returns: 0

All elements of A are equal to 7. Regardless of the value of B you choose, all elements in C will be equal as well. Thus, the number of pairs we seek is always zero.
131072

131070

411

415

398

463

9191

Returns: 4302679760
2

23237

0

1

1

1

1

Returns: 60000516
2

39088

0

0

0

1

1

Returns: 190993739
2

88857

0

1

1

0

0

Returns: 986945806
4

77309

3

0

2

0

3

Returns: 231918
4

89167

3

2

3

2

1

Returns: 1490844376
4

20187

2

2

3

0

3

Returns: 50944418
8

62560

0

4

3

4

7

Returns: 611563100
8

122220

0

1

3

7

0

Returns: 2904599040
8

71377

3

6

2

7

4

Returns: 636941577
16

58857

10

15

8

5

7

Returns: 811936911
16

34010

7

11

13

8

15

Returns: 271158549
16

11876

4

12

11

15

15

Returns: 27426963
32

15831

8

19

23

22

4

Returns: 60704836
32

54222

0

4

26

29

23

Returns: 689109087
32

3316

16

21

19

14

24

Returns: 2663474
64

93536

22

60

31

49

13

Returns: 1944260080
64

107601

44

9

9

18

2

Returns: 2826781441
64

121491

9

40

18

16

60

Returns: 1214830
128

117223

7

84

77

66

16

Returns: 3395264068
128

12702

49

72

123

69

100

Returns: 38810080
128

107016

124

67

79

79

66

Returns: 2385952933
256

88175

230

214

50

134

143

Returns: 1322467
256

111398

212

2

242

250

231

Returns: 1559403
256

118379

105

50

217

225

215

Returns: 3460992309
512

66660

484

225

431

125

213

Returns: 1107107700
512

83269

93

276

409

342

272

Returns: 1728583700
512

6205

393

420

432

212

45

Returns: 37206
1024

6798

1009

446

31

270

10

Returns: 11539368
1024

42524

241

521

803

354

550

Returns: 451325477
1024

55968

505

407

538

193

23

Returns: 780238969
2048

69513

2018

1972

1349

49

431

Returns: 1207414090
2048

83281

1554

1879

1132

274

1122

Returns: 999251
2048

117323

1151

764

670

1794

195

Returns: 2463457
4096

128046

3571

2536

936

3943

793

Returns: 4067046584
4096

104175

3249

3009

1470

2236

482

Returns: 2499749
4096

6718

555

1722

2858

1460

2844

Returns: 154111
8192

30679

6318

678

2195

3892

655

Returns: 235322340
8192

50338

4045

1133

7189

5755

5499

Returns: 634045519
8192

74319

8186

6723

690

7194

5783

Returns: 1708907
16384

22511

8019

7730

9076

8314

15057

Returns: 314997
16384

55291

7543

2806

4835

14862

13760

Returns: 764681939
16384

48582

16306

6749

7294

6486

8969

Returns: 1214049
32768

41039

13088

161

5359

20402

18154

Returns: 421607032
32768

53611

94

19585

2365

29842

14215

Returns: 719137701
32768

82682

21028

18438

25778

16414

10508

Returns: 2149173
65536

101732

7256

35171

64873

36347

31520

Returns: 2589979486
65536

18504

14443

22184

30654

7132

41092

Returns: 536018
65536

70701

537

54387

20930

63086

38728

Returns: 2191033
131072

36501

109138

39607

102847

129932

47848

Returns: 334216715
131072

61209

77572

75585

130707

67821

103774

Returns: 937269886
131072

10789

110364

112993

126149

88307

65886

Returns: 29323639
262144

26132

82911

116533

189130

134711

207986

Returns: 170900013
262144

19669

202024

73626

259981

137367

117363

Returns: 97013187
262144

63578

182580

1151

24380

121966

127601

Returns: 1080601
524288

63875

239846

496912

163874

451750

216338

Returns: 2298542
524288

76851

106815

442987

457652

41007

502193

Returns: 1479625939
524288

9646

103391

436409

84855

417173

362362

Returns: 23356375
1048576

91779

473106

716006

473690

359171

87112

Returns: 2107785803
1048576

103658

526445

914373

518461

906625

961401

Returns: 2694148763
1048576

32253

441433

783509

222800

752027

619605

Returns: 261190755
2097152

78104

120758

1902757

424307

1258590

1523126

Returns: 1534510930
2097152

39356

1387182

1931867

919834

983251

1930694

Returns: 389943508
2097152

82356

105276

1931722

134539

1008776

1525019

Returns: 1700164757
4194304

17129

1154369

3414095

1370132

4175056

2275954

Returns: 376464
4194304

108928

3270148

808158

2706464

3675345

3031576

Returns: 2980756601
4194304

21798

1427623

802910

3177609

2989884

702147

Returns: 119402057
8388608

78041

1756222

8072406

6308638

4783712

1312935

Returns: 3588295
8388608

61034

3899247

6143093

847643

6185596

1626886

Returns: 937933666
8388608

129486

1585149

2481511

2401139

7843290

5899221

Returns: 4198006577
16777216

124886

12316608

15872055

5195334

14390720

2831852

Returns: 5743064
16777216

27556

13139628

13037266

8978890

6192982

14009228

Returns: 1210858
16777216

52905

12452636

10616111

4808965

7162433

12113675

Returns: 703696087
33554432

51228

5055055

24500018

4076553

29569054

28870035

Returns: 658916155
33554432

8259

7999364

21952421

32904880

3709719

8937174

Returns: 17128086
33554432

62430

29965327

4491418

26954306

28948306

24419931

Returns: 3057294
67108864

129757

2039061

20973433

26387614

38355021

58184493

Returns: 4215470349
67108864

101539

9473982

45883049

26428929

32820034

16534985

Returns: 2581534956
67108864

128867

47014651

31532420

47058389

41892104

56837979

Returns: 4159801255
134217728

87886

99795636

37567740

82520939

103896185

109943942

Returns: 1941095362
134217728

9314

78498903

96689833

105380346

37806443

2026143

Returns: 21967246
134217728

95640

128876634

12093312

98496221

103318638

80736330

Returns: 2296262792
268435456

119713

28776728

203411920

117087010

124609890

259363844

Returns: 6103442
268435456

23369

199306420

157655022

110393030

135478538

106698167

Returns: 1283141
268435456

130905

42160526

45342980

134117197

97485514

145507365

Returns: 4297138847
536870912

114480

315481588

201615006

106909386

80153207

512601482

Returns: 3285936560
536870912

46831

234509654

218390512

374034076

114397746

424607778

Returns: 1263847
536870912

95087

83516024

192928180

243918267

96285383

272907717

Returns: 2269374345
1073741824

55603

36266296

718206558

364153791

927385200

1025549166

Returns: 776465378
1073741824

75297

758394104

663511744

571829859

956502497

901793550

Returns: 1424836191
1073741824

128310

801886897

197964852

557346079

787187461

767431394

Returns: 4123854671
1073741824

131072

141249309

513499077

416719421

828088045

61207686

Returns: 4299378726
1073741824

131072

119807212

142515129

931390265

185615422

252678648

Returns: 4307304476
1073741824

131072

577928307

682156641

273016423

309510929

918370446

Returns: 4302246661
1073741824

131072

154713196

267126153

350909134

672633457

73784074

Returns: 4297750710
1073741824

131072

1065826258

544920208

668334123

1069555354

533192428

Returns: 4308041296
1073741824

131072

572887291

824841385

195822307

502566606

998089151

Returns: 4308727464
1073741824

131072

88290473

332291048

736408473

402812554

336428167

Returns: 4303797142
1073741824

131072

378354907

438109454

871417947

843356151

742057538

Returns: 4308466087
1073741824

131072

1055996694

667131450

272818362

815699454

329838551

Returns: 7730676
1073741824

131072

877240978

12966311

230373985

83991765

560959061

Returns: 4305215358
1073741824

131072

908917065

660318756

733464388

596623620

10114781

Returns: 3800398
1073741824

131072

495913967

926205879

664386029

824862537

340906702

Returns: 4302784285
1073741824

131072

699357358

616247682

936126865

319063882

727409046

Returns: 4307818075
1073741824

131072

457493799

190401742

188268665

744363708

486480932

Returns: 4303526778
1073741824

131072

447080738

892736284

59424212

687166731

953061983

Returns: 4302368912
1073741824

131072

400986268

784111720

464484347

997792476

782174671

Returns: 4300295192
1073741824

131072

195490932

641718009

745168924

431938598

603991801

Returns: 3800404
1073741824

131072

530618987

708021763

15296663

211088964

647866309

Returns: 4308948388
1073741824

131072

1043157327

34446352

45935033

482352141

1061055358

Returns: 4305149253
1073741824

131072

105541521

1028347170

522227221

718914071

583474038

Returns: 4302659536
1073741824

131070

411

415

398

463

9191

Returns: 4306787059
1024

12343

45

44

344

987

354

Returns: 37992737
1073741824

131071

1073741820

1073741821

1073741822

1073741823

1073741819

Returns: 4310026488
1073741824

100000

99999

999999999

999999999

999999999

999999999

Returns: 2507856950
536870912

130000

0

1234

6

7

3456

Returns: 4235601672
131072

130070

411

415

398

463

9121

Returns: 4244241556
1073741824

131072

114

514

1919

810

5235

Returns: 4308500415
1073741824

12332

1312

123123

32412

123213

123123321

Returns: 38324183
1073741824

100000

41

18467

6334

26500

19169

Returns: 5697514
1073741824

131072

1073741823

1073741823

1073741823

1073741823

1073741823

Returns: 1908859790
1073741824

2

536870912

0

1

1

1

Returns: 1
1073741824

131072

5646

123

897

564

321

Returns: 4308316187
1073741824

131072

1073741820

1000000000

111132

1073741823

1073741823

Returns: 4317984034
1073741824

131072

2

3

5

7

11

Returns: 4309347817
1073741824

131072

1073741820

1073741821

1073741822

1073741823

1073741819

Returns: 4310137573

Statistics

Problem Statement for "XorSequence"

Problem Statement

Definition

Notes

Constraints

Examples