Last Updated: 13 Dec, 2021
Merging Stones
Ninja
Asked in company
You are given an array of piles of stones ‘stones’, where ‘stones[i]’ represents the number of stones in ‘ith’ piles. You are also given an integer ‘K’. Your task is to merge stones into one pile with minimum cost. In one operation you can take exactly ‘K’ consecutive piles and merge them and the cost of merging piles of stones in a particular operation is the total number of stones in all piles considered in that operation.
If it is not possible to merge, return -1.
For example:
You are given ‘stones’ = [4, 3, 4, 2, 5] and ‘K’ = 3, Here one way you can first merge [3, 4, 2] with a cost of 9, to form the array [4, 9, 5] then merge these piles as [18], with a cost of 18. The total cost to merge the array is 27, which is the minimum of all the possible ways. Hence the answer is 27.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘K’, representing the number of piles and ‘K’ the integer given.
The second line of each test case contains ‘N’ space-separated integers, representing the elements of the array ‘stones’.
Output Format:
For each test case print a single integer representing the minimum cost to merge the whole array into 1.
Print a separate line for each test case.
Constraints:
1 <= T <= 10
1 <= |N| <= 10^2
2 <= K <= N
1 <= |stones| <= 10^5
Time Limit: 1 sec.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we will look at all possible subarrays of the array, for any array, we will have to add the sum of its elements to the solution at one point or another. If the subarray has only ‘K’ elements we will return the sum of all elements otherwise we will further check if more piles can be formed in the subarray or not and return the minimum of all possible solutions.
Since for each subarray, we will require the sum of its element we will create a prefix sum array to get the subarray sum in O(1) time.
We will create a recursive function mergeStonesRecur(stones, preArr, k , start, end), where start and end are the starting and ending indices of the current subarray, while preArr is the prefix sum array of stones.
Algorithm:
- In the function mergeStoneRecur(stones, preArr, k, start, end)
- If start is equal to end return 0
- If end - start + 1 is equal to k return preArr[end + 1] - preArr[start]
- Set minSol as infinity
- Iterate i from start to end at each step increment i by k - 1
- Set firstPile as mergeStoneRecur(stones, preArr, k, start, i)
- Set otherPiles as mergeStonesRecur(stones, preArr, k, i + 1, end)
- Set mergingCost as 0 if end - start is divisible by k - 1, otherwise set it as preArr[end + 1] - preArr[start]
- Set minSol as minimum of itself and firstPile + otherPile + mergingCost
- Return minSol
- In the given function
- Create a prefix sum array preArr from the array stones
- Return mergeStoneRecur(stones, preArr, k, 0, size of stones - 1)
In this approach, we will store the value of each recursive call in the previous approach, and try to reuse it. We will create a cache and check if the values are already stored in the cache or not.
We will create a recursive function mergeStonesRecur(stones, preArr, k , start, end, cache), where start and end are the starting and ending indices of the current subarray, while preArr is the prefix sum array of stones. Cache is the cache of all the unique recursive calls.
Algorithm:
- In the function mergeStoneRecur(stones, preArr, k, start, end, cache)
- If start is equal to end return 0
- If end - start + 1 is equal to k return preArr[end + 1] - preArr[start]
- Set key as (start, end) as string
- If key is present in cache return cache[key]
- Set minSol as infinity
- Iterate i from start to end at each step increment i by k - 1
- Set firstPile as mergeStoneRecur(stones, preArr, k, start, i, cache)
- Set otherPiles as mergeStonesRecur(stones, preArr, k, i + 1, end, cache)
- Set mergingCost as 0 if end - start is divisible by k - 1, otherwise set it as preArr[end + 1] - preArr[start]
- Set minSol as minimum of itself and firstPile + otherPile + mergingCost
- Set cache[key] as minSol
- Return minSol
- In the given function
- Create a prefix sum array preArr from the array stones
- Set cache as an empty hashmap
- Return mergeStoneRecur(stones, preArr, k, 0, size of stones - 1, cache)
In this approach, we will build the solution from the bottom up.
We store the solution of subarray stones[i: j] in dp[i][j] as
dp[i][j] = min(dp[i][k] + dp[k + 1][j]) + sum of elements in the subarray
This approach is very similar to the last approach.
Algorithm:
- Create a prefix sum array preArr from the array stones
- If end - start is divisible by k - 1 return -1
- Create a 2D matrix dp rows and columns as size of stones array.
- Iterate start from size of stones - 1 to 0
- Iterate end from start + k - 1 to size of stones - 1
- Set dp[start][end] as maxsize
- Iterate i from start to end
- Set firstPile as dp[start][i]
- Set otherPile as dp[i + 1][start]
- Set megeCost as 0 if end - start is divisible by k - 1, otherwise set it as preArr[end + 1] - preArr[start]
- Set dp[start][end] as minimum of itself and firstPile + otherPile + mergeCost
- Iterate end from start + k - 1 to size of stones - 1
- Return dp[0][length of stones - 1]
Similar problems