Question 2
At Amazon Web Services (AWS), efficient and cost-effective data backup is critical. You are given a batch of n files, containing files from 1 to n; and these files have to be stored in Amazon S3 buckets for backup. A total of K of these files are sensitive and require encryption. The sensitive files are given as an array sensitiveFiles.
The storage cost is determined as follows:
for a batch of M files that contains X sensitive files, cost is M * X * encCost, where encCost is the encryption cost for sensitive files. This is applicable only when batch contains at least 1 sensitive file.
For a batch of M files with 0 sensitive files, the cost is a constant flatCost.
If the no of files in a batch M is divisible by 2 then:
store the entire batch in bucket and calculate cost using rule 1 or 2.
split the batch into 2 equal parts and total cost will be the sum of the costs for smaller batches
Note:
When splitting a batch into two files, both must remain in their original order.
For example, given a batch containing files 1, 4, 2, 6, the only split is into {1, 4} and {2, 6}. You cannot reshuffle the files into different groupings like {1, 2} and {4, 6}.
Though B1 can further be split into {1} and {4}, and similarly B2 can be split into {2} and {6}.
You are to compute the minimum storage cost while maintaining the rules constraints.
Examples
Example 2:
n = 2
encCost = 2
flatCost = 1
sensitiveFiles = [1, 3]
Batch = {1, 2, 3, 4}, where files 1 and 3 are sensitive.
Approach 1:
Store all on single bucket
Batch size is 4 with 2 sensitive files, Using rule 1 gives cost of 4 * 2 * 2 = 16
Approach 2:
split batches into 2 as per rule 3. new batches = [1,2] and [3,4]
batch [1,2] has 1 sensitive file. using rule 1 gives cost = 2 * 1 * 2 = 4;
batch [3,4] has 1 sensitive file. using rule 1 gives cost = 2 * 1 * 2 = 4
total cost = 4 + 4 = 8
Approach 3:
split batches into 2 as per rule 3. new batches = [1,2] and [3,4]
split the batch [1,2] again into batches [1] and [2]
similarily split [3,4] into [3] and [4]
cost of [1] and [3] as per rule 1 = 2 each
cost of [2] and [4] as per rule 2 = 1 each
total cost = 2 + 2 + 1 + 1 = 6
So minimum cost is 6
Function Description
Complete the function minStorageCost :
int minStorageCost(int n, int encCost, int flatCost, int[] sensitiveFiles)
Parameters:
int n: total files numbered from 1 to n.
int encCost: encryption multiplier as described in Rule 1.
int flatCost: flat cost for split batches as described in Rule 2.
int[] sensitiveFiles: integer array representing the indices of K sensitive files.
Returns
Return the minimum cost to store the files, modulo 1e9+7.
Constraints
1 ≤ n ≤ 3 × 10^5
1 ≤ encCost, flatCost ≤ 10^5
1 ≤ K ≤ n
Input Format for Custom Testing
Sample Case 0
n = 3
encCost = 2
flatCost = 1
sensitiveFiles = [1,2,3,4,5,6,7,8]
Sample Output:
16
Explanation:
Optimal approach is to keep splitting batches until all batches contain a single file.
Each batch costs 1 * 1 * 2 = 2
Total cost = 2 * 8 = 16
Sample Case 1
n = 3
encCost = 2
flatCost = 1
sensitiveFiles = [7,1]
Sample Output:
8
Explanation:
Split batch into [1], [2], [3,4], [5,6], [7], [8].
Costs:
Sensitive files cost 2 each, remaining batches cost 1 each.
Total cost = 8