CHOCOLATE DILEMMA

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 in data structures and algorithms.

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;
    }
 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])));
    }
    }
#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;
    }

Previous post MONOPOLY
Next post RAHUL AND PUZZLE WORLD

Leave a Reply

Your email address will not be published. Required fields are marked *