DeleteArrays
SRM 770 · 2019-10-31 · by lazy_fox
Problem Statement
You are given three numbers: a, b, and c. You need to generate three arrays A, B, C of lengths a, b, c using the pseudocode given below:
A[0] = 33
A[1] = 42
for i = 2 to a-1:
A[i] = (5*A[i-1] + 7*A[i-2]) modulo 1000000007 + 1
B[0] = 13
for i = 1 to b-1:
B[i] = (11*B[i-1]) modulo 1000000007 + 1
C[0] = 7
C[1] = 2
for i = 2 to c-1:
C[i] = (5*C[i-1] + 7*C[i-2]) modulo 1000000007 + 1
Now that you have 3 arrays A , B and C, you can perform three types of moves:
- Remove one element each from arrays A and B. The cost of this operation is (x + the sum of elements you removed).
- Remove one element each from arrays B and C. The cost of this operation is (y + the sum of elements you removed).
- Remove one element each from arrays A and C. The cost of this operation is (z + the sum of elements you removed).
You need to minimize the sum of elements remaining in these arrays after performing above mentioned operations any number of times. If there are multiple ways to obtain the minimum sum, you need to minimize the cost of doing so.
Return an array of two integers containing the minimum sum (at index 0) and minimum cost of obtaining the minimum sum (at index 1).
Notes
- The input format is only chosen to keep the input size small. The reference solution does not depend on any properties of these arrays A, B, C, it would work correctly for any arrays of the given length.
- Watch out for integer overflows, both when generating the input arrays and when calculating the return values.
- The elements of arrays can be removed in any order.
Constraints
- Each of a, b and c will be between 2 and 10^5, inclusive.
- Each of x, y and z will be between 1 and 10^9, inclusive.
2
2
2
2
3
4
Returns: {0, 250 }
The arrays are: A = {33, 42} B = {13, 144} C = {7, 2} We can remove first elements from arrays A and B with cost (2 + 33 + 13) = 48. Next we remove the remaining element from A and the first element of C with cost (4 + 42 + 7) = 53. Finally, we remove the remaining elements from B and C with cost (3 + 144 + 2) = 149. Sum of Elements remaining = 0, which is clearly optimal. Cost = 48 + 53 + 149 = 250.
3
2
2
3
2
1
Returns: {2, 688 }
The arrays are: A = {33, 42, 442} B = {13, 144} C = {7, 2} One optimal solution: Remove 33 from A and 13 from B, cost = (3 + 33 + 13) = 49. Remove 442 from A and 144 from B, cost = (3 + 442 + 144) = 589. Remove 42 from A and 7 from C, cost = (1 + 42 + 7) = 50. Sum of remaining elements = 2. Total cost = 49 + 589 + 50 = 688.
24561
4357
3117
3895
2425
11697
Returns: {6002652266123, 10041603080088 }
340
500
234
1
1
1
Returns: {0, 498124880075 }
1000
100
100
2352
232
4263
Returns: {320467404289, 272083126790 }
Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DeleteArrays with a public method vector<long long> doDelete(int a, int b, int c, long long x, long long y, long long z) · 29 test cases · 2 s / 256 MB per case