What I learnt today — MIXTURES
I have been into competitive coding since few months. Currently I am solving SPOJ problems.
Today, I came across an interesting problem titled MIXTURES. Basically problem statement states that
There are n mixtures arranged in a row. Each mixture has one of 100 different colors (colors have numbers from 0 to 99).One have to mix all these mixtures together. At each step, we can take two mixtures that stand next to each other and mix them together, and put the resulting mixture in their place.When mixing two mixtures of colors a and b, the resulting mixture will have the color (a+b) mod 100.
Also, there will be some smoke in the process. The amount of smoke generated when mixing two mixtures of colors a and b is a*b.Find out what is the minimum amount of smoke that can get when mixing all the mixtures together.
After reading the problem statement, it was obvious that it’s an Dynamic programming problem. I tried solving it for an hour approx but didn’t come up with any answer.
Matrix chain multiplication is the key to solve this problem. I will strongly recommend one to learn MCM first.
Now, coming to this problem, we can see that there are overlapping sub problems here. Suppose there are 3 numbers 40,60 and 20.
we can find the answer in many ways
((40*60)*20) = 0*20 = 20. Smoke = 2400 + 0 = 2400.
(40*(60*20)) = 40*80 = 20. Smoke = 1200 + 3200 = 4400.
Clearly, the second method is better one.
To solve this problem, we will take two arrays one to store the intermediate sum and another to store the intermediate result.
Let’s name both arrays as sum and dp and array is the input array.
Filling the sum matrix
sum[i][j] = sum of the input numbers from index i to index j.
we can clearly say that sum[i][i] = array[i]
Matrix can be filled using this formula
sum[i][j] = (sum[i][j-1] + arr[j])%100; ( we only need to fill the cells above the diagonal of the sum matrix)
sum[i][i] = arr[i];
sum[i][j] = (sum[i][j-1] + arr[j])%100;
Now we have to find the minimum smoke among all the possible answers.
Let’s go lengthwise, what I mean is that we will first consider the sub problems of length 1, then length 2 ans so on…
Let’s take 4 numbers 10,20,30 and 40.
Length 0 :
result = 0 as we need at least two numbers to multiply, right.
so dp[i][i] = 0
possible combinations are 10–20, 20–30 and 30–40
for 10–20, resultant mixture = (10+20)%100 = 30 and smoke = 200.
for 20–30, resultant mixture = (20+30)%100 = 50 and smoke = 600.
for 30–40, resultant mixture = (30+40)%100 = 70 and smoke = 1200.
possible combinations are 10–20-30, 20–30–40.
for 10–20–30, we have two possibilities, (10(20 30)) or ((10 20) 30). we will take the minimum of both. One interesting thing is that we can find the solution of this length using previous length solution.
possible combinations are 10–20–30–40.
similarly, we can do (10 (20 30 40)) or ((10 20) (30 40)) or ((10 20 30) 40).
code for the above explanation :
for(ll i=n-1; i>=0; i — )
dp[i][i] = 0;
for(ll j=i+1; j<n; j++)
dp[i][j] = INT_MAX;
ll val = dp[i][k] + dp[k+1][j] + (sum[i][k]*sum[k+1][j]);
dp[i][j] = min(dp[i][j], val);
final result can be found at dp[n-1].
Happy coding :)