I always love solving Harry Potter theme based problems.This one http://www.spoj.com/problems/MIXTURES/ was fun solving.
Its based on classic DP problem Matrix Chain multiplication.
Task :
Minimize the amount of smoke that Harry can get when mixing all the mixtures together.
Solution:
If you look into the problem statement carefully you will know that harry can mix only adjacent mixtures together. So for example m1,m2,m3 are the mixtures he can either mix m1,m2 first or m2,m3 first.
i.e you can either split the mixture set as {m1} and {m2,m3}
OR
{m1,m2} and {m3}
Let dp[a][b]=minimum smoke produced on mixing mixtures a to b
SO its all about splitting the mixtures into 2 subsets and each of that subsets into 2 sub-subsets and so on such that smoke produced(smoke generated in mixing subsets s1 ans s2 is sum(elements in s1)%100 X sum(elements in s2)%100) is minimized. Aim of the problem boils down to minimizing the product of the 2 mixtures to be mixed.
Hence our recurrence relation is going to be
dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b)) for all k where a<=k<b
Here sum(a,b) defines (sum of all elements from a to b )%100
Base case is dp[i][i]=0
[gist https://gist.github.com/vishnujayvel/9030639]
coding hangover 
dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b))
“min” shouldn’t be there…
No.dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b)) is correct statement. k varies from a to b. we compute dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b) for each k value and finally substitute the minimum to dp[a][b]. I hope you got it cleared now 🙂
what is ‘k’ in the above code int the solve() function?can anyone explain??
K is the variable which is used into split the given mixture array.a<=k<b. Here we are looking for all possible ways to recursively split the mixture array such that minimum smoke is produced.
for case 40,20,60 : according to your explanation mixture can be divided into 40, (20,60) or (40,20),60
but the correct answer is (40,60) ,20.
sorry ,I got it.