SettingShield
2016 TCO Algo 1B · 2016-03-24 · by boba5551
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
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])
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.
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.
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.
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.
12
6
4
{4, 3, 7}
{2, 4, 5}
{3, 8, 7}
{40, 23, 13}
Returns: 108
50
77
4
{4, 11, 30}
{9, 40, 7}
{33, 8, 12}
{20000, 200, 13}
Returns: 79111
22
7
4
{10000000, 1, 5}
{9999999, 9999998, 9999997}
{9995999, 0, 9919999}
{1999999, 9993999, 9299999}
Returns: 40000000
Watch out for integer overflow.
555
120
4
{10000000, 301, 520}
{9999999, 9999998, 9999997}
{9995999, 0, 9919999}
{1999999, 9993999, 9299999}
Returns: 40000000
Watch out for integer overflow.
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.
Submissions are judged against all 101 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SettingShield with a public method long long getOptimalCost(int n, int h, int t, vector<int> val0, vector<int> a, vector<int> b, vector<int> m) · 101 test cases · 2 s / 256 MB per case