Last Updated: 5 Jul, 2021
Morty and his array
Hard
Asked in company
Rick gave Morty an array 'Arr' of length ‘N’ and an integer ‘K’ and asked him to find the minimum possible cost to split the array into non-empty sub-arrays such that the following conditions can be achieved:
1. If every element in the sub-array is unique, then the cost of the sub-array is K.
2. If some elements are not unique, then the cost will be ‘K’ + the number of elements that are not unique i.e. frequencies of repeated elements.
An array ‘C’ is a sub-array of array ‘D’ if ‘C’ can be obtained from ‘D’ by deleting several elements from the beginning and several elements from the end.
Example : let ‘arr’ = [1,0,0] then the possible sub-arrays of ‘arr’ will be- {1}, {0}, {0}, {1,0}, {0,0}, {1,0,0}.
For Example
Let Arr[] = {1, 1, 1, 4, 1, 2, 4}, K=2
The given array can be split into two sub-arrays {1, 1, 1, 4}, {1, 2, 4}. The total cost will be for the first sub-array - 2+ 3(frequency of 1 is 3 in the first sub-array) + for the second sub-array - 2, Hence total cost is 7.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains two integers, ‘N’ and ‘K’, denoting the length of the array and cost of each subarray, respectively.
The second line of the test case contains an array ‘Arr’ of ‘N’ integers.
Output Format :
For each test case, print a single integer ‘ANS’ representing the minimum cost of splitting the array.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints :
1 <= T <= 10
1 <= N <= 500
1 <= K <= 500
1 <= Arr[i] <= 500
Time limit: 1 sec
Approaches
The basic idea is to generate all the possible subarrays and find the cost of every possible split and then returning the minimum cost from all of them.
The steps are as follows:
- Recursively go through every possible split of the array Arr.
- Store all the subarrays of one split into a vector<vector<int>> split.
- Now go through every subarray of that split and find the frequency of every element in that subarray and calculate the cost of that split.
- Return the minimum value from all of the splits.
The basic idea of this approach is that we will compute the minimum cost of creating a subarray from 1 to i where i <= N and store the value of that in a dp array.
The steps are as follows:
- Take an array dp of size ‘N’ and initialize every value of dp by INT_MAX except for dp[0]. As dp[0] will always be zero.
- Now iterate through the array Arr from 1 to N(say iterator be i):
- Take an array ‘F’ of size M where M is the maximum value present in the array Arr. In the array ‘F’ we will store the frequency of all the elements.
- Iterate through the array Arr from i to N (say iterator be j):
- In every iteration increment the value of F[Arr[j]] by 1.
- Now take an int ‘Cost’ and find the total cost of constructing the subarray from i to j by iterating in the array F.
- Now, edit the value of dp[j]=min(dp[j], dp[i-1] + Cost + K);
- Return the value of dp[n-1].
The basic idea of this approach is that we will compute the minimum cost of creating a subarray from 1 to i where i <= N but using a top-down dp such that we don’t have to calculate the frequency every time.
The steps are as follows:
- Take an array dp of size ‘N’ and initialize every value of dp by -1.
- Make another function ‘solve’ from start=0 to end=n by which we will find the value of dp[n-1] to dp[0].
- Base case for this function will be if start==end then we have to return 0 or if dp[start]!=-1 then we will return dp[start].
- Now if the above condition is not satisfied then we will iterate from start to end and for every iteration, we will increase the frequency of the current element ie frequency[arr[i]]++.
- And we will set the dp at current element to be the minimum of dp at current element or the cost for splitting the array at that element + the cost of remaining element(i.e i to end) which can be written as dp[i]=min(dp[i], cost + solve(i+1));
- Return the value of dp[0].