RAM_SAMA- EDITORIAL

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given 3 different integer arrays A,B,C each of size N and you have to choose N integers under the constraints that the ith integer will be either A_i or B_i or C_i and i^{th} and (i+1)_{th} integer cannot be from the same array. Under these conditions print the maximum possible sum of the chosen integers.

QUICK EXPLANATION:

Use dynamic programming to solve the problem. The dp state will be 2-dimensional. Read explanation for detailed approach.

EXPLANATION:

It’s a standard dp problem.

Iterative approach

Let us define dp[i][j] as maximum sum obtainable when we have processed i maids and we choose the i_{th} maid to do the j_{th} job.

So clearly, if the i_{th} maid is doing the j_{th} job that means the (i-1)_{th} maid was chosen to do jobs other than j_{th} job.

So we can now see the transitions too.

Let the jobs be numbered 0,1 and 2.
Base values will be set as : dp[0][0]=vaccuming[0],dp[0][1]=laundry[0] and dp[0][2]=dishwashing[0];
And then the transitions will be as follows:

dp[i][0]=max(dp[i-1][1],dp[i-1][2])+vaccuming[i];
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+laundry[i];
dp[i][2]=max(dp[i-1][0],dp[i-1][1])+dishwashing[i];

The answer to the problem will thus be max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});

Recursive approach

It’s similar to the iterative approach.
If we are choosing the i_{th} maid to do the j_{th} job, that means (i+1)_{th} maid can’t do the j_{th} job.

Let the jobs be numbered 0,1 and 2.
Let us define a memoization table and set dp[i][j] as maximum sum obtainable from the maids numbered from i to N-1 , when we have processed i-1 maids and we choose the i_{th} maid to do the j_{th} job.

The transition will be :

dp[i][0]=max(dp[i+1][1],dp[i+1][2])+vaccuming[i];
dp[i][1]=max(dp[i+1][0],dp[i+1][2])+laundry[i];
dp[i][2]=max(dp[i+1][0],dp[i+1][1])+dishwashing[i];

See the tester solution for reference code.

SOLUTIONS:

Setter's/Editorialist's Solution 
    #include<bits/stdc++.h>
    using namespace std;
     
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		int n;
    		cin>>n;
    		
    		int v[n],l[n],d[n];
    		for(int i=0;i<n;i++)
    			cin>>v[i];
     
    		for(int i=0;i<n;i++)
    			cin>>l[i];
    		
    		for(int i=0;i<n;i++)
    			cin>>d[i];
    		
    		long long dp[n][3];
    		memset(dp,0,sizeof(dp));
    		
    		dp[0][0]=v[0];
    		dp[0][1]=l[0];
    		dp[0][2]=d[0];
    		
    		for(int i=1;i<n;i++)
    		{
    			for(int j=0;j<3;j++)
    			{
    				dp[i][0]=max(dp[i-1][1],dp[i-1][2])+v[i];
    				dp[i][1]=max(dp[i-1][0],dp[i-1][2])+l[i];
    				dp[i][2]=max(dp[i-1][0],dp[i-1][1])+d[i];
    			}
    		}
     
    		cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<'\n';
    		
    	}
    	return 0;
    }
Tester's Solution 
CodeChef submission 34620964 (C++17) plaintext list. Status: AC, problem RAM_SAMA, contest FTCF20TS. By sibasish_14 (sibasish_14), 2020-06-22 00:02:07.

    #include<bits/stdc++.h>
    #define mod 1000000007
    #define F first
    #define S second
    #define pb push_back
    #define all(v) v.begin(),v.end()
    #define rall(v) v.rbegin(),v.rend()
     
    using namespace std;
    typedef long long int ll;
     
    ll n,a[100010][3];
    ll dp[100010][3];
     
    ll solve(ll idx,ll job)
    {
        if(idx == n+1)
            return 0;
        if(dp[idx][job] != -1)
            return dp[idx][job];
        ll res=0,i;
        for(i=0;i<3;i++)
        {
            if(i == job)
                continue;
            res=max(res,solve(idx+1,i));
        }
        res+=a[idx][job];
        return dp[idx][job]=res;
    }
     
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        ll t=1;
        cin>>t;
        while(t--)
        {
            ll i,j,ans=0;
            cin>>n;
            for(j=0;j<3;j++)
            {
                for(i=1;i<=n;i++)
                {
                    cin>>a[i][j];
                    dp[i][j]=-1;
                }
            }
            ans=max({solve(1,0),solve(1,1),solve(1,2)});
            cout<<ans<<"\n";
        }
        return 0;
    }
3 Likes