TopCoder Statistics - Problem Statement

Problem Statement

This problem has a non-standard time limit: 5 seconds.

You are given an undirected tree on N nodes numbered from 0 to N-1. Each node x has some value V[x]. These values are then used to compute the cost of each node. Your task is to find the sum of costs of all nodes in the tree.

The cost of a node x is defined as follows:

Let's say the set of nodes at distance 2 from node x is set S. The cost of this node is the minimum value of abs(V[a]-V[b]) where a and b belong to S and a != b. If size of set S is less than 2, then the cost of node x is 0.

You are given the int N, the int[]s edge and int[]s val, and the ints D, seed. Use the pseudocode below to generate the edges of the tree and the values of all its nodes.

A[0] = seed
for i = 1 to 2*N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2147483648

V = val
for i = size(val) to N-1:
    V[i] = A[i]

E = edge
for i = size(edge) to N-1:
    E[i] = A[N+i] modulo min(i,D)

for i = 1 to N-1:
    the tree contains an edge between i and E[i]

Definition

Class:: TwoDistance
Method:: findMinValue
Parameters:: int, int[], int[], int, int
Returns:: long
Method signature:: long findMinValue(int N, int[] edge, int[] val, int D, int seed)
(be sure your method is public)

Notes

The distance between two nodes is the number of edges in the shortest path between the two nodes.

Constraints

N will be between 3 and 200,000, inclusive.
The number of elements in edge will between 1 and min(N, 100), inclusive.
edge[0] will be equal to -1.
For i > 0, edge[i] will be between 0 and i-1, inclusive.
The number of elements in val will between 0 and min(N, 100), inclusive.
Each element of val will be between 0 and 2,147,483,647, inclusive.
D will be between 1 and N, inclusive.
seed will be between 0 and 2,147,483,647, inclusive.

Examples

3

{-1}

{}

1

1

Returns: 0
10

{-1}

{}

9

340406567

Returns: 6115640787
5

{-1}

{}

3

1088687237

Returns: 1157676346
8

{-1}

{}

4

1660459886

Returns: 1380655965
6

{-1}

{}

1

1259879209

Returns: 1719981821
10

{-1}

{}

2

1038689777

Returns: 1855461438
3

{-1}

{}

1

93172120

Returns: 0
10

{-1}

{}

10

122972108

Returns: 1952280822
10

{-1}

{}

6

106738545

Returns: 4260370422
8

{-1}

{}

7

670614018

Returns: 3498908364
9

{-1}

{}

1

69599489

Returns: 274396664
10

{-1}

{}

2

1972423060

Returns: 2451348436
3

{-1}

{}

1

1612610476

Returns: 0
8

{-1}

{}

7

1332661686

Returns: 2979360316
10

{-1}

{}

3

583901794

Returns: 1012010086
8

{-1}

{}

4

1749880315

Returns: 3981832534
4

{-1}

{}

4

1954873465

Returns: 2860637364
8

{-1}

{}

3

1451280024

Returns: 2892761897
10

{-1}

{}

5

180350466

Returns: 5384184839
5

{-1}

{}

1

401165250

Returns: 1414308619
9

{-1}

{}

4

516254110

Returns: 4756483468
461

{-1}

{}

378

1936115223

Returns: 96423619495
926

{-1}

{}

500

1178070029

Returns: 202452382875
465

{-1}

{}

301

1369162335

Returns: 104136574821
487

{-1}

{}

149

1570136325

Returns: 78216347710
508

{-1}

{}

276

1426819187

Returns: 118099245804
557

{-1}

{}

166

1200838980

Returns: 90495426845
157

{-1}

{}

114

340946300

Returns: 34222909810
327

{-1}

{}

154

1692715496

Returns: 69496568348
623

{-1}

{}

213

726963553

Returns: 126596410296
253

{-1}

{}

18

260041982

Returns: 3753783977
316

{-1}

{}

149

1695733626

Returns: 62404512657
961

{-1}

{}

816

1733957464

Returns: 181691093848
183

{-1}

{}

148

2124200585

Returns: 53700897876
756

{-1}

{}

502

1191221154

Returns: 184370223661
993

{-1}

{}

930

529644521

Returns: 205268079006
475

{-1}

{}

437

15135415

Returns: 90311356315
806

{-1}

{}

606

1024677383

Returns: 181130783295
369

