TopCoder Statistics - Problem Statement

Problem Statement

Bear Limak and deer Evil have N cookies with various flavors. Cookies are numbered 0 through N-1. Bears and deer are natural enemies so Limak and Evil don't want to eat together. They decided to divide cookies by playing a simple game. They will alternately take one cookie. Limak starts. The game ends when there are no more cookies.

As you can guess, bears and deer prefer different flavors. The i-th cookie has value A[i] for Limak and value B[i] for Evil. We define Limak's score as sum of A[i] of his cookies and Evil's score as sum of B[i] of his cookies.

Limak knows his opponent's strategy. Evil always takes a cookie with the biggest B[i]. In case of tie he takes a cookie with the biggest A[i] (from cookies with the biggest B[i]).

Limak wants to maximize the difference between his and Evil's score. Help him and find the maximum possible value of L-E, where L denotes Limak's score and E denotes Evil's score.

The description of cookies is provided in the form of a pseudorandom generator. You are given the ints N, R, C, D, A_MAX, and B_MAX. As defined above, N is the number of cookies. The flavors of cookies are generated by the pseudocode below. Watch out for integer overflow when implementing it.

for i between 0 and N-1, inclusive:
    R = (C * R + D) modulo (10^9+7);
    A[i] = R % A_MAX;
    R = (C * R + D) modulo (10^9+7);
    B[i] = R % B_MAX;

Note that A[i] will be between 0 and A_MAX-1, inclusive. And B[i] will be between 0 and B_MAX-1, inclusive.

Definition

Class:: BearEats
Method:: getDifference
Parameters:: int, int, int, int, int, int
Returns:: long
Method signature:: long getDifference(int N, int R, int C, int D, int A_MAX, int B_MAX)
(be sure your method is public)

Notes

N will be between 1 and 200,000, inclusive.
R, C and D will be between 0 and 1,000,000,000, inclusive.
A_MAX and B_MAX will be between 1 and 1,000,000,000, inclusive.

Constraints

Examples

3

4

4

1

11

15

Returns: -3

A = {6,2,4}, B = {9,14,4}. Limak should take the second cookie - (2,14). It has value A[i]=2 for him. Evil wants a cookie with the bigest B[i] so he takes (6,9). Limak can take the last cookie (4,4) and his score is 2+4=6. Evil's score is 9 so difference is 6-9 = -3. Limak can't achieve a better difference.
5

2

3

0

14

40

Returns: 4

A = {6, 12, 10, 6, 12}, B = {18, 2, 18, 2, 18}. Optimal start for Limak is to take the cookie (12,18). There are two cookies with the biggest B[i] now and Evil takes the one with bigger A[i] - (10, 18). Limak takes (6,18), Evil (12,2) and Limak (6,2). Limak has score 12+6+6 = 24. Evil has score 18+2 = 20.
4

938593858

538591850

384025833

885912358

3405

Returns: 1452754016

A = {224250140, 715072124, 737687500, 357608742}, B = {2859, 908, 1144, 2749}. Evil wants first cookie and the last one and Limak should allow him to do it. Limak ends with score 737687500 + 715072124 and Evil with 2859 + 2749.
200000

999998741

999997411

64592149

57

75

Returns: 462494
1

1

1

1

1

1

Returns: 0

empty test, it can be changed into example
1

0

0

0

1

1

Returns: 0
1

0

879491958

347382474

1000000000

1000000000

Returns: 347382474
8

916279866

316131776

776320464

689999266

796683188

Returns: 251788502
25

444191428

72719855

47355995

346604533

289119891

Returns: 1032895387
50

941224390

226247247

574563146

802120366

375694523

Returns: 9008571427
95

896348377

272236780

942212127

938093213

141892658

Returns: 32740543854
169

16947122

185428134

678023159

130393326

40726126

Returns: 6414507346
400

629312780

452582649

121563549

793892321

534698133

Returns: 61709426136
1000

558184187

275240084

29561951

593294737

681824432

