Statistics

Problem Statement for "ETSums"

Problem Statement

You are given a rooted tree on N nodes. The nodes are numbered from 0 to N-1 with node 0 being the root. Each node x has three associated values: its parent P[x], its cost C[x], and its timestamp T[x].

You are given the parents and the costs of all nodes. The timestamps correspond to the order in which a depth-first search discovers the nodes of the tree. Formally, the timestamps can be computed using the following pseudocode: 

counter = 1
define dfs(current_id):
    T[ current_id ] = counter
    counter += 1
    for each child_id such that P[child_id] = current_id:
        dfs(child_id)

// note that the children of a node are always processed in increasing order of their IDs
// in order to compute all timestamps, call:
dfs(0)

For each node x we will now define a new number: it's ET value, denoted ET[x].

Let the nodes on the (unique) simple path from the root to x be the nodes 0 = v0, v1, v2, ..., vk = x. The value ET[x] is defined as follows:

ET[x] = sumi C[vi] * i^T[x]

The sum is over all valid indices i, that is, 0 <= i <= k. The symbol ^ denotes exponentiation (i to the power of T[x]).

Find and return the sum of ET-values of all nodes in the tree, modulo 10^9+7.


In order to keep the test data small, the input for this problem is given in the following form: You are given the int N, the int[]s parent and cost, and the ints D, seed, and MX. Use the following pseudocode to generate the arrays P and C: 

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

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

C = cost
for i = size(cost) to N-1:
	C[i] = A[N+i] modulo MX

Definition

Class:
ETSums
Method:
findSumOfETSums
Parameters:
int, int[], int[], int, int, int
Returns:
int
Method signature:
int findSumOfETSums(int N, int[] parent, int[] cost, int D, int seed, int MX)
(be sure your method is public)

Notes

  • Be careful to avoid potential overflows.
  • The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

  • N will be between 1 and 200,000, inclusive.
  • The number of elements in parent will between 1 and min(N, 100), inclusive.
  • parent[0] will be equal to -1, representing the fact that node 0 has no parent.
  • For each i, parent[i] will be less than i.
  • Number of elements in cost will between 0 and min(N, 100), inclusive.
  • Each element of cost will be between 0 and MX-1, inclusive.
  • D will be between 1 and 200,000, inclusive.
  • seed will be between 0 and 2,147,483,647, inclusive.
  • MX will be between 1 and 1,000,000,000, inclusive.

