OSQUE - Editorial

editorial
, ,
1

OSQUE - Editorial

Problem Link:

Practice

Contest

Author, Tester and Editorialist:-
tejaram15

Difficulty:

Easy

Pre-Requisites:

Matrix chain multiplication

Problem Statement:

Given an array of integers and all are to be combined. Minimize the total multiplication value.

Explanation:

This is a varient of matrix chain multiplication problem. If you observe carefully you can perform the combine operation on consequetive elements only. So for example m1,m2,m3 are the processes you can either combine m1,m2 first or m2,m3 first.

Let dp[a][b]=minimum COUPLING TIME! produced on combining a and b.

So problem is all about splitting the given number of processes into two subsets, Dividing them further into two subsets and so on. Aim reduces down to minimizing the product of two processes to be combined.

So The recurrance relation follows:-

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

Psuedo Code: 
    for(int i=0;i < n;i++)

    {

        cin>>a[i];

        dp[i][i].first=a[i];

        dp[i][i].second=0;

    }

    for(int l=2;l < = n;l++)

    {

        for(int i=0;i < n-l+1;i++)

        {

            int j=i+l-1;

            dp[i][j].second=1000000000;

            for(int k=i;k < j;k++)

            {

                long long q = dp[i][k].second + dp[k+1][j].second + dp[i][k].first * dp[k+1][j].first;

                if(q < dp[i][j].second)

                {

                    dp[i][j].first = (dp[i][k].first + dp[k+1][j].first) % 100;

                    dp[i][j].second = q;

                } 

            }

        }

    }

    cout << dp[0][n-1].second << "\n";

</div>

Time Complexity: O(N2)

Solution : Here