Returns: 56412941039
1111

127599558

8098051

761487632

416252622

118386824

Returns: 131952971315
5678

103809973

806239226

984008966

13155268

839599524

Returns: -992627072878
10123

861561821

289798548

350217919

10562837

589076867

Returns: -1269526228463
56000

925256458

824979543

893493112

294862664

903811998

Returns: -5621033962646
150000

565740495

358098766

860677532

944499571

259005519

Returns: 42663017828957
200000

182845746

765584359

730637516

333466660

745024241

Returns: -5988581555549
199999

706789544

957914300

129393803

615539340

458345295

Returns: 18726882918071
199998

992345332

290770975

95390555

180004791

362835131

Returns: -3979289218062
199997

598187997

553432398

94098241

844509433

346784978

Returns: 42812316199108
199996

508432463

490139536

556728175

205744224

726735583

Returns: -15128833982272
199995

569623820

114343216

735227440

12168532

845247225

Returns: -36066418313177
199994

46513121

965026040

426601311

65546821

726074614

Returns: -25216517116208
199993

918816141

840475475

988351228

202640860

988914261

Returns: -33852728681405
199992

548111849

891754738

487524854

666932791

555289516

Returns: 17705917884853
199991

532980510

233958779

735610061

792250373

152297778

Returns: 46845533991927
200000

1000000000

1

0

1000000000

1000000000

Returns: 0
200000

999999999

1

0

1000000000

1000000000

Returns: 0
200000

570435228

816316804

752129074

1

249129567

Returns: -12404429273742
200000

678234341

944941777

973613947

448212684

1

Returns: 20634685588966
200000

991334295

756768663

266408164

1

1

Returns: 0
199999

454326193

810640770

187636186

23

952303984

Returns: -45525705605444
199999

186998103

941903934

534624557

905427590

37

Returns: 64981761838449
199999

26347406

575009880

314592696

139

496

Returns: -14383115
199998

430261032

477392532

148731543

199

389790740

Returns: -17640654327206
199998

978528755

558047535

886301849

586806672

328

Returns: 39044312478947
199998

306760239

666971135

843837941

1666

2909

Returns: -20066200
199997

526963227

59277185

328949915

1053

483346237

Returns: -23421161559711
199997

374009974

868878190

542786184

217885535

638

Returns: 15667470128964
199997

960498652

845979297

982445935

2568

8506

Returns: -232965214
199996

189441268

996568330

509101530

1390

566474655

Returns: -25401670575455
199996

864613468

663964980

26336690

135519739

207

Returns: 9975528165454
199996

248664130

985197003

749593755

32479

3132

Returns: 2282115043
199995

50609411

48462942

109739509

5980

228430895

Returns: -10820912203325
199995

421757867

641556687

173340594

788514687

2477

Returns: 53823403419500
199995

297399641

895409183

265714803

9551

52653

Returns: -1913826441
199994

147798638

283133991

692901435

4057

665729998

Returns: -27677628142355
199994

81865779

655784550

588792904

641216066

2745

Returns: 41483319289869
199994

856956875

94638421

18711600

10490

78837

Returns: -3153007586
199993

934443401

459278045

745627516

1608

186273646

Returns: -8891987971472
199993

303255445

909472946

969116300

913324909

10537

Returns: 66320148174254
199993

741067705

271950155

164882659

166436

201055

Returns: 2421422995
199992

455086587

362172507

967557702

15245

765318690

Returns: -32033824920989
199992

385424595

399048920

811767508

289831270

5411

Returns: 20655781036132
199992

190848866

428352101

33655850

195852

61541

Returns: 11590287702
199991

243390263

537267663

827768971

18649

577958465

Returns: -25560371539612
199991

741995138

445587374

479298852

846363952

13422

Returns: 59627334382473
199991

724631774

834147645

624452010

118270

435617

Returns: -12941447658

Statistics

Problem Statement for "BearEats"

Problem Statement

Definition

Notes

Constraints

Examples