{-1}

{}

335

1684803888

Returns: 82810681332
859

{-1}

{}

102

70023697

Returns: 27599385719
962

{-1}

{}

882

546058814

Returns: 205892518835
146

{-1}

{}

98

1741320430

Returns: 32489407673
958

{-1}

{}

223

591312825

Returns: 129976775467
317

{-1}

{}

284

2142132077

Returns: 64806210215
937

{-1}

{}

686

484188024

Returns: 188046712481
995

{-1}

{}

263

2021501376

Returns: 156840910145
444

{-1}

{}

284

2010758626

Returns: 107124694053
118

{-1}

{}

25

210473515

Returns: 13081490790
606

{-1}

{}

122

1408110021

Returns: 59956041746
75

{-1}

{}

28

1885073143

Returns: 14059207513
537

{-1}

{}

56

1904847206

Returns: 13934350361
152467

{-1}

{}

598

1604057853

Returns: 5122445028
155284

{-1}

{}

210

924207404

Returns: 655245388
155990

{-1}

{}

402

1363639159

Returns: 2351325418
190761

{-1}

{}

624

1923717583

Returns: 4611641483
136911

{-1}

{}

98

471497244

Returns: 177935846
143341

{-1}

{}

792

1263682714

Returns: 9436543384
116426

{-1}

{}

638

1481847913

Returns: 7620483362
101367

{-1}

{}

895

1609939581

Returns: 16733137131
101127

{-1}

{}

962

1081260080

Returns: 19164448979
128813

{-1}

{}

186

1121557538

Returns: 541878674
175501

{-1}

{}

707

705893756

Returns: 5948239309
147238

{-1}

{}

720

1360724985

Returns: 7320442932
105863

{-1}

{}

319

742738741

Returns: 2121114228
107349

{-1}

{}

769

621271337

Returns: 11969923307
109185

{-1}

{}

762

1676614541

Returns: 11150046401
106952

{-1}

{}

578

2088961845

Returns: 7112246312
132838

{-1}

{}

98

2062314804

Returns: 176853042
103869

{-1}

{}

922

6590058

Returns: 17914094607
150197

{-1}

{}

353

501736746

Returns: 1750575227
145611

{-1}

{}

757

712480279

Returns: 8731179428
174224

{-1}

{}

620

776287345

Returns: 4786239585
182896

{-1}

{}

187

421352287

Returns: 368410765
152021

{-1}

{}

485

209063171

Returns: 3480016807
118121

{-1}

{}

134

1228343633

Returns: 337051586
196547

{-1}

{}

162

343208454

Returns: 292422106
178829

{-1}

{}

816

338130485

Returns: 8004124669
126291

{-1}

{}

131

1780504381

Returns: 325735051
154622

{-1}

{}

515

1810711080

Returns: 3791102949
153828

{-1}

{}

703

803455938

Returns: 7188624494
121618

{-1}

{}

911

1969046251

Returns: 15036943835
200000

{-1}

{}

24

247720945

Returns: 8126911
200000

{-1}

{}

20

429697271

Returns: 5446979
200000

{-1}

{}

32

515765927

Returns: 16003479
200000

{-1}

{}

59

292055508

Returns: 35017585
200000

{-1}

{}

33

1085890988

Returns: 12935672
200000

{-1}

{}

78

2008578986

Returns: 79437858
200000

{-1}

{}

1

189741421

Returns: 199999
200000

{-1}

{}

84

589477399

Returns: 88111951
200000

{-1}

{}

8

815831022

Returns: 1799985
200000

{-1}

{}

80

2001366083

Returns: 78360126
200000

{-1}

{}

84

413245182

Returns: 75563455
200000

{-1}

{}

80

2129073202

Returns: 79076775
200000

{-1}

{}

62

534602155

Returns: 39250619
200000

{-1}

{}

19

1824362329

Returns: 5789715
200000

{-1}

{}

3

34238712

Returns: 200000
200000

{-1}

{}

61

1938614387

Returns: 64666267
200000

{-1}

{}

20

1762590669

Returns: 5793694
200000

{-1}

{}

13

598252180

Returns: 3048086
200000

{-1}

{}

58

261018158

Returns: 43179724
200000

{-1}

{}

68

1711781246

Returns: 47169445
200000

{-1}

{}

7

532299219

Returns: 1086428
200000

