TopCoder Statistics - Problem Statement

Problem Statement

Hero has a list of n tasks he can do. Hero can choose which tasks he will perform and in which order. Each task will take him exactly one day, and on each day he can only work on one of the tasks. The days on which Hero can do these tasks are numbered starting from 0. Each task i has three parameters:

start[i] is the first day on which Hero can do this task,
finish[i] is the last such day, and
cost[i] is the amount of money Hero will earn if he completes this task.

Calculate and return the maximum total amount of money Hero can earn by completing some of the given tasks. You are given the ints: n, A, B, C, modStart, modLen, and modCost. Use the pseudocode below to generate the arrays start, finish, and cost:

x[0] = A
for i from 1 to n*3 - 1: x[i] = (x[i-1] * B + C) % (10^9+7);
for i from 0 to n - 1:
	start[i] = x[i*3] % modStart
	finish[i] = start[i] + (x[i*3+1] % modLen)
	cost[i] = x[i*3+2] % modCost

Definition

Class:: HeroicSchedule
Method:: getmax
Parameters:: int, int, int, int, int, int, int
Returns:: int
Method signature:: int getmax(int n, int A, int B, int C, int modStart, int modLen, int modCost)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator. In the given time limit the reference solution would be able to solve any valid test case with the same bounds on the number of tasks and the range of their parameters.

Constraints

n will be between 1 and 2,000,000, inclusive.
A, B and C will be between 0 and 1,000,000,006, inclusive.
modStart, modLen and modCost will be between 2 and 1000, inclusive.

Examples

2000000

111111

22222

33333

1000

1000

1000

Returns: 1994616
4

3

2

3

4

2

10

Returns: 15

There are four tasks with following start, finish and cost: (3,4,1) (1,2,9) (1,2,3) (1,2,5) One optimal solution looks as follows: On day 0 Hero cannot work on any of the tasks. On day 1 Hero completes the task with cost 5. On day 2 Hero completes the task with cost 9. On day 3 Hero relaxes. On day 4 Hero completes the task with cost 1. The total amount Hero has earned is 5+9+1 = 15.
6

1

2

3

4

3

10

Returns: 17

There are six tasks with following start, finish and cost: (1,3,3) (1,2,5) (1,3,1) (1,2,9) (1,3,3) (1,2,5) The optimal solution is to pick tasks with costs 9, 5 and 3 (any subset with these costs can be completed in some order).
4

3

2

1

2

2

100

Returns: 118
10

5

5

5

9

3

10

Returns: 23
14

385298911

804439326

337276054

9

10

6

Returns: 29
7

839144198

420275280

358582520

11

4

9

Returns: 20
15

667669788

578820906

958641928

5

7

7

Returns: 48
7

31677326

880737565

118254213

11

6

8

Returns: 23
10

225176688

947705345

906794488

4

7

9

Returns: 31
3

303822313

600426537

185347105

9

9

3

Returns: 5
9

706096906

107773399

722351341

5

7

7

Returns: 20
14

616486302

153639988

904427123

7

11

4

Returns: 20
7

992551759

272338785

700030547

8

9

8

Returns: 28
2

202168369

636086820

582808886

1000

1000

1000

Returns: 432
758

904301397

73230906

64184864

156

1000

693

Returns: 259346
598

737535387

632941884

767609454

1000

642

495

Returns: 148215
948

432166786

411608516

67061593

854

100

1000

Returns: 466145
900

824215072

216458023

213987384

1000

1000

234

Returns: 106484
537

447245832

631701886

904856651

753

1000

804

Returns: 209301
72

725007967

787756269

954918376

1000

1000

718

Returns: 23770
128

723691027

15453891

13084915

1000

305

868

Returns: 52209
711

920921826

347129408

391557809

1000

549

1000

Returns: 347979
348

688208699

743033551

814469412

172

285

1000

Returns: 175725
177

325783136

795580866

634897527

842

531

1000

Returns: 83967
680

278568300

897669545

38903948

688

359

959

