Last Updated: 29 Aug, 2021
Combine The Slimes
Hard
Asked in companies
Steve has ’N’ slimes. Each slime has a size between 0 and 99. He wants to merge all these slimes into one by repeatedly mixing two adjacent slimes. The cost of mixing two slimes of size a and b is a * b, and the resulting slime has size (a + b) % 100. Help Steve compute the minimum cost to combine all slimes into one.
Help Steve to find the minimum cost in mixing for mixing all these slimes.
For Example :
Slimes = {10, 7, 3}
On mixing slime 3 and 7 remaining slimes are: {10, 10} and the cost is 3 * 7 = 21.
On mixing slime 10 and 10 remaining slimes are: {10} and the cost of mixing is 10 * 10 = 100.
So the final cost of mixing the slime is 121.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the total number of slimes.
The next line contains 'n' integers denoting the size of the slimes.
Output Format :
For each test case, print a single integer “ans” denoting the minimum cost of converting all these slime into one single slime.
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.
Constraints :
1 <= T <= 10
1 <= N <= 100
0 <= slime[i] <= 99
Time limit: 1 sec
Approaches
In this approach, we will start combining every adjacent slime and check for the minimum possible cost.
The steps are as follows:
- In the “main” function:
- Call the function recursion from start to end where start is the index of the first slime and end is the index of the last slime.
- In the “recursion” function:
- Check if the starting slime is greater than the ending slime, if true then return 0.
- Else take a variable “ans” to store the minimum cost and iterate from the starting point(say i) to the ending point(say j) to find the minimum cost of combining the slime(say iterator be k):
- The cost of combining slime i to j will be the minimum of “ans”, cost of combining the slime i to k + k to j + the total size of the slimes from i to k * k to j. i.e. “ans” = min(“ans”, “recursion(i, k)” + “recursion(k + 1, j)” + “computeSiz(i , k)” * “computeSiz(k + 1, j)”.
- Return ans.
- In the “computeSiz” function:
- Take a variable ans in which we will store the final size of slimes from i to j.
- Iterate through all the slimes from i to j:
- Add all the slimes to “ans”
- Return (“ans” % 100).
This approach is similar to the previous approach, the only difference is we are storing the minimum cost for all subarrays and use the precomputed values when required.
The steps are as follows:
- In the “main” function:
- Call the function recursion from start to end where start is the index of first slime and end is the index of last slime.
- In the “recursion” function:
- Check if the starting slime is greater than the ending slime, if true then return 0.
- Check if dp[i][j] != -1, if there is some value in the current position it means we have already computed the minimum for this subarray. Return “dp[i][j]”.
- Else take a variable ‘ans’ to store the minimum cost and iterate from the starting point(say i) to the ending point(say j) to find the minimum cost of combining the slime(say iterator be k):
- The cost of combining slime i to j will be the minimum of “ans”, cost of combining the slime i to k + k to j + the total size of the slimes from i to k * k to j. i.e. “ans” = min(“ans”, “recursion(i, k)” + “recursion(k + 1, j)” + “computeSiz(i , k)” * “computeSiz(k + 1, j)”.
- Store the value of ans in “dp[i][j]”.
- Return “ans”.
- In the “computeSiz” function:
- Take a variable “ans” in which we will store the final size of slimes from i to j.
- Iterate through all the slimes from ‘i’ to ‘j’:
- Add all the slimes to “ans”
- Return (“ans” % 100)
In this approach we will take two 2D arrays “dp” and “sum”. “dp[i][j]” will store the minimum cost of combining all the slimes from index i to index j and sum[i][j] will contain the final size of the slime after combining all the slimes from i to j.
The steps are as follows:
- Take two 2D arrays “dp” and “sum” initialize the dp array by INT_MAX.
- Iterate through the array “slime” from 0 to n-1(say iterator be i):
- Iterate through the array again from 0 to n-1(say iterator be j):
- Update sum[i][j] = sum[i][j - 1] + slime[i].
- Iterate through the array again from 0 to n-1(say iterator be j):
- Once we have computed the value of the sum array. We will start iterating through the array again from 1 to n-1(say iterator be “siz”):
- Iterate through the array from 0 to n-1(say iterator be i):
- Take a int j = “siz” + i.
- Now if j < n iterate through i to j(say iterator be k):
- Update the value of dp[i][j] = min( dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]).
- Iterate through the array from 0 to n-1(say iterator be i):
- Return dp[0][n - 1].