TopCoder Statistics - Problem Statement

Problem Statement

You have probably heard the phrase "the proof is in the pudding". And if you did hear it, you probably thought that it is nonsense. And if you did think that, you were right. It is nonsense, because this is a distorted version of the original saying: "the proof of the pudding is in the eating". The meaning of this phrase is that you should not judge the quality of something before you experience it.

In this problem, we are going to do just that: eat some pudding.

There are N different puddings available. Some are sweet, some are savory. You have three goals:

You want to eat exactly Vall spoons of pudding. If you cannot do that, you will simply eat all the available pudding.
You want to eat at least Vsweet spoons of sweet pudding. If you cannot do that, you will simply eat all the available sweet pudding.
Given the previous two goals, you want to maximize your happiness (as explained below).

The puddings are numbered 0 to N-1. The volume of pudding i is V[i] spoons. The tastiness of pudding i is T[i]. The value S[i] is 1 if the pudding is sweet and 0 if it's savory.

You are allowed to eat as much of each pudding as you like (possibly leaving parts of multiple puddings uneaten). Each spoonful of the pudding increases your happiness by its tastiness. Compute and return the maximum happiness you can obtain by eating the puddings.

Use the pseudocode below to generate the arrays V, T, and S.

V, T, S = Vprefix, Tprefix, Sprefix
state = seed
while length(V) &lt; N:
    state = (state * 1103515245 + 12345) modulo 2^31
    V.append( 1 + (state modulo 10^6) )
    state = (state * 1103515245 + 12345) modulo 2^31
    T.append( 1 + (state modulo 10^6) )
    state = (state * 1103515245 + 12345) modulo 2^31
    S.append( (state div 1024) modulo 2 )

Definition

Class:: ChristmasPudding
Method:: eat
Parameters:: int, long, long, int[], int[], int[], int
Returns:: long
Method signature:: long eat(int N, long Vall, long Vsweet, int[] Vprefix, int[] Tprefix, int[] Sprefix, int seed)
(be sure your method is public)

Notes

Watch out for integer overflows. In particular, we recommend using 64-bit integers when generating the arrays V, T, and S.
The reference solution does not depend on any properties of the pseudorandom generator. It would correctly solve each input that matches the constraints.

Constraints

N will be between 1 and 200,000, inclusive.
0 <= Vsweet <= Vall <= 10^12.
Vprefix, Tprefix and Sprefix will have the same number of elements.
The number of elements in Vprefix will be between 0 and min(100,N), inclusive.
Each element of Vprefix will be between 1 and 1,000,000, inclusive.
Each element of Tprefix will be between 1 and 1,000,000, inclusive.
Each element of Sprefix will be 0 or 1.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

3

300

220

{100, 100, 200}

{4, 5, 7}

{1, 0, 1}

47

Returns: 1880

There are three puddings: 100 spoons of sweet pudding with tastiness 4, 100 spoons of savory pudding with tastiness 5, and 200 spoons of sweet pudding with tastiness 7. We want to eat exactly 300 spoons of pudding, out of which at least 220 should be sweet. The optimal solution is to eat 20 spoons of pudding #0, 80 spoons of pudding #1, and 200 spoons of pudding #2. The total happiness we'll gain will be 20*4 + 80*5 + 200*7 = 1880.
3

390

220

{100, 100, 200}

{4, 5, 7}

{1, 0, 1}

4747

Returns: 2260

The same setting as in Example #0, but now we want to eat a total of 390 spoons of pudding. The optimal solution is to eat 90 spoons of pudding #0, the whole pudding #1, and the whole pudding #2.
3

300

300

{100, 200, 300}

{30, 10, 20}

{0, 1, 0}

42

Returns: 5000

We would like to eat exactly 300 spoons of pudding. That can be done. We would also like to eat at least 300 spoons of sweet pudding. That cannot be done, as there are only 200 spoons of sweet pudding. Hence, we will eat all those 200 spoons of sweet pudding (to satisfy our second goal) and also 100 spoons of savory pudding (to satisfy the first goal). The optimal solution is to eat the whole pudding #0 and the whole pudding #1, leaving pudding #2 untouched.
2

100

0

{47, 10}

{3, 5}

{0, 0}

5

Returns: 191

We want to eat 100 spoons of pudding, but there are only 47 + 10 = 57 spoons of pudding. Thus, we simply eat all the pudding.
20

5000000

3000000

{470}

{407}

{0}

4747

Returns: 3528114042726

Use this example to check whether you are generating the input correctly. You should get the following arrays: V = {470, 262889, 589672, 702899, 546746, 927533, 688636, 441879, 104622, 107313, 754256, 815739, 562274, 293045, 533348, 205407, 310614, 187897, 415160, 748227} T = {407, 911298, 378453, 456644, 573439, 754742, 840985, 980824, 401891, 183530, 590749, 234988, 167431, 118622, 322465, 359744, 581611, 868882, 360165, 944980} S = {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0}
200000

100000000000

20000000000

{}

{}

{}

4247

Returns: 50073587994464801
10

0

0

{}

{}

{}

0

Returns: 0
136117

472714946146

251485969194

{}

{}

{}

1475191316

Returns: 34102160462818070
123741

423107726801

336692860399

{}

{}

{}

175701600

Returns: 31004497907754970
194213

723352089581

440044526

{}

{}

{}

1133040875

Returns: 48463185933176394
193841

796637203185

10937940715

{}

{}

{}

1355395163

Returns: 48428514560530402
164392

250945058219

142755014196

{}

{}

{}

1542245923

Returns: 41069076216309656
147962

266106568449

150466723623

{}

{}

{}

1607036031

Returns: 36919448071980898
183943

389500281983

187264764301

{}

{}

{}

841741944

Returns: 46077457595331972
121276

926805019588

42672792140

{}

{}

{}

539016619

Returns: 30268533345739060
133768

395557670691

212937400666

{}

{}

{}

1085916001

Returns: 33373644786415224
102726

960564318197

252892449071

{}

{}

{}

1438208187

Returns: 25729631151409542
118646

818066845639

663214505771

{}

{}

{}

1516333974

Returns: 29578325386509052
178454

317279332092

132327779051

{}

{}

{}

1123519141

Returns: 44560162030220046
136785

620763152655

528453247696

{}

{}

{}

1340917328

Returns: 34260128339801798
163759

437140329685

286604074126

{}

{}

{}

948917258

Returns: 40970183215335890
169474

687684117327

231247192053

{}

{}

{}

1631517495

Returns: 42267315908803290
153622

613861475281

485972123348

{}

{}

{}

65241470

Returns: 38376997358739292
112320

689544082805

81959898389

{}

{}

{}

1141387247

Returns: 28027245975915200
157008

686390132194

522039808145

{}

{}

{}

1870943262

Returns: 39322273250251488
137917

837168496645

665862444952

{}

{}

{}

1138224035

Returns: 34489411447287362
174448

569549747786

519302325281

{}

{}

{}

1352884873

Returns: 43692106614248336
198728

631455684171

232971995013

{}

{}

{}

1485905588

Returns: 49557059107044880
146575

953302987816

204834672966

{}

{}

{}

758823778

Returns: 36783060836382794
151576

218703878719

26319028241

{}

{}

{}

586949650

Returns: 38105935793569104
185737

626142251204

581298290048

{}

{}

{}

1685176129

Returns: 46500196700892968
104166

486477481641

356484226460

{}

{}

{}

525600088

Returns: 26083470316442236
144272

404015395253

141822919400

{}

{}

{}

179122525

Returns: 36123109058120688
108407

812526977777

221152089150

{}

{}

{}

2124698091

Returns: 26993283560667246
159242

620423449313

11026628440

{}

{}

{}

317163642

Returns: 39844542323084116
112953

166798374634

149988233580

{}

{}

{}

1453170456

Returns: 28417794781735046
173299

50968762131

42423711674

{}

{}

{}

1007175254

Returns: 29282806599898457
183355

412579863353

9118851199

{}

{}

{}

380485713

Returns: 45888169285762412
129679

966599106069

337360471374

{}

{}

{}

1027003835

Returns: 32344708955223118
170301

807009241165

165506080830

{}

{}

{}

1173215853

Returns: 42485331754643092
171131

88351062311

66842400268

{}

{}

{}

1471952835

Returns: 42689780626852574
162944

451463748909

195067303385

{}

{}

{}

1300568894

Returns: 40855324222048704
163966

836849860620

659231331100

{}

{}

{}

599801112

Returns: 41107337957478476
98327

562515435019

501595732057

{}

{}

{}

76784397

Returns: 24580313653036152
146961

621952813739

72869783314

{}

{}

{}

1235357188

Returns: 36715923306551930
192727

539897817867

62287310195

{}

{}

{}

1052781061

Returns: 48150730142646752
136162

364197126897

254119976233

{}

{}

{}

97040700

Returns: 34107673024788660
167034

734861112465

701268459908

{}

{}

{}

102151484

Returns: 41814176888471940
163426

902756106711

316451471744

{}

{}

{}

175604815

Returns: 40861558877608186
191161

593836186758

422979902857

{}

{}

{}

294059352

Returns: 47753156908235718
184689

119339945318

72495601381

{}

{}

{}

2050067571

Returns: 46376328547571050
160406

870780278032

637209777343

{}

{}

{}

1338728498

Returns: 40142737036477900
144014

750631384170

101500890993

{}

{}

{}

441009962

Returns: 36040168838792284
157160

338482607364

293486950908

{}

{}

{}

1546714289

Returns: 39088650740531928
104260

936703077442

818717083008

{}

{}

{}

1830200175

Returns: 26085598753216524
137255

382467889930

349575365778

{}

{}

{}

1150680127

Returns: 34253816914307754
123336

318732146616

254301609206

{}

{}

{}

1286402574

Returns: 30751322903616176
148359

854419510532

349784077724

{}

{}

{}

235240045

Returns: 37212626731007800
110352

526478321837

12887544874

{}

{}

{}

1815666907

Returns: 27659871007835120
149952

483270680235

449313963112

{}

{}

{}

1106908031

Returns: 37610700931028288
128530

331152747372

232657295608

{}

{}

{}

1445927722

Returns: 32072252188417316
155212

550763017664

344727395064

{}

{}

{}

99073865

Returns: 38791948531079620
169808

960668521586

942227007732

{}

{}

{}

1983527925

Returns: 42541692377560432
170868

195671466790

191910006648

{}

{}

{}

1619264208

Returns: 42767655046083112
196756

197752303994

168283097095

{}

{}

{}

334718070

Returns: 49122159552801784
153563

66189823971

31028646908

{}

{}

{}

755530463

Returns: 37654387121277724
168372

6003905151

2681972450

{}

{}

{}

312614420

Returns: 5788745391225504
163425

1671227102

825427543

{}

{}

{}

2144595767

Returns: 1654795597701313
187236

693444476521

558871814508

{}

{}

{}

1720060055

Returns: 46573807185423468
103383

867952919035

452776700011

{}

{}

{}

447805518

Returns: 25905251006764222
170909

992888338604

548317510048

{}

{}

{}

2043547395

Returns: 42739807402453090
147573

913094292232

434194242171

{}

{}

{}

1406159933

Returns: 36948827913475508
146698

344441960259

69039838040

{}

{}

{}

2094311409

Returns: 36801956417693866
133654

715756032521

275328204502

{}

{}

{}

2085040342

Returns: 33443520227686524
193678

102969619291

51667310226

{}

{}

{}

349278773

Returns: 48452328734401622
168846

567898781543

230399520144

{}

{}

{}

1106723769

Returns: 42048955010236822
183489

841203516935

339170481139

{}

{}

{}

488502684

Returns: 45947114882379586
20

5000000

3000000

{470 }

{407 }

{0 }

4747

Returns: 3528114042726

Statistics

Problem Statement for "ChristmasPudding"

Problem Statement

Definition

Notes

Constraints

Examples