Statistics

Problem Statement for "SettingShield"

Problem Statement

Vasa has carefully cultivated n plants. The plants are arranged into a line and they are conveniently numbered from 0 to n-1, inclusive, in the order in which they appear on the line.

Vasa needs to protect his plants from an incoming ice storm. In order to do that, he has installed some shields. There is exactly one special shield and there are h simple shields. The special shield covers all plants. Each simple shield covers some contiguous range of plants: simple shield number i covers plants with numbers from left[i] to right[i], inclusive.

The power of each shield can be set to any nonnegative integer value. Setting any single simple shield to power P costs P coins. Setting the special shield to power P costs (t * P) coins.

For each i, plant i will survive the storm if the total power of all shields that cover it is greater than or equal to protection[i].

You are given the ints n, h, and t. You are also given int[]s val0, a, b, and m. Below we give pseudocode that uses these to generate the int[]s protection, left, and right.

Vasa wants to make sure that all his plants survive the storm. Find and return the smallest possible total cost of doing so.

Pseudocode to generate protection, left, and right follows. Watch out for integer overflow. 

protection[0] = val0[0]
for i = 1 .. n-1
  protection[i] = (a[0] * protection[i-1] + b[0]) mod m[0]

left[0] = val0[1]
right[0] = val0[2]
for i = 1 .. h-1
  left[i] = min(n-1, (a[1] * left[i-1] + b[1]) mod m[1])
  dist = right[i-1] - left[i-1]
  right[i] = min(n-1, left[i] + (a[2] * dist + b[2]) mod m[2])

Definition

Class:
SettingShield
Method:
getOptimalCost
Parameters:
int, int, int, int[], int[], int[], int[]
Returns:
long
Method signature:
long getOptimalCost(int n, int h, int t, int[] val0, int[] a, int[] b, int[] m)
(be sure your method is public)

Notes

  • The intended solution should work within the given time limit for arbitrary int[]s protection, left, and right that satisfy the constraints. It does not depend on any special properties of the pseudorandom generator.

Constraints

  • n, h, and t will be between 1 and 10^5, inclusive.
  • val0, a, b, and m each will contain exactly 3 elements.
  • val0[0], and each element of a, and b will be between 0 and 10^7, inclusive.
  • Each element of m will be between 1 and 10^7, inclusive.
  • val0[1] will be between 0 and n-1, inclusive.
  • val0[2] will be between val0[1] and n-1, inclusive.

