TopCoder Statistics - Problem Statement

Problem Statement

Mojtaba lives in Tehran. Tehran is a city with n squares and n-1 streets such that all of the squares are connected. The streets may have different lengths. The squares are numbered from 0 to n-1. The Grand Mosque of Tehran is at the square number 0.

Tehran can be viewed as a rooted weighted tree. The node number 0 is the root. You are given the description of the tree: for each i > 0 you are given the numbers par[i] and w[i]. Here, par[i] is the parent of node i, and w[i] is the length (in kilometers) of the street from i to par[i]. Note that the tree is numbered in such a way that par[i] < i for all i >= 1.

It's Friday and q people are going to travel from their homes to the Grand Mosque. The people will travel one at a time, in the given order. More precisely, person i+1 will start their journey only after person i parks their car and finishes their journey.

The cars consume 1 liter of fuel per kilometer.

In general, the journey of a person looks as follows: Somewhere in Tehran there are cars parked by the previous travelers, and there may be some fuel available in them. (The Iranians are kind, so they leave their fuel leftovers available for other travelers to the mosque.) Person i starts from the square u[i] where they live. When they start their journey, they are in their car and the car has f[i] liters of fuel. Each person follows the same simple algorithm:

while you are not at the Grand Mosque:
    let X be your current square
    collect all the fuel available in the cars parked at square X, and put all that fuel into your car
    let F be the amount of fuel you now have
    if F &gt;= w[X]:
        travel from X to par[X], which consumes w[X] liters of fuel
        upon arrival to par[X], receive 2*w[X] liters of fuel from the locals
    else:
        park your car at square X
        walk from there to the Grand Mosque

After each person finishes their trip to the mosque, the locals in all the squares will refill all the fuel that was taken from the parked cars. Hence, once somebody parks a car somewhere and leaves L liters of fuel in that car, each future traveler will have those L liters available at that location.

The input is generated pseudorandomly, using parameters A, B, and t Use the following pseudocode:

    par[1] = 0
    for i = 2 to n-1:
        par[i] = Max(0, i - 1 - ((par[i - 1] * A + B) Modulo t) )

    w[1] = B
    for i = 2 to n-1:
        w[i] = (w[i - 1] * A + B) Modulo 10^9

    u[0] = B modulo N
    for i = 1 to q-1:
        u[i] = (u[i - 1] * A + B) Modulo n

    f[0] = B
    for i = 1 to q-1:
        f[i] = (f[i - 1] * A + B) Modulo 10^9

For each person, determine the number of the square where they will park their car. Return the sum of those numbers.

Definition

Class:: InThePathToMosque
Method:: solve
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long solve(int n, int q, int A, int B, int t)
(be sure your method is public)

Notes

The queries are not independent and their order matters. Remember that each person may use fuel that was left in the cars by previous travelers.
The people who reach the mosque in their cars will park next to the Mosque, in the square number 0.

Constraints

n, q, t will each be between 1 and 100,000, inclusive.
A, B will each be between 0 and 10^9 - 1, inclusive.

Examples

5

10

3

2

1

Returns: 5
10

20

1234567

7654321

13

Returns: 29
100000

100000

103

203

6

Returns: 568527503
100000

100000

154651

134845

100

Returns: 964188963
100000

100000

545118445

514512857

100000

Returns: 3444558
7

3

125

787

5

Returns: 3
10

20

1234567

7654321

3

Returns: 29

The edges of the tree: x par[x] w[x] 1 0 7654321 2 0 779768328 3 1 253048297 4 1 84536720 5 2 252454561 6 5 77664408 7 6 922845657 8 6 801879840 9 7 396083601 The first few queries: u[i] f[i] 1 7654321 8 779768328 7 253048297 0 84536720 1 252454561 8 77664408 7 922845657
97882

95512

0

0

47

Returns: 0
98524

99535

0

7

47

Returns: 0
98716

99675

1

0

47

Returns: 0
97813

97108

116202

4431

8579

Returns: 1648807844
95839

95005

502

8541880

1899

Returns: 321491435
96884

96947

112601

24315

3

Returns: 633216690
97895

99923

1425

137

26

Returns: 168878685
95802

97972

463249

98675

11

Returns: 13699710
97743

96790

39986

30758014

3220

Returns: 134755654
96957

99548

817750697

2212

53228

Returns: 58088185
99609

98239

369

643758

112

Returns: 1969632657
98976

97073

680737

16881

37

Returns: 391856163
95611

97177

127993

62787920

2183

Returns: 2084654518
99979

97170

521736534

875092130

1

Returns: 275070586
96731

97834

11206

62

80

Returns: 2185383459
95806

96119

14160893

116963

12

Returns: 2136958226
98636

95003

1305216

9292

2132

Returns: 1730750243
97164

95341

21

16625940

127

Returns: 316060840
99327

98715

267380

4813764

41

Returns: 453585
99451

97771

