medium problem(mixtures)

general
,
1

someone please explain how to approach https://www.codechef.com/problems/MIXTURES and also mention tags of the problem.thanks

1 Like
2

This seems to be a standard dp problem, which I believe can be solved in O(n^3)

To define a state, Let dp[i][j] be the minimum amount of smoke released to collate all mixtures from i to j (inclusive) into a single mixture. We soon realise that we also need to maintain the value that this subarray [i,j] attains.

More formally, we need to determine 2 values for every range [i,j] :

  1. The minimum smoke released to combine said range into 1 mixture.

  2. The value of the 1 mixture formed by combining.

The former can be done by maintaining a 2d array for each state, where dp[i][j] = min smoke for range [i,j]. The latter can also be an array, where val[i][j] = value of mixture created by [i,j], Or it can be done by mainaitining cumilative sums, and then processing (range_sum)%100 to get the value of the mixture.

Now coming to the recurrence relation, We know that our answer will be dp[0][n-1].

solve(int start, int end):    //solves for subrange [i,j]
    if(dp[start][end])    return dp[start][end]
    if(start==end) return 0    //if only one element, no smoke is emmited
    best = inf   //finding best way to split up the current range
    for(int i = start; i < end; i++)    //Here i is where we break the current range and try to find least smoke emmision 
        best = min(best,solve(start,i)+solve(i+1,end)+val[start][i]*val[i+1][end])    //Any of the methods can be used to determine val[i][j], cost of left subarray + cost of right subarray + cost of merging
    return dp[start][end]=best     //memoize

This was the top down solution, which is usually more intuitive, but has a greater recursive overhead, the bottom up approach is also easy to write

for(int i = 1; i < n; i++)    //i is size of sub array
    for(int j = 0; j < n; j++)    //j is starting index
        for(int k = i; k < j; k++)    //k is the break point
            dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+val[i][k]*val[k+1][j])    //cost of left subarray + cost of right subarray + cost of merging

For bottom up solutions it is necessary for the states to be processed in the topological ordering.

The basic intuition lies in trying all possibilities, for which we can split every subarray in any way. the base case lies when size of subarray is 2, we have to compulsorily mix these mixtures, as the mixtures have to be next to each other. So basically, every time we wrote dp[i][k]+dp[k+1][j]+val[i][k]*val[k+1][j], it meant, process [i,k] and [k+1,j] first optimally, such that now they are neighbours, then mix them to create one single mixture.

I hope this helps.

Read & lt as less than.

2 Likes
3

@s4shyam thank you <@> it seems standard. is it?

4

@mahipalsaran Yes, it is. By standard I mean, the recurrence relation. A similar dag is used for solving a lot of n^3 dp questions.

5

@s4shyam Thanks…