Examples

  1. 3

    3

    10

    {4, 0, 1}

    {1, 1, 1}

    {3, 1, 1}

    {6, 10, 10}

    Returns: 8

    Using the pseudocode we obtain protection = {4, 1, 4}, left = {0, 1, 2}, and right = {1, 2, 2}. Thus, we have one special shield and three simple shields. Simple shield 0 covers the range [0,1], simple shield 1 covers the range [1,2], and simple shield 2 covers the range [2,2]. One optimal solution is to set each of simple shields 0 and 2 to power 4. The special shield and simple shield 1 will remain untouched, with power 0. The total cost of this solution is 4 + 4 = 8. Another optimal solution is to set the three simple shields to power 4, 1, and 3, respectively.

  2. 3

    1

    10

    {4, 0, 1}

    {1, 1, 1}

    {3, 1, 1}

    {6, 10, 10}

    Returns: 40

    The only difference from Example 0 is that now we only have a single simple shield. This shield does not cover plant 2. Hence, we need to set the special shield at least to power 4 to give this plant enough protection. On the other hand, setting the special shield to 4 is clearly enough to protect all three plants. Thus, the optimal cost is 10*4 = 40.

  3. 6

    3

    2

    {4, 1, 3}

    {2, 4, 3}

    {3, 2, 2}

    {20, 9, 4}

    Returns: 22

    In this example we have protection = {4, 11, 5, 13, 9, 1}, left = {1, 5, 4}, and right = {3, 5, 5}. An optimal solution: set the special shield to 4, and set the simple shields to 9, 0, and 5, respectively. The total cost of this solution is 4*2 + 9 + 0 + 5 = 22.

  4. 12

    6

    4

    {4, 3, 7}

    {2, 4, 5}

    {3, 8, 7}

    {40, 23, 13}

    Returns: 108

  5. 50

    77

    4

    {4, 11, 30}

    {9, 40, 7}

    {33, 8, 12}

    {20000, 200, 13}

    Returns: 79111

  6. 100000

    59999

    55

    {186, 6112, 6300}

    {9701, 340, 17}

    {3318, 89084, 1208}

    {10000, 200000, 1000}

    Returns: 549890

  7. 3

    2

    100

    {1, 0, 1}

    {1, 1, 1}

    {2, 2, 1}

    {2, 2, 100}

    Returns: 1

  8. 22

    7

    4

    {10000000, 1, 5}

    {9999999, 9999998, 9999997}

    {9995999, 0, 9919999}

    {1999999, 9993999, 9299999}

    Returns: 40000000

    Watch out for integer overflow.

  9. 100000

    99999

    101

    {10000000, 123, 4567}

    {9999999, 9992998, 9939997}

    {9995999, 379077, 919199}

    {1999999, 9993999, 9299999}

    Returns: 1010000000

  10. 555

    120

    4

    {10000000, 301, 520}

    {9999999, 9999998, 9999997}

    {9995999, 0, 9919999}

    {1999999, 9993999, 9299999}

    Returns: 40000000

    Watch out for integer overflow.

  11. 501

    2

    2

    {10000000, 500, 500}

    {10000000, 10000000, 10000000}

    {0, 0, 500}

    {1000003, 10000000, 10000000}

    Returns: 10000000

    There are two simple shields, with left = {500, 0} and right = {500, 500}. Simple shield 0 protects just the plant number 500. Simple shield 1 protects all 501 plants, exactly like the special shield. However, using simple shield 1 is cheaper than using the special shield, so you should do that in the optimal solution.

  12. 1

    100000

    2

    {10000000, 0, 0}

    {10000000, 10000000, 10000000}

    {74824, 723647, 500}

    {1000003, 10000000, 10000000}

    Returns: 10000000

  13. 2

    100000

    100000

    {10000000, 0, 0}

    {10000000, 10000000, 10000000}

    {74824, 723647, 500}

    {1000003, 1, 1}

    Returns: 7582324276

  14. 2

    100000

    100000

    {10000000, 1, 1}

    {10000000, 10000000, 10000000}

    {74824, 723647, 500}

    {1000003, 1, 1}

    Returns: 10075724

  15. 2

    100000

    100000

    {10000000, 1, 1}

    {10000000, 0, 0}

    {74824, 1, 5551}

    {1000003, 2, 2}

    Returns: 1000000000000

  16. 100000

    100000

    100000

    {10000000, 1, 1}

    {10000000, 0, 10000000}

    {74824, 1, 10000000}

    {1000003, 2, 1}

    Returns: 1000000000000

  17. 99229

    100000

    369

    {8567053, 15132, 43914}

    {3966832, 7961579, 6154918}

    {1732159, 776197, 4036571}

    {2319761, 5956145, 5}

    Returns: 3161242557

  18. 99692

    100000

    398

    {2764834, 45352, 82222}

    {4005359, 6223316, 7697431}

    {4579329, 4809545, 9696251}

    {4401766, 1484287, 3}

    Returns: 1751896898

  19. 99073

    100000

    353

    {2696468, 44095, 70273}

    {4651140, 5973959, 889921}

    {5314285, 4726876, 1027500}

    {7775884, 3042809, 2}

    Returns: 2744839397

  20. 99172

    100000

    343

    {2642227, 98446, 98671}

    {906620, 1719636, 1812360}

    {7235580, 7034149, 3850839}

    {2647934, 1153977, 2}

    Returns: 908238618

  21. 99414

    100000

    331

    {905264, 26960, 79507}

    {4495932, 1645518, 9042093}

    {6624409, 1617030, 7426936}

    {3753199, 7117693, 5}

    Returns: 1242267243

  22. 99959

    99441

    228

    {1598549, 70644, 90610}

    {393018, 6573951, 4548193}

    {230716, 6104225, 6142574}

    {3125836, 2859615, 16}

    Returns: 712689696

  23. 99818

    99913

    155

    {401699, 37521, 94361}

    {8190735, 1864061, 5223231}

    {6775065, 4028222, 7317682}

    {4680536, 943654, 15}

    Returns: 725466185

  24. 99997

    99500

    226

    {7185811, 62468, 72390}

    {4104566, 6347618, 7984215}

    {5071559, 9419886, 5088522}

    {9716550, 1398256, 5}

    Returns: 2195699158

  25. 99198

    99751

    437

    {4377890, 75621, 78678}

    {7355384, 3087932, 5647900}

    {431762, 2480773, 6840885}

    {5532196, 1231109, 27}

    Returns: 2417511094

  26. 99621

    99182

    183

    {4063801, 4102, 86201}

    {7267696, 719584, 294296}

    {6849095, 2580152, 2194629}

    {8481203, 7945816, 23}

    Returns: 1552049169

  27. 4297

    99350

    567

    {2518682, 0, 879}

    {4600500, 7333717, 3453806}

    {6683847, 681177, 7017110}

    {3155728, 3776894, 22}

    Returns: 1789108965

  28. 4574

    99776

    121

    {4863277, 0, 546}

    {269094, 7579246, 1281318}

    {560156, 1696536, 6520458}

    {6450774, 2463540, 19}

    Returns: 779990198

  29. 4969

    99418

    357

    {1383924, 0, 4337}

    {800040, 1326526, 5971989}

    {3482545, 8398159, 7293582}

    {6860568, 974370, 18}

    Returns: 2445441429

  30. 4395

    99774

    527

    {7602939, 0, 2661}

    {3951178, 4125761, 4535757}

    {2022319, 6132669, 3365220}

    {5790139, 7572688, 28}

    Returns: 3052825761

  31. 4666

    99590

    504

    {9418738, 0, 849}

    {6579397, 1364576, 3863187}

    {7434427, 2835943, 9750906}

    {9495044, 4474096, 16}

    Returns: 4783021992

  32. 4990

    99606

    506

    {1619, 0, 1350}

    {524023, 9953257, 6836460}

    {7729293, 2580497, 1177862}

    {841, 8825179, 7}

    Returns: 425819

  33. 4553

    99830

    472

    {1656, 0, 428}

    {5052136, 9220407, 174396}

    {6494843, 8929200, 1915591}

    {825, 2300739, 5}

    Returns: 389760

  34. 4326

    99627

    214

    {1383, 0, 3511}

    {4045440, 149713, 2212549}

    {9634687, 5418787, 4987506}

    {1330, 2540439, 14}

    Returns: 260604

  35. 4331

    99655

    414

    {499, 0, 2370}

    {757079, 1754979, 9443047}

    {6498387, 2218744, 3284638}

    {878, 7342972, 19}

    Returns: 360594

  36. 4489

    99264

    462

    {793, 0, 2789}

    {2518669, 9219470, 1008227}

    {2482999, 8447956, 9881232}

    {1008, 2783060, 7}

    Returns: 463386

  37. 4746

    99097

    11

    {324, 0, 1264}

    {1061933, 6310089, 9465203}

    {1576214, 5806545, 6883313}

    {967, 4122613, 2}

    Returns: 10615

  38. 4224

    99098

    26

    {42, 0, 2634}

    {2439487, 9844351, 2162829}

    {9104353, 2340855, 1192030}

    {764, 9232388, 16}

    Returns: 19630

  39. 4845

    99814

    24

    {543, 0, 3298}

    {8643011, 408243, 876186}

    {9509461, 9775227, 2628395}

    {633, 9336965, 19}

    Returns: 15144

  40. 4414

    99826

    26

    {603, 0, 3040}

    {4945942, 3640986, 7568761}

    {3070199, 4909319, 242358}

    {701, 2189260, 26}

    Returns: 17966

  41. 4117

    99810

    51

    {999, 0, 2972}

    {6069470, 1773675, 6899684}

    {6071727, 4753972, 2836699}

    {1417, 1910149, 10}

    Returns: 71757

  42. 4084

    99719

    32

    {501, 0, 1160}

    {9843162, 7373750, 2349317}

    {1583984, 1467606, 3406106}

    {958, 2610665, 426}

    Returns: 30592

  43. 4208

    99862

    21

    {144, 0, 3342}

    {1813446, 9374068, 731940}

    {1130977, 8721090, 1778433}

    {1259, 5739850, 67}

    Returns: 26418

  44. 4440

    99453

    56

    {384, 0, 4435}

    {9430439, 8387524, 5244894}

    {4788427, 9158904, 9332858}

    {868, 2684361, 115}

    Returns: 36336

  45. 4084

    99487

    46

    {186, 0, 3884}

    {3379454, 2833692, 1067302}

    {3703051, 4312000, 5191239}

    {920, 9176728, 492}

    Returns: 41630

  46. 4056

    99936

    31

    {1212, 0, 3496}

    {622710, 5471419, 7986024}

    {7356433, 5318463, 2333433}

    {1250, 6928830, 384}

    Returns: 21102

  47. 2815

    99385

    3

    {1769, 0, 60}

    {1301272, 999589, 9180778}

    {5735853, 728112, 5000002}

    {1157, 5505670, 206}

    Returns: 4077

  48. 2574

    99244

    5

    {1194, 0, 1794}

    {3955085, 6628629, 2125942}

    {7391683, 9746716, 2095322}

    {753, 1053376, 51}

    Returns: 4198

  49. 2393

    99113

    7

    {1553, 0, 2180}

    {3905259, 2562491, 9457867}

    {2872817, 9203322, 7604595}

    {984, 8747857, 274}

    Returns: 6767

  50. 2436

    99746

    7

    {447, 0, 2285}

    {6195612, 2097678, 5783096}

    {8411179, 6692907, 3186883}

    {1105, 3493741, 42}

    Returns: 7294

  51. 3213

    99075

    6

    {207, 0, 1938}

    {8950396, 1591636, 5384750}

    {9120610, 1045206, 5629920}

    {736, 466252, 262}

    Returns: 4380

  52. 100000

    99901

    900

    {712, 0, 99}

    {37, 1, 0}

    {13, 1, 99}

    {1000, 1000000, 1000000}

    Returns: 848460

  53. 99745

    99700

    2168

    {237523, 0, 45}

    {6362890, 1, 0}

    {9184870, 1, 45}

    {1063, 10000000, 10000000}

    Returns: 2255079

  54. 99527

    99510

    5499

    {7069217, 0, 17}

    {7167952, 1, 0}

    {8020210, 1, 17}

    {1167, 10000000, 10000000}

    Returns: 12308020

  55. 99430

    99419

    8267

    {355869, 0, 11}

    {304037, 1, 0}

    {3634872, 1, 11}

    {1202, 10000000, 10000000}

    Returns: 8265169

  56. 99238

    99166

    1319

    {1944965, 0, 72}

    {3501537, 1, 0}

    {8852197, 1, 72}

    {1249, 10000000, 10000000}

    Returns: 3375274

  57. 99119

    99066

    1828

    {8358373, 0, 53}

    {6576515, 1, 0}

    {1306938, 1, 53}

    {1105, 10000000, 10000000}

    Returns: 10149554

  58. 99028

    98933

    977

    {7657945, 0, 95}

    {2153578, 1, 0}

    {9533838, 1, 95}

    {880, 10000000, 10000000}

    Returns: 8471929

  59. 99242

    99224

    5199

    {1483165, 0, 18}

    {9142893, 1, 0}

    {2072074, 1, 18}

    {847, 10000000, 10000000}

    Returns: 5092796

  60. 99693

    99625

    1339

    {5696107, 0, 68}

    {2077468, 1, 0}

    {5377360, 1, 68}

    {1252, 10000000, 10000000}

    Returns: 7278271

  61. 99287

    99192

    913

    {739149, 0, 95}

    {3751592, 1, 0}

    {3708954, 1, 95}

    {1025, 10000000, 10000000}

    Returns: 1623789

  62. 99132

    99114

    5198

    {1434271, 0, 18}

    {8403744, 1, 0}

    {3093535, 1, 18}

    {1547, 10000000, 10000000}

    Returns: 8445750

  63. 100000

    99985

    6241

    {48761, 0, 15}

    {973837, 1, 0}

    {7723239, 1, 15}

    {818, 123456, 123456}

    Returns: 4299501

  64. 100000

    99945

    1784

    {69845, 0, 55}

    {2054649, 1, 0}

    {5145500, 1, 55}

    {1222, 123456, 123456}

    Returns: 1953609

  65. 100000

    99999

    49999

    {19931, 0, 1}

    {1079120, 1, 0}

    {4940478, 1, 1}

    {684, 123456, 123456}

    Returns: 17019987

  66. 100000

    99902

    998

    {43393, 0, 98}

    {7636871, 1, 0}

    {1939089, 1, 98}

    {1174, 123456, 123456}

    Returns: 1102442

  67. 100000

    99917

    1149

    {94242, 0, 83}

    {965294, 1, 0}

    {1804214, 1, 83}

    {1348, 123456, 123456}

    Returns: 1498424

  68. 100000

    99976

    3987

    {5591, 0, 24}

    {6130517, 1, 0}

    {2794851, 1, 24}

    {885, 123456, 123456}

    Returns: 2918231

  69. 100000

    99972

    3429

    {54451, 0, 28}

    {5124801, 1, 0}

    {8220716, 1, 28}

    {758, 123456, 123456}

    Returns: 2257227

  70. 100000

    99919

    1203

    {47745, 0, 81}

    {7904339, 1, 0}

    {6342479, 1, 81}

    {617, 123456, 123456}

    Returns: 728412

  71. 100000

    99975

    3844

    {3516, 0, 25}

    {2984784, 1, 0}

    {2232606, 1, 25}

    {1275, 123456, 123456}

    Returns: 4146381

  72. 100000

    99943

    1701

    {7091, 0, 57}

    {6415611, 1, 0}

    {4734890, 1, 57}

    {863, 123456, 123456}

    Returns: 1336743

  73. 100000

    99973

    3464

    {27076, 0, 27}

    {9285181, 1, 0}

    {2168529, 1, 27}

    {1303, 123456, 123456}

    Returns: 3887106

  74. 100000

    99960

    2316

    {12641, 0, 40}

    {2063312, 1, 0}

    {5110552, 1, 40}

    {1136, 123456, 123456}

    Returns: 2525449

  75. 100000

    99972

    3324

    {94849, 0, 28}

    {5903449, 1, 0}

    {7041076, 1, 28}

    {1480, 123456, 123456}

    Returns: 4119319

  76. 100000

    99969

    3013

    {57791, 0, 31}

    {8649487, 1, 0}

    {1221723, 1, 31}

    {1101, 123456, 123456}

    Returns: 3002298

  77. 100000

    99947

    1739

    {38128, 0, 53}

    {3581152, 1, 0}

    {5119279, 1, 53}

    {1361, 123456, 123456}

    Returns: 2258499

  78. 100000

    99943

    1615

    {91641, 0, 57}

    {6462059, 1, 0}

    {1136586, 1, 57}

    {1505, 123456, 123456}

    Returns: 2369790

  79. 100000

    99906

    879

    {68414, 0, 94}

    {2525538, 1, 0}

    {6093348, 1, 94}

    {1188, 123456, 123456}

    Returns: 784862

  80. 100000

    99998

    33231

    {39837, 0, 2}

    {2648243, 1, 0}

    {7610712, 1, 2}

    {1280, 123456, 123456}

    Returns: 26690048

  81. 100000

    99909

    924

    {65251, 0, 91}

    {1070707, 1, 0}

    {758923, 1, 91}

    {669, 123456, 123456}

    Returns: 669836

  82. 100000

    99903

    891

    {17477, 0, 97}

    {4325920, 1, 0}

    {840187, 1, 97}

    {1343, 123456, 123456}

    Returns: 1208297

  83. 100000

    100000

    100000

    {0, 0, 0}

    {0, 0, 0}

    {0, 0, 0}

    {1, 1, 1}

    Returns: 0

  84. 100000

    100000

    100000

    {10000000, 0, 0}

    {0, 0, 0}

    {0, 0, 0}

    {1, 1, 1}

    Returns: 10000000

  85. 100000

    100000

    100000

    {10000000, 0, 0}

    {1, 0, 0}

    {1, 0, 0}

    {10000000, 1, 1}

    Returns: 10009800001

  86. 100000

    100000

    100000

    {10000000, 0, 0}

    {10000000, 10000000, 10000000}

    {10000000, 10000000, 10000000}

    {10000000, 10000000, 10000000}

    Returns: 10000000

  87. 100000

    99926

    1183

    {66653, 0, 74}

    {6482117, 1, 0}

    {7587546, 1, 74}

    {840, 121212, 121212}

    Returns: 996887

  88. 100000

    99942

    1531

    {30585, 0, 58}

    {1251676, 1, 0}

    {5254949, 1, 58}

    {882, 121212, 121212}

    Returns: 1359147

  89. 100000

    99947

    1724

    {57970, 0, 53}

    {7793030, 1, 0}

    {3032893, 1, 53}

    {877, 121212, 121212}

    Returns: 1474854

  90. 100000

    99999

    49888

    {37126, 0, 1}

    {8229364, 1, 0}

    {6198642, 1, 1}

    {1326, 121212, 121212}

    Returns: 34830400

  91. 100000

    99966

    2713

    {76873, 0, 34}

    {652838, 1, 0}

    {832864, 1, 34}

    {1287, 121212, 121212}

    Returns: 3371953

  92. 100000

    99988

    7574

    {89155, 0, 12}

    {4477855, 1, 0}

    {1863338, 1, 12}

    {850, 121212, 121212}

    Returns: 4170105

  93. 100000

    99946

    1684

    {91939, 0, 54}

    {5684858, 1, 0}

    {2411420, 1, 54}

    {1282, 121212, 121212}

    Returns: 2127991

  94. 100000

    99988

    7576

    {24832, 0, 12}

    {903044, 1, 0}

    {1313786, 1, 12}

    {786, 121212, 121212}

    Returns: 5170984

  95. 100000

    99993

    12387

    {265, 0, 7}

    {9639046, 1, 0}

    {6439660, 1, 7}

    {1546, 121212, 121212}

    Returns: 14486952

  96. 100000

    99985

    6134

    {37801, 0, 15}

    {2017706, 1, 0}

    {6387457, 1, 15}

    {838, 121212, 121212}

    Returns: 4144685

  97. 555

    120

    4

    {10000000, 301, 520 }

    {9999999, 9999998, 9999997 }

    {9995999, 0, 9919999 }

    {1999999, 9993999, 9299999 }

    Returns: 40000000

  98. 100000

    1337

    42

    {13, 17, 19 }

    {23, 29, 31 }

    {1009, 1013, 1019 }

    {100003, 100019, 100043 }

    Returns: 4172728

  99. 100000

    100000

    100000

    {33625, 313, 99999 }

    {3653625, 3636363, 2415411 }

    {3653625, 3636363, 3727367 }

    {313625, 363636, 563321 }

    Returns: 31337500125

  100. 100000

    100000

    100000

    {10000000, 1305, 13531 }

    {1, 52, 5428 }

    {1, 2, 631 }

    {10000000, 10000000, 10000000 }

    Returns: 1000000000000

  101. 2

    2

    1

    {1, 0, 0 }

    {1, 1, 1 }

    {0, 1, 0 }

    {2, 2, 2 }

    Returns: 1

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: