Mixtures

Posted: 10 Dec, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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:

 

  1. We will implement a prefix sum array ‘PREF’ to calculate the prefix sum mod 100.
  2. Then we will call the ‘solver’ function with zero and ‘N-1’ as arguments.
  3. If ‘X’ == ‘Y’, the smoke produced will be zero since there is only one potion.
  4. Else we will iterate from ‘X’ to ‘Y-1’ and will choose the adjacent indices which we should mix to produce minimum smoke.
  5. 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’.
  6. Finally, we will take the minimum smoke from all the possible values and then return it.
Try Problem