TopCoder Statistics - Problem Statement

Problem Statement

Let p[0], p[1], ..., p[N-1] be a permutation of integers between 0 and N-1, inclusive. A binary search tree is a rooted binary tree with an integer value stored at each node. We use the following pseudocode to construct a binary search tree from the permutation p:

Create the root and put p[0] there
For each i in (1, 2, ..., N-1)
	Call insert(root, p[i])

Procedure insert(vertex V, integer X)
	If X &lt; number at V
		If V has left child
			Call insert(left child of V, X)
		Else
			Create new left child of V with value X
	Else
		If V has right child
			Call insert(right child of V, X)
		Else
			Create new right child of V with value X
	End
End

You are given three ints: N, seed and limit. Use the following pseudocode to generate the permutation p (be sure to use 64-bit integers in computations where needed; note that '/' represents integer division and % represents remainder):

X := seed
For each i in (0, 1, ..., N-1)
	p[i] := i
	X := (X * 295397169) % 1073741789;
	If (X * 1000000) / 1073741789 &lt; limit
		X := (X * 295397169) % 1073741789
		// generate j within [0, i]
		j := (X * (i + 1)) / 1073741789
		// j &lt;= i, so p[j] is already initialized
		swap(p[i], p[j])
	End
End

John constructed a binary search tree from the generated permutation using the pseudocode described above. Return the sum of the heights of all nodes in the constructed tree. The height of a node V is the number of nodes in the path from the root to V.

Definition

Class:: BSTConstruction
Method:: sumHeights
Parameters:: int, int, int
Returns:: long
Method signature:: long sumHeights(int N, int seed, int limit)
(be sure your method is public)

Notes

The input is encoded purely for convenience. The intended solution does not rely on any properties of the way it is generated, and will work for any permutation p.

Constraints

N will be between 1 and 250,000, inclusive.
seed will be between 1 and 1,073,741,788, inclusive.
limit will be between 0 and 1,000,000, inclusive.

Examples

10

12345678

500000

Returns: 40

The permutation p here is (9, 1, 4, 3, 2, 5, 6, 7, 8, 0). The binary search tree for this permutation looks as follows: 9 / 1 / \ 0 4 / \ 3 5 / \ 2 6 \ 7 \ 8 The sum of the nodes' heights in this tree is 1+2+3+3+4+4+5+5+6+7=40.
10

87654321

1000000

Returns: 31

Now p is (6, 3, 2, 7, 9, 4, 8, 1, 0, 5).
10

45454545

0

Returns: 55

Here p = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).
1

99988877

12345

Returns: 1
2

744517728

196535

Returns: 3
2

544147260

835994

Returns: 3
3

607505550

718554

Returns: 6
3

341359378

798645

Returns: 6
3

699553589

261395

Returns: 6
3

707164486

502056

Returns: 5
3

141407159

773248

Returns: 6
3

321629483

963647

Returns: 5
4

732757031

688457

Returns: 8
5

458246626

401391

Returns: 15
6

638322508

977252

Returns: 15
7

84412019

304625

Returns: 28
8

265428946

858729

Returns: 23
9

483881841

724700

Returns: 33
18

214122155

190876

Returns: 107
31

837733285

698066

Returns: 152
76

131730492

617259

Returns: 522
88

765188923

42320

Returns: 1953
271

376339101

732298

Returns: 2598
560

374390659

372040

Returns: 6113
819

231194937

841244

Returns: 9273
2059

394536876

839780

Returns: 28696
2823

438894667

201414

Returns: 48949
9426

365057406

277956

Returns: 166426
12604

671374569

851907

Returns: 223621
32191

211152997

958467

Returns: 578313
57220

1017213619

280826

Returns: 1292174
104556

236386757

535032

Returns: 2292476
212544

326451679

173175

Returns: 5700199
32767

546838512

286861

Returns: 630783
32768

55183554

24170

Returns: 1894375
32769

13891897

925380

Returns: 640790
65535

476905701

685694

Returns: 1350832
65536

348546555

379393

Returns: 1477279
65537

210800135

822191

Returns: 1340536
131071

952429936

381888

Returns: 2981363
131072

486840216

648737

Returns: 2903524
131073

948652670

531892

Returns: 2842249
250000

367405061

0

Returns: 31250125000
250000

956261569

1

Returns: 27382003843
250000

123232176

2

Returns: 25394797892
250000

252833734

3

Returns: 29518741385
250000

637044828

4

Returns: 16017126094
250000

317939388

5

Returns: 11826046083
250000

687409832

6

Returns: 24212675860
250000

492413804

7

Returns: 19120480254
250000

152771840

8

Returns: 11492111257
250000

240830683

9

Returns: 15575868799
250000

278283280

10

Returns: 9197958807
250000

311486976

12

Returns: 23098044128
250000

10677981

29

Returns: 12189178181
250000

219870145

37

Returns: 12104888292
250000

897802281

48

Returns: 8874194206
250000

805772159

58

Returns: 7459303349
250000

1000879629

61

Returns: 8766710176
250000

174372600

76

Returns: 4122920321
250000

1026631515

81

Returns: 5029325462
250000

260083601

95

Returns: 3053141054
250000

887099557

174

Returns: 1631617214
250000

181360711

298

Returns: 1611483789
250000

201678168

383

Returns: 667186052
250000

13718606

444

Returns: 613490274
250000

489860150

514

Returns: 613523027
250000

606076511

607

Returns: 474033147
250000

951940344

774

Returns: 327125409
250000

293695324

872

Returns: 333085679
250000

873055500

980

Returns: 293406891
250000

172705365

1669

Returns: 167380619
250000

1054533897

2304

Returns: 174369377
250000

687515450

4847

Returns: 59357680
250000

62893076

10674

Returns: 28599397
250000

684961950

20634

Returns: 18997983
250000

215198615

56917

Returns: 10456393
250000

711446002

79073

Returns: 7696993
250000

665257876

176263

Returns: 6609293
250000

988316966

496098

Returns: 5692583
250000

1045640633

761945

Returns: 5552668
250000

91192267

1000000

Returns: 5805407

Statistics

Problem Statement for "BSTConstruction"

Problem Statement

Definition

Notes

Constraints

Examples