CHOCOLATE DILEMMA

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Dynamic programming

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Arnab can take one candy from each row of candies but with the restrictions imposed:

1. There are 3 sections in each row;
2. If he takes candy from jth section in the ith row,then in (i+1)^th row ,he can’t choose candy from the same section i.e. jth section.

See original problem statement here

For Example :

6 6 
1 3 5 2 4 6 
6 4 5 1 3 2 
1 3 5 2 4 6 
6 4 5 1 3 2 
6 4 5 1 3 2 
1 3 5 2 4 6

Arnab selects sweets 
row 1: 6
row 2: 6
row 3: 6
row 4: 6
row 5: 5
row 6: 6
sum =35

OBSERVATION:

To get the maximum sum of sweetness values,he must select sweets with maximum sweetness value from each section keeping in mind the constraints mentioned.

Also,you could observe that of all the values of each section ,only the maximum one is relevant.
For example:

n=3,m=6;
1 3 5 2 4 6 
6 4 5 1 3 2 
1 3 5 2 4 6

For the first row,The relevant values for each section are:
section 1: max(1,3) i.e. 3
section 2: max(5,2) i.e. 5
section 3: max(4,6) i.e. 6

SOLVING APPROACH:

This question has a simple and elegant dynamic programming approach.

Let’s define a funtion sweetness_r(i,s) , where i denotes the row which we are currently on and s denotes the section. It is clearly mentioned in the question that we have only 3 sections.Therefore,

sweetness_r(i,0)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,2));

sweetness_r(i,1)=a[i][1]+max(sweetness_r(i,0),sweetness_r(i,2));

sweetness_r(i,2)=a[i][0]+max(sweetness_r(i,1),sweetness_r(i,0));

Then print the maximum of sweetness_r(n,0),sweetness_r(n,1) and sweetness_r(n,2) ,where n is the number of rows.

SOLUTIONS:

 #include <stdio.h>
     int max(int x,int y)
    {
    if(x>y)
     return x;
    return y;
    }
    int main()
    {
    //write your code here
    int n,m;
    scanf("%d%d",&n,&m);
    int a[n][3];
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<3;j++)
    {int mx=0;
      for(int c=0;c<m/3;c++)
      {int x;
        scanf("%d",&x);
        mx=mx>x?mx:x;
      }
      a[i][j]=mx;    }
    }
     int dp[n][3];
    dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
     for(int i=1;i<n;i++)
    {
    for(int j=0;j<3;j++)
    {
      if(j==0)
      dp[i][j]=a[i][j]+max(dp[i-1][1],dp[i-1][2]);
      if(j==1)
      dp[i][j]=a[i][j]+max(dp[i-1][2],dp[i-1][0]);
      if(j==2)
      dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][1]);

    }
    }
     printf("%d",max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])));
    return 0;
    }#include <stdio.h>

int main(void) {
	// your code goes here
	return 0;
}

#include <bits/stdc++.h>
     using namespace std;

    int main()
    {
    //write your code here
    int n,m;
    cin>>n>>m;
    int a[n][3];
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<3;j++)
    {int mx=0;
      for(int c=0;c<m/3;c++)
      {int x;
        cin>>x;
        mx=max(mx,x);
      }
      a[i][j]=mx;    }
    }
     int dp[n][3];
    dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
     for(int i=1;i<n;i++)
    {
    for(int j=0;j<3;j++)
    {
      if(j==0)
      dp[i][j]=a[i][j]+max(dp[i-1][1],dp[i-1][2]);
      if(j==1)
      dp[i][j]=a[i][j]+max(dp[i-1][2],dp[i-1][0]);
      if(j==2)
      dp[i][j]=a[i][j]+max(dp[i-1][0],dp[i-1][1]);

    }
    }
     cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
    return 0;
    }

 import java.util.*;

    class solution{
    public static void main (String[] args) {

    Scanner sc=new Scanner(System.in);

    int n=sc.nextInt();
    int m=sc.nextInt();

    int a[][]=new int[n][3];
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<3;j++)
    {
      int mx=0;
      for(int c=0;c<m/3;c++)
      {
        int x=sc.nextInt();
        mx=Math.max(mx,x);
      }
      a[i][j]=mx;    
     }
    }
     int dp[][]=new int[n][3];
     dp[0][0]=a[0][0];dp[0][1]=a[0][1];dp[0][2]=a[0][2];
     for(int i=1;i<n;i++)
     {
     for(int j=0;j<3;j++)
     {
      if(j==0)
      dp[i][j]=a[i][j]+Math.max(dp[i-1][1],dp[i-1][2]);
      if(j==1)
      dp[i][j]=a[i][j]+Math.max(dp[i-1][2],dp[i-1][0]);
      if(j==2)
      dp[i][j]=a[i][j]+Math.max(dp[i-1][0],dp[i-1][1]);
    }
    }
     System.out.print(Math.max(dp[n-1][0],Math.max(dp[n-1][1],dp[n-1][2])));
    }
    }

This article tried to discuss Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic programming you can check out MYCODE | Competitive Programming.