{-1}

{}

13

1377570056

Returns: 2368706
200000

{-1}

{}

12

322579969

Returns: 2931097
200000

{-1}

{}

1

836046445

Returns: 199999
200000

{-1}

{}

8

601677097

Returns: 2000059
200000

{-1}

{}

1

58817551

Returns: 199999
200000

{-1}

{}

11

1294625958

Returns: 2087483
200000

{-1}

{}

3

1522668472

Returns: 200000
200000

{-1}

{}

2

1827935713

Returns: 400000
200000

{-1}

{}

2

8060810

Returns: 400000
200000

{-1}

{}

1

168162550

Returns: 199999
200000

{-1}

{}

19

824859459

Returns: 5637125
200000

{-1}

{}

3

274225558

Returns: 200000
200000

{-1}

{}

3

1607158210

Returns: 200000
200000

{-1}

{}

9

9093678

Returns: 1182939
200000

{-1}

{}

20

2056675018

Returns: 7964277
200000

{-1}

{}

14

544269641

Returns: 3145282
200000

{-1}

{}

6

750280965

Returns: 466985
200000

{-1}

{}

18

605842738

Returns: 6123020
200000

{-1}

{}

1

1109698634

Returns: 199999
200000

{-1}

{}

4

5523932

Returns: 800002
200000

{-1}

{}

8

691575842

Returns: 2599990
200000

{-1}

{}

3

991214854

Returns: 200000
200000

{-1}

{}

6

1429870216

Returns: 533896
200000

{-1}

{}

6

448890010

Returns: 400010
200000

{-1}

{}

9

1158852336

Returns: 1174484
200000

{-1}

{}

6

728090454

Returns: 400001
200000

{-1}

{}

8

927347082

Returns: 1599990
200000

{-1}

{}

6

955492269

Returns: 400008
200000

{-1}

{}

2

792905415

Returns: 400000
200000

{-1}

{}

2

1076863215

Returns: 400000
200000

{-1}

{}

5

890081051

Returns: 719453
200000

{-1}

{}

7

68293287

Returns: 1342200
200000

{-1}

{}

6

2134292228

Returns: 400010
200000

{-1}

{}

3

489397827

Returns: 200000
200000

{-1}

{}

5

472663883

Returns: 719774
200000

{-1}

{}

5

306133754

Returns: 918970
200000

{-1}

{}

4

1404253578

Returns: 799994
200000

{-1}

{}

6

252650474

Returns: 400011
200000

{-1}

{}

9

1069709549

Returns: 1037866
200000

{-1}

{}

3

1049101440

Returns: 200000
200000

{-1}

{}

8

1836328764

Returns: 1600036
200000

{-1}

{}

8

1783105308

Returns: 1800008
200000

{-1}

{}

2

1602018840

Returns: 400000
200000

{-1}

{}

8

1899342323

Returns: 1600024
200000

{-1}

{}

4

1004141700

Returns: 799994
200000

{-1}

{}

7

867466807

Returns: 1545175
200000

{-1}

{}

9

980119719

Returns: 1114901
200000

{-1}

{}

7

1816409462

Returns: 1714716
200000

{-1}

{}

3

171318735

Returns: 200004
200000

{-1}

{}

1

1076863215

Returns: 199999
3

{-1, 0, 1}

{}

3

2

Returns: 0

Here, we can see that no node will have greater than 1 nodes at a distance of 2. Hence answer is 0.
5

{-1}

{1, 2, 3, 4, 5}

3

4

Returns: 6

Here we will obtain E array as {-1, 0, 1, 2, 2} and hence the edges as 0-1, 1-2, 2-3, 2-4. For node 0, only node 2 is at a distance of 2, hence cost for node 0 is 0. For node 1, it has nodes 3 and 4 at a distance of 2, hence cost for node 1 is abs(V[3]-V[4]) = 1 For node 2, again cost is 0. For node 3, nodes 1 and 4 are at a distance 2, hence cost is abs(V[1]-V[4]) = 3. Similarly for node 4, cost is 2. Hence answer is 1 + 2 + 3 = 6.
8

{-1}

{}

7

670614018

Returns: 3498908364
200000

{-1}

{}

84

589477399

Returns: 88111951

Statistics

Problem Statement for "TwoDistance"

Problem Statement

Definition

Notes

Constraints

Examples