1146483

394332362

3

Returns: 913084315
96008

95181

6

3

166

Returns: 137410091
99505

99749

25942964

608911

55228

Returns: 816300276
99559

95427

14

13987

1012

Returns: 1370979179
99896

96144

4

516075037

16969

Returns: 668354671
98560

99619

74211

52856888

40247

Returns: 10207353
97008

97885

55774824

61

1

Returns: 63543363
98763

98772

268

180692

553

Returns: 739953175
97156

99442

57914

4

97156

Returns: 587816567
99400

97965

425563

11548

4

Returns: 56353823
99197

97498

6821

225475

9

Returns: 720721996
98490

97953

3

291753

6290

Returns: 17112780
97083

96725

726

26198

30816

Returns: 8699081
97600

95448

31

1

15686

Returns: 38459826
99261

98587

794529

616

638

Returns: 88156220
96390

98465

2042

12034

96390

Returns: 9210222
97564

99544

1

258188223

56

Returns: 2590458982
95350

96487

714564

606006

59704

Returns: 834210952
95493

96838

22148

964105375

1

Returns: 557575191
95596

99589

4102

8186

28613

Returns: 754344725
96003

99188

4932

7

9900

Returns: 578349692
96432

99084

61554

622565

6778

Returns: 104764010
98543

96610

1837

154240309

31

Returns: 2590732132
97728

95858

504

39776059

2169

Returns: 16761674
98232

95666

759419

93163

98232

Returns: 148692368
97511

99096

643551

603924608

693

Returns: 2591141209
98999

96976

7979

1

223

Returns: 2239525876
95874

97767

5

317660

174

Returns: 410293501
95655

96160

87575

11163723

4

Returns: 312727286
96031

99825

6949

14

736

Returns: 1003493444
97841

95738

1707407

8

81

Returns: 545200600
97705

95744

109968450

31170965

97705

Returns: 83885
99270

99255

15386

14960

34254

Returns: 372479461
96595

97674

3

322719420

20448

Returns: 889735219
95788

97741

9158

1407

15872

Returns: 41495575
99243

98891

5196925

783229648

67

Returns: 2621178796
99423

99043

1314

2784262

586

Returns: 610961841
95384

99953

557

1061792

432

Returns: 445219337
96574

99550

111

467445317

22

Returns: 802396045
98665

95282

53795077

838425

10007

Returns: 174014371
98462

98426

4086

279

47823

Returns: 21411148
97216

98322

2

5658

14202

Returns: 14265405
99261

95726

3436

18604

7

Returns: 1108229543
97185

95527

45

236

45708

Returns: 19188967
97430

95048

8

365

3977

Returns: 534890121
96755

97723

4410

3836615

1729

Returns: 416770
95061

95895

1

36815156

64

Returns: 2401560896
95286

99543

287969

7897

75

Returns: 368526153
97271

98239

111131

2

830

Returns: 530353562
95426

99998

999999999

29712

1208

Returns: 2320969207
97074

98444

2450

7360097

5541

Returns: 387368
97422

95244

1

23

4

Returns: 3127720023
98464

98503

15123

329032

28

Returns: 93743350
99414

98768

331

4

160

Returns: 416309925
95577

95143

19

82219

940

Returns: 326119881
99484

98998

548887

41

158

Returns: 46002667
96241

97335

1032143

531530180

26516

Returns: 423232135
98356

98684

716682

1

64856

Returns: 433311474
98342

97813

3284

54176960

7180

Returns: 202843917
95291

99311

328

29241

9

Returns: 1156139036
99856

95278

3441

2715780

1

Returns: 1149555086
97877

96310

565995

61224618

53967

Returns: 771780852
96208

97176

425

10019

86

Returns: 680463322
96888

97311

3127678

27555

27

Returns: 23435868
95913

96199

727693227

381420

95913

Returns: 141051711
99438

96687

50276130

3

5504

Returns: 208392
99015

99987

719713156

744428896

4535

Returns: 907274833
98841

97677

150640

304

22

Returns: 268447
97242

99892

5005

439

14

Returns: 58152747
98049

99366

202

420

2

Returns: 2856429
97426

98654

27689233

20609748

21

Returns: 1535030200
97133

97810

304

724

3

Returns: 1079990316
96778

96624

4162209

37843

4286

Returns: 572855952
99856

96228

14

737

11301

Returns: 249971512
95705

96754

1517308

154475

13255

Returns: 874575835
97583

98063

664372595

6

23326

Returns: 2142478773
95962

95709

220374

33026007

143

Returns: 1601814518
97612

97526

58988109

286

6

Returns: 146411579
98745

99129

252

838

12268

Returns: 365989710
99996

97691

372102

181856641

94

Returns: 240902573
95340

95240

6379850

13332801

107

Returns: 441258

Statistics

Problem Statement for "InThePathToMosque"

Problem Statement

Definition

Notes

Constraints

Examples