Returns: 333505
708

829579035

591490544

55072634

464

1000

1000

Returns: 350266
139

331842348

901970291

888592999

1000

1000

390

Returns: 26070
915

521781598

498590439

157591417

1000

1000

863

Returns: 395965
634

366910397

939183139

473812415

515

356

1000

Returns: 328875
232

676183841

717349415

650584497

282

423

1000

Returns: 111636
213

117911902

919942968

583043661

438

1000

1000

Returns: 102146
564

663873187

883116605

238965730

1000

1000

913

Returns: 272350
63

478833767

258923133

490638515

391

909

748

Returns: 24161
622

46057302

201932655

660540941

303

1000

129

Returns: 38350
1104710

784223276

505649086

907437841

1000

1000

1000

Returns: 1992323
1135192

711508104

151993401

706703520

1000

1000

32

Returns: 61900
383142

84984875

539565255

212936928

653

1000

1000

Returns: 1640645
283866

863730796

731621299

640528030

1000

54

1000

Returns: 1050135
805088

82094262

933171038

633496740

1000

352

736

Returns: 991698
1826385

652977774

253849336

958489088

14

1000

970

Returns: 981569
1684228

210872258

650478172

245546215

1000

1000

373

Returns: 742553
1415803

366421741

154431817

568555399

445

253

1000

Returns: 695962
1293193

834406704

450514996

934133215

1000

1000

132

Returns: 261523
726510

928843676

223617986

215724084

333

1000

285

Returns: 377856
978441

583726298

735309840

931299679

1000

215

474

Returns: 573778
1901858

500914306

979004094

3733043

1000

1000

1000

Returns: 1994899
578071

807638388

192999440

776444795

1000

1000

1000

Returns: 1989591
784987

659273486

614466897

10444537

1000

841

1000

Returns: 1833947
1156982

998148449

336646164

704331534

1000

777

1000

Returns: 1771575
786027

570406114

458946933

935508567

758

974

832

Returns: 1434686
917313

134730424

883014482

457083605

1000

267

495

Returns: 625048
808664

944783512

503730814

448002238

1000

630

1000

Returns: 1623574
1964623

734860188

393142047

341618518

47

41

1000

Returns: 86913
1950871

364717713

994716734

693920107

1000

1000

1000

Returns: 1995609
417965

878976012

25965204

78939979

350

844

292

Returns: 346416
1344758

461821162

653330110

592420605

1000

1000

936

Returns: 1865941
891042

145410758

438140338

706374238

1000

659

323

Returns: 532954
201596

200960988

45116354

837198158

1000

538

1000

Returns: 1524414
913855

692303326

764977071

663931887

1000

1000

1000

Returns: 1991032
1955679

387582426

973823288

756785414

238

1000

1000

Returns: 1235459
98658

437968298

297764727

850665079

1000

808

377

Returns: 667203
440254

905498977

800780706

913772662

1000

899

620

Returns: 1168156
460406

290860128

334526858

924310026

392

1000

1000

Returns: 1386356
1644025

834480297

815541715

782793588

38

1000

620

Returns: 641884
1412331

919778979

131636649

368730267

392

1000

441

Returns: 611637
1717736

632861430

903792451

62425640

1000

1000

222

Returns: 441308
1567141

729752120

373792473

728215905

144

1000

599

Returns: 683391
1274845

331650458

883974209

575519384

1000

1000

1000

Returns: 1993674
1536389

320013974

782878733

586080517

187

885

1000

Returns: 1069589
981292

72163379

161998203

554909297

1000

1000

701

Returns: 1396872
1240338

64735983

953866709

841557917

506

613

402

Returns: 447991
795225

171268147

122013212

701159131

1000

1000

1000

Returns: 1991138
2000000

365949393

981432661

630459823

1000

1000

1000

Returns: 1994823
1647576

563661983

323363640

79084580

392

1000

828

Returns: 1149658

Statistics

Problem Statement for "HeroicSchedule"

Problem Statement

Definition

Notes

Constraints

Examples