Spoj(MIXTURES) Mixtures – Dynamic Programming

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]

Spoj(NITT8) Dating Rishi

http://www.spoj.com/problems/NITT8/

Theres a nlogn solution for this.

Store the (height,position) array as a vector of pairs

Now our aim is to maximize the friend quotient(i,e maximize both terms a and b in the formula given down)

FQ = minimum height of the 2 girls {term a}* absolute diff of the position of the 2 girls{term b}

Sort the vector based on height

 After sorting , considering each height element h of the pair (starting from the maximum. i.e is right side) as the candidate for the minimum height .Let its postion be i.

We have to maximize the difference too.(maximize b). So for each position i ( position where our candidate height h is located) find the value that is most maximum than it and store it in max1.also find the value that is most minimum that it and store it in min1.

You will find out that you have to check only the right side of the position i to find the max1 and min1 since if we go left our height value will be reduced. 

Calculate the F.Q at each iteration and store the maximum F.Q in a variable and update the variable at each stage.

[gist https://gist.github.com/vishnujayvel/8996647]