Mixtures
Hermione is attending the Magic Potion's Class in Hogwarts. She has ‘N’ potions in front of her lying in a row. Her task is to combine these potions into 1. To do so, she can pick any two adjacent potions of color ‘A’, ‘B’ and mix them to form another potion of color ‘C’=(‘A’ + ‘B’)%100, which will then replace ‘A’ and ‘B’ in the row (Two potions combine to form one potion). But when a new potion is formed, it produces smoke of value ‘A’ * ‘B’. Hermione needs your help to minimize the smoke produced in the above task.
For example:
For the given array [ 1, 3, 1, 2, 4 ].
The optimal way will be:
Mix the last two elements. The array will be [1, 3, 1, 6 ], and the smoke will be 8.
Mix the first two elements. The array will be [4, 1, 6 ], and the smoke will be 11.
Mix the last two elements. The array will be [4, 7], and the smoke will be 17.
Mix the remaining two elements. The array will be [11], and the smoke will be 45.
So, the output will be 45.
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 a single integer ‘N’, representing the number of potions.
The second line of each test case contains ‘N’ space-separated integers representing the color value of the potions.
Output Format:
For each test case, print a single-digit integer representing the minimum amount of smoke generated.
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 <= X <= 99
Where ‘X’ is the color value of a potion.
It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 100.
Time Limit: 1 sec.
We will implement a recursive function, which will take two indices ‘X’ and ‘Y’ as arguments and return the minimum smoke produced by merging all the potions between these two indices. To find this we will iterate from ‘X’ to ‘Y’ and will find the optimal adjacent indices which we should mix to get minimum smoke.
So, for the final output, we will give zero and ‘N - 1’ as the argument and the function will return the optimal answer.
Algorithm:
- We will implement a prefix sum array ‘PREF’ to calculate the prefix sum mod 100.
- Then we will call the ‘solver’ function with zero and ‘N-1’ as arguments.
- If ‘X’ == ‘Y’, the smoke produced will be zero since there is only one potion.
- Else we will iterate from ‘X’ to ‘Y-1’ and will choose the adjacent indices which we should mix to produce minimum smoke.
- For two adjacent indices, ‘i’ and 'i + 1’, the smoke produced will be the sum of the smoke produced from ‘X’ to ‘i’, smoke produced from ‘i + 1’ to ‘Y’, and the product of the sums of ‘X’ to ‘i’ and ‘i + 1’ to ‘Y’.
- Finally, we will take the minimum smoke from all the possible values and then return it.
We will apply a similar approach to the recursive one but here we will use memoization to store the answer of each state to avoid revisiting the same state. We will take a two-dimensional vector ‘DP’ where ‘DP[i][j]’ denotes the minimum smoke produced by merging all the potions from index ‘i’ to index ‘j’. To calculate ‘DP[i][j]’, we will iterate over ‘i’ to ‘j’ and choose the optimal adjacent indices to mix.
Algorithm:
- We will implement a prefix sum array ‘PREF’ to calculate the prefix sum mod 100.
- Then we will call the ‘solver’ function with zero and ‘N-1’ as arguments.
- If ‘X’ == ‘Y’, the smoke produced will be zero since there is only one potion.
- If dp[x][y] is already calculated, we will return it.
- Else we will iterate from ‘X’ to ‘Y-1’ and will choose the adjacent indices which we should mix to produce minimum smoke.
- For two adjacent indices, ‘i’ and 'i + 1’, the smoke produced will be the sum of the smoke produced from ‘X’ to ‘i’, smoke produced from ‘i + 1’ to ‘Y’, and the product of the sums of ‘X’ to ‘i’ and ‘i + 1’ to ‘Y’.
- Finally, we will take the minimum smoke from all the possible values, store it in the current state, and then return it.
This approach is also similar to the above approach. Here we will do dynamic programming iteratively. We will do first calculate all the answers of subarrays of length two. Using this we will then calculate the answers for the subarrays of length three. In this way, we will calculate our final answer which will be the answer for the whole array of length ‘N’.
Algorithm:
- We will implement a prefix sum array ‘pref’ to calculate the prefix sum mod 100.
- We will take a two-dimensional array and initialize it with zero.
- Then we will iterate over all the possible lengths of the subarrays(starting from 2) and calculate the optimal answer for the current subarray.
- ‘l+1’ is the length of the subarray. ‘I’ is the starting index and ‘j’ is the ending index.
- Now to calculate the optimal answer for indices ‘i’ and ‘j’, we will iterate from ‘i’ to ‘j’ and will choose the adjacent indices which we should mix to produce minimum smoke.
- For two adjacent indices, ‘I’ and ’I+1’, the smoke produced will be the sum of the smoke produced from ‘X’ to ‘I’, smoke produced from ‘I+1’ to ‘Y’, and the product of the sums of ‘X’ to ‘I’ and ‘I+1’ to ‘Y’.
- we will take the minimum smoke from all the possible values, store it in the ‘DP’ array.
- The output will be the optimal answer considering the whole array. So, ‘DP[0][n-1]’ will be the final output.