Examples

  1. 2

    {-1}

    {}

    114575

    304655178

    1000000000

    Returns: 125568817

  2. 5

    {-1}

    {}

    48772

    383616353

    1000000000

    Returns: 77279466

  3. 7

    {-1}

    {}

    190629

    682098057

    1000000000

    Returns: 328481118

  4. 2

    {-1}

    {}

    7775

    685975157

    1000000000

    Returns: 654132376

  5. 22

    {-1}

    {}

    4784

    1269929825

    1000000000

    Returns: 447446552

  6. 36

    {-1}

    {}

    31932

    467588830

    1000000000

    Returns: 855958868

  7. 8

    {-1}

    {}

    78537

    618002001

    1000000000

    Returns: 198573533

  8. 19

    {-1}

    {}

    86918

    1083678843

    1000000000

    Returns: 35954019

  9. 39

    {-1}

    {}

    38506

    652839596

    1000000000

    Returns: 727362031

  10. 8

    {-1}

    {}

    161868

    1891466096

    1000000000

    Returns: 72479019

  11. 20

    {-1}

    {}

    96263

    1674724049

    1000000000

    Returns: 921594447

  12. 9

    {-1}

    {}

    36991

    835051398

    1000000000

    Returns: 299949887

  13. 35

    {-1}

    {}

    177068

    253751719

    1000000000

    Returns: 82720520

  14. 20

    {-1}

    {}

    91757

    56514242

    1000000000

    Returns: 311515048

  15. 14

    {-1}

    {}

    194328

    1536994396

    1000000000

    Returns: 301207800

  16. 35

    {-1}

    {}

    196221

    748244296

    1000000000

    Returns: 785809969

  17. 2

    {-1}

    {}

    131545

    1362590559

    1000000000

    Returns: 255534602

  18. 27

    {-1}

    {}

    175467

    42244722

    1000000000

    Returns: 934647092

  19. 11

    {-1}

    {}

    6504

    1172109979

    1000000000

    Returns: 865684508

  20. 34

    {-1}

    {}

    144965

    1484816172

    1000000000

    Returns: 188308845

  21. 196565

    {-1}

    {}

    45895

    775865589

    1000000000

    Returns: 772665504

  22. 195554

    {-1}

    {}

    108325

    1940985235

    1000000000

    Returns: 580659599

  23. 180337

    {-1}

    {}

    48153

    1047774984

    1000000000

    Returns: 664309792

  24. 181785

    {-1}

    {}

    197489

    1485008335

    1000000000

    Returns: 265115661

  25. 193296

    {-1}

    {}

    166466

    620811552

    1000000000

    Returns: 359331718

  26. 193474

    {-1}

    {}

    53968

    951768109

    1000000000

    Returns: 235517991

  27. 195290

    {-1}

    {}

    33792

    1081745524

    1000000000

    Returns: 36394747

  28. 183579

    {-1}

    {}

    179694

    1125252224

    1000000000

    Returns: 933298599

  29. 182001

    {-1}

    {}

    24712

    1472948137

    1000000000

    Returns: 828907307

  30. 194105

    {-1}

    {}

    102643

    1886326457

    1000000000

    Returns: 703712474

  31. 193144

    {-1}

    {}

    123492

    1116601988

    1000000000

    Returns: 459639267

  32. 181972

    {-1}

    {}

    28607

    2000212165

    1000000000

    Returns: 349288487

  33. 195723

    {-1}

    {}

    160717

    1491667182

    1000000000

    Returns: 374470888

  34. 196115

    {-1}

    {}

    106986

    1489398184

    1000000000

    Returns: 599720118

  35. 180071

    {-1}

    {}

    23620

    344556846

    1000000000

    Returns: 902653876

  36. 193819

    {-1}

    {}

    76858

    275413463

    1000000000

    Returns: 441520548

  37. 180392

    {-1}

    {}

    88502

    1166868834

    1000000000

    Returns: 143222395

  38. 197026

    {-1}

    {}

    172325

    209552603

    1000000000

    Returns: 284972374

  39. 195423

    {-1}

    {}

    120464

    973281343

    1000000000

    Returns: 627874631

  40. 180422

    {-1}

    {}

    29832

    155904035

    1000000000

    Returns: 616268625

  41. 195083

    {-1}

    {}

    178720

    1815023882

    1000000000

    Returns: 620931138

  42. 189577

    {-1}

    {}

    189992

    555670314

    1000000000

    Returns: 981344903

  43. 191439

    {-1}

    {}

    98989

    1312046806

    1000000000

    Returns: 17539511

  44. 193189

    {-1}

    {}

    146600

    1697330378

    1000000000

    Returns: 48026091

  45. 180080

    {-1}

    {}

    11929

    1217723135

    1000000000

    Returns: 557354180

  46. 181413

    {-1}

    {}

    189770

    1305211359

    1000000000

    Returns: 276170063

  47. 180665

    {-1}

    {}

    104628

    119887591

    1000000000

    Returns: 636978499

  48. 180896

    {-1}

    {}

    81898

    1998829856

    1000000000

    Returns: 334350200

  49. 195281

    {-1}

    {}

    115811

    1695015153

    1000000000

    Returns: 900285521

  50. 186772

    {-1}

    {}

    3384

    1582553146

    1000000000

    Returns: 755299236

  51. 186277

    {-1}

    {}

    80114

    792467643

    1000000000

    Returns: 943814817

  52. 199469

    {-1}

    {}

    89334

    351958574

    1000000000

    Returns: 904278557

  53. 184194

    {-1}

    {}

    78326

    762539680

    1000000000

    Returns: 415479948

  54. 191667

    {-1}

    {}

    70962

    1231353581

    1000000000

    Returns: 388405379

  55. 193222

    {-1}

    {}

    48231

    1703602797

    1000000000

    Returns: 780230559

  56. 198819

    {-1}

    {}

    171588

    860081201

    1000000000

    Returns: 729016363

  57. 197449

    {-1}

    {}

    157564

    1986844002

    1000000000

    Returns: 899733063

  58. 192591

    {-1}

    {}

    68747

    1273507743

    1000000000

    Returns: 352279161

  59. 195222

    {-1}

    {}

    147593

    645858157

    1000000000

    Returns: 595228691

  60. 187272

    {-1}

    {}

    12516

    258703899

    1000000000

    Returns: 729118377

  61. 189394

    {-1}

    {}

    69525

    1734317987

    1000000000

    Returns: 724267660

  62. 197263

    {-1}

    {}

    157163

    1859341419

    1000000000

    Returns: 57022162

  63. 193235

    {-1}

    {}

    158976

    130768895

    1000000000

    Returns: 512301761

  64. 190070

    {-1}

    {}

    193590

    731127055

    1000000000

    Returns: 346494862

  65. 191482

    {-1}

    {}

    83220

    475931742

    1000000000

    Returns: 39359988

  66. 182878

    {-1}

    {}

    84239

    1476444000

    1000000000

    Returns: 263230699

  67. 190976

    {-1}

    {}

    122601

    867075258

    1000000000

    Returns: 882151846

  68. 196168

    {-1}

    {}

    43377

    2004518888

    1000000000

    Returns: 783221126

  69. 192183

    {-1}

    {}

    138238

    827605671

    1000000000

    Returns: 559593922

  70. 195124

    {-1}

    {}

    171653

    970633729

    1000000000

    Returns: 21430959

  71. 197438

    {-1}

    {}

    111957

    150016523

    1000000000

    Returns: 758981511

  72. 196396

    {-1}

    {}

    126878

    281807537

    1000000000

    Returns: 402974203

  73. 196203

    {-1}

    {}

    1999

    2107198754

    1000000000

    Returns: 31870623

  74. 199060

    {-1}

    {}

    171826

    552035524

    1000000000

    Returns: 526783952

  75. 196648

    {-1}

    {}

    51401

    1446717362

    1000000000

    Returns: 316449726

  76. 186621

    {-1}

    {}

    76763

    211587627

    1000000000

    Returns: 725071727

  77. 181840

    {-1}

    {}

    181495

    337657227

    1000000000

    Returns: 731463243

  78. 187707

    {-1}

    {}

    80206

    1099226773

    1000000000

    Returns: 181521907

  79. 193117

    {-1}

    {}

    53310

    1889441858

    1000000000

    Returns: 454927273

  80. 190685

    {-1}

    {}

    147611

    988497740

    1000000000

    Returns: 198658832

  81. 192260

    {-1}

    {}

    193559

    566462510

    1000000000

    Returns: 400689030

  82. 187689

    {-1}

    {}

    158949

    1130490963

    1000000000

    Returns: 576413919

  83. 186067

    {-1}

    {}

    32737

    1718873251

    1000000000

    Returns: 662774485

  84. 187271

    {-1}

    {}

    22306

    1281586877

    1000000000

    Returns: 734539662

  85. 182976

    {-1}

    {}

    105542

    6997870

    1000000000

    Returns: 54482205

  86. 199648

    {-1}

    {}

    11094

    1535275087

    1000000000

    Returns: 934056180

  87. 192719

    {-1}

    {}

    10898

    1223178129

    1000000000

    Returns: 800904505

  88. 198295

    {-1}

    {}

    29964

    835176537

    1000000000

    Returns: 375148826

  89. 198973

    {-1}

    {}

    40720

    1258829633

    1000000000

    Returns: 678352073

  90. 199818

    {-1}

    {}

    104917

    1356661202

    1000000000

    Returns: 19312576

  91. 191669

    {-1}

    {}

    198183

    2010757405

    1000000000

    Returns: 795249251

  92. 181723

    {-1}

    {}

    153541

    1941292723

    1000000000

    Returns: 124186338

  93. 183005

    {-1}

    {}

    163316

    1806434480

    1000000000

    Returns: 725897584

  94. 199101

    {-1}

    {}

    37611

    1256184982

    1000000000

    Returns: 414961389

  95. 183497

    {-1}

    {}

    2024

    81875497

    1000000000

    Returns: 598705848

  96. 181834

    {-1}

    {}

    100304

    548386447

    1000000000

    Returns: 175937419

  97. 181757

    {-1}

    {}

    99876

    36394329

    1000000000

    Returns: 585820133

  98. 195666

    {-1}

    {}

    53939

    74129481

    1000000000

    Returns: 145396431

  99. 185565

    {-1}

    {}

    138323

    598132718

    1000000000

    Returns: 42511922

  100. 184904

    {-1}

    {}

    81154

    1184546405

    1000000000

    Returns: 152232391

  101. 189159

    {-1}

    {}

    43

    521755374

    1000000000

    Returns: 416077573

  102. 188800

    {-1}

    {}

    100

    823025680

    1000000000

    Returns: 182289790

  103. 185696

    {-1}

    {}

    79

    920508279

    1000000000

    Returns: 240134580

  104. 182773

    {-1}

    {}

    14

    1008688611

    1000000000

    Returns: 919810813

  105. 190820

    {-1}

    {}

    100

    605021878

    1000000000

    Returns: 779494655

  106. 185716

    {-1}

    {}

    20

    228033024

    1000000000

    Returns: 187569692

  107. 195789

    {-1}

    {}

    74

    1518999845

    1000000000

    Returns: 306895305

  108. 189177

    {-1}

    {}

    30

    1167734122

    1000000000

    Returns: 184646254

  109. 191212

    {-1}

    {}

    46

    663095561

    1000000000

    Returns: 247047828

  110. 195152

    {-1}

    {}

    53

    943779493

    1000000000

    Returns: 186985700

  111. 185205

    {-1}

    {}

    53

    1432859692

    1000000000

    Returns: 804973311

  112. 189978

    {-1}

    {}

    94

    1619729806

    1000000000

    Returns: 487067580

  113. 181970

    {-1}

    {}

    75

    2142398679

    1000000000

    Returns: 91080167

  114. 186975

    {-1}

    {}

    20

    135073917

    1000000000

    Returns: 233466370

  115. 191016

    {-1}

    {}

    45

    479650322

    1000000000

    Returns: 304738850

  116. 194200

    {-1}

    {}

    6

    934317721

    1000000000

    Returns: 213664733

  117. 196100

    {-1}

    {}

    52

    355954463

    1000000000

    Returns: 345398174

  118. 189453

    {-1}

    {}

    53

    773661563

    1000000000

    Returns: 642008216

  119. 184034

    {-1}

    {}

    27

    233325109

    1000000000

    Returns: 778217011

  120. 181692

    {-1}

    {}

    38

    1899845639

    1000000000

    Returns: 172650706

  121. 187657

    {-1}

    {}

    58

    1402421882

    1000000000

    Returns: 206598472

  122. 198851

    {-1}

    {}

    95

    1997624454

    1000000000

    Returns: 133418229

  123. 199697

    {-1}

    {}

    51

    912784708

    1000000000

    Returns: 520029573

  124. 195256

    {-1}

    {}

    9

    802596872

    1000000000

    Returns: 568422408

  125. 188040

    {-1}

    {}

    8

    2058195600

    1000000000

    Returns: 442500971

  126. 180756

    {-1}

    {}

    50

    96481530

    1000000000

    Returns: 37090786

  127. 197972

    {-1}

    {}

    22

    1678096578

    1000000000

    Returns: 356880381

  128. 199935

    {-1}

    {}

    81

    1044931331

    1000000000

    Returns: 247176348

  129. 187446

    {-1}

    {}

    37

    967652255

    1000000000

    Returns: 977684020

  130. 189704

    {-1}

    {}

    26

    1540580900

    1000000000

    Returns: 932551397

  131. 189506

    {-1}

    {}

    26

    1651989128

    1000000000

    Returns: 128446842

  132. 191102

    {-1}

    {}

    88

    1964886800

    1000000000

    Returns: 974717054

  133. 190804

    {-1}

    {}

    21

    1499433465

    1000000000

    Returns: 463802512

  134. 186162

    {-1}

    {}

    31

    2014826696

    1000000000

    Returns: 320561672

  135. 185885

    {-1}

    {}

    54

    481598530

    1000000000

    Returns: 661717074

  136. 182754

    {-1}

    {}

    50

    2022471547

    1000000000

    Returns: 517834020

  137. 197887

    {-1}

    {}

    26

    1352910213

    1000000000

    Returns: 276539702

  138. 185529

    {-1}

    {}

    1

    1032772765

    1000000000

    Returns: 584543134

  139. 195180

    {-1}

    {}

    61

    1839820528

    1000000000

    Returns: 954697906

  140. 199655

    {-1}

    {}

    76

    1952422982

    1000000000

    Returns: 931466453

  141. 199639

    {-1}

    {}

    66

    1802235195

    1000000000

    Returns: 333322731

  142. 181945

    {-1}

    {}

    36

    965686221

    1000000000

    Returns: 761644432

  143. 180159

    {-1}

    {}

    18

    872230501

    1000000000

    Returns: 92215729

  144. 198988

    {-1}

    {}

    49

    2060558757

    1000000000

    Returns: 50559759

  145. 193396

    {-1}

    {}

    50

    833993386

    1000000000

    Returns: 950334187

  146. 190761

    {-1}

    {}

    83

    981646968

    1000000000

    Returns: 40125603

  147. 189350

    {-1}

    {}

    59

    1041016009

    1000000000

    Returns: 834587972

  148. 180950

    {-1}

    {}

    68

    578947970

    1000000000

    Returns: 671443440

  149. 186491

    {-1}

    {}

    55

    2034058612

    1000000000

    Returns: 912047118

  150. 185129

    {-1}

    {}

    75

    2081419824

    1000000000

    Returns: 750207180

  151. 193359

    {-1}

    {}

    21

    1551162904

    1000000000

    Returns: 367317845

  152. 189389

    {-1}

    {}

    16

    1861595385

    1000000000

    Returns: 180843214

  153. 185041

    {-1}

    {}

    48

    31948495

    1000000000

    Returns: 570431498

  154. 182488

    {-1}

    {}

    91

    2025615740

    1000000000

    Returns: 975387754

  155. 187969

    {-1}

    {}

    68

    1523370914

    1000000000

    Returns: 902191002

  156. 191447

    {-1}

    {}

    41

    1984906203

    1000000000

    Returns: 908284396

  157. 184138

    {-1}

    {}

    17

    706903299

    1000000000

    Returns: 635321396

  158. 188213

    {-1}

    {}

    68

    878115671

    1000000000

    Returns: 139574818

  159. 198085

    {-1}

    {}

    21

    1198241675

    1000000000

    Returns: 499828914

  160. 188188

    {-1}

    {}

    66

    372123693

    1000000000

    Returns: 1822421

  161. 184440

    {-1}

    {}

    76

    767137520

    1000000000

    Returns: 411899821

  162. 186574

    {-1}

    {}

    64

    230075056

    1000000000

    Returns: 430659877

  163. 192760

    {-1}

    {}

    70

    1415219274

    1000000000

    Returns: 702744872

  164. 187309

    {-1}

    {}

    32

    1625398184

    1000000000

    Returns: 488875418

  165. 190491

    {-1}

    {}

    48

    2128301960

    1000000000

    Returns: 66364434

  166. 182534

    {-1}

    {}

    89

    1503495658

    1000000000

    Returns: 104448481

  167. 187547

    {-1}

    {}

    34

    885904429

    1000000000

    Returns: 316059557

  168. 190512

    {-1}

    {}

    90

    996027704

    1000000000

    Returns: 309368766

  169. 185293

    {-1}

    {}

    17

    508498255

    1000000000

    Returns: 319773645

  170. 181970

    {-1}

    {}

    37

    869031515

    1000000000

    Returns: 553843671

  171. 186178

    {-1}

    {}

    68

    734446802

    1000000000

    Returns: 859929781

  172. 197302

    {-1}

    {}

    45

    1805878399

    1000000000

    Returns: 662005694

  173. 192188

    {-1}

    {}

    8

    1696119264

    1000000000

    Returns: 23485219

  174. 193102

    {-1}

    {}

    66

    378929103

    1000000000

    Returns: 554107061

  175. 183847

    {-1}

    {}

    76

    163105453

    1000000000

    Returns: 199924306

  176. 183859

    {-1}

    {}

    79

    377518418

    1000000000

    Returns: 922117353

  177. 186947

    {-1}

    {}

    41

    1997010281

    1000000000

    Returns: 481871772

  178. 196314

    {-1}

    {}

    29

    1686089733

    1000000000

    Returns: 257636797

  179. 194888

    {-1}

    {}

    66

    408035462

    1000000000

    Returns: 753019052

  180. 198783

    {-1}

    {}

    14

    1659075385

    1000000000

    Returns: 641076553

  181. 190007

    {-1}

    {}

    87

    317811244

    1000000000

    Returns: 957115004

  182. 189486

    {-1}

    {}

    65

    582811182

    1000000000

    Returns: 58417136

  183. 188087

    {-1}

    {}

    48

    1824857850

    1000000000

    Returns: 577657796

  184. 190061

    {-1}

    {}

    97

    673532145

    1000000000

    Returns: 255715937

  185. 183134

    {-1}

    {}

    72

    714060798

    1000000000

    Returns: 88321220

  186. 187512

    {-1}

    {}

    11

    781509235

    1000000000

    Returns: 455178113

  187. 180802

    {-1}

    {}

    42

    1244684279

    1000000000

    Returns: 634665394

  188. 198400

    {-1}

    {}

    20

    872151019

    1000000000

    Returns: 247643151

  189. 197691

    {-1}

    {}

    39

    424292298

    1000000000

    Returns: 707440214

  190. 195907

    {-1}

    {}

    1

    989736302

    1000000000

    Returns: 268134773

  191. 191776

    {-1}

    {}

    77

    654553667

    1000000000

    Returns: 251321818

  192. 183483

    {-1}

    {}

    77

    1409567692

    1000000000

    Returns: 626527508

  193. 195618

    {-1}

    {}

    72

    1985976077

    1000000000

    Returns: 607199186

  194. 181063

    {-1}

    {}

    62

    1593919405

    1000000000

    Returns: 723200320

  195. 196470

    {-1}

    {}

    71

    159374580

    1000000000

    Returns: 761499975

  196. 180759

    {-1}

    {}

    20

    1712283117

    1000000000

    Returns: 288496535

  197. 193790

    {-1}

    {}

    10

    1890402613

    1000000000

    Returns: 581933581

  198. 185056

    {-1}

    {}

    24

    1219441398

    1000000000

    Returns: 609579757

  199. 189380

    {-1}

    {}

    24

    1101173979

    1000000000

    Returns: 764422423

  200. 4

    {-1,0,1,2}

    {4,3,3,4}

    1

    0

    5

    Returns: 405

    This tree is a path 0 -> 1 -> 2 -> 3. All values of P and C are given. The values of T are {1,2,3,4}. The ET values look as follows: ET[0] = 4*0^1 = 0 ET[1] = 4*0^2 + 3*1^2 = 3 ET[2] = 4*0^3 + 3*1^3 + 3*2^3 = 27 ET[3] = 4*0^4 + 3*1^4 + 3*2^4 + 4*3^4 = 375 Therefore the sum of all ET values is 0 + 3 + 27 + 375 = 405.

  201. 5

    {-1,0,0,1,3}

    {5,0,3,2,3}

    1

    0

    6

    Returns: 294

    The tree looks as follows: 0 / \ 1 2 / 3 / 4 Timestamps are T = {1, 2, 5, 3, 4}. ET values are as follows: ET[0] = 5*0^1 = 0 ET[1] = 5*0^2 + 0*1^2= 0 ET[2] = 5*0^5 + 3*1^5 = 3 ET[3] = 5*0^3 + 0*1^3 + 2*2^3 = 16 ET[4] = 5*0^4 + 0*1^4 + 2*2^4 + 3*3^4 = 275 Finally, the sum will be 0 + 0 + 3 + 16 + 275 = 294.

  202. 4

    {-1,0,0,0}

    {3,2,3,0}

    1

    0

    4

    Returns: 5

    In this tree each node other than 0 is its child. The timestamps are T = {1,2,3,4} again, and the ET values are {0, 2, 3, 0}.

  203. 10

    {-1}

    {}

    7

    176

    15

    Returns: 2425

  204. 100000

    {-1,0,0,0}

    {4,7}

    1

    0

    1000000000

    Returns: 412779665

  205. 15

    {-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    15

    0

    2

    Returns: 14

  206. 15

    {-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

    15

    0

    16

    Returns: 291773459

  207. 11

    {-1,0,1,2,3,4,0,6,7,8,9}

    {10,1,1,1,1,1,2,2,2,2,2}

    6

    0

    11

    Returns: 108683381

  208. 10

    {-1 }

    { }

    7

    176

    15

    Returns: 2425

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: