Any Intuitive DP solution for Problem CHEFSHOPPING in April,22 COOK OFF?

I was noticing some DP solutions for the problem Contest Page | CodeChef !

I first misread the problem( missed the fact it was at most one operation) and tried Divide and Conquerer, and later nothing was coming to head (Divide and Conquer Totally had taken over my head) and I saw one observation solution which was not so intuitive,

So PLEASE IF ANYONE HAVE ANY INTUITIVE DP solution, PLEASE POST IN THE COMMENTS!

3 Likes

in case you are interested in top down code , Might help …

// DETAILS COULD BE DISTRACTING ...... Somtimes!
// Simple Solution is the Best 
#include"unordered_map"
#include"unordered_set"
#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cassert"
#include"cstdio"
#include"vector"
#include"cmath"
#include"map"
#include"set"
#include"queue"
#include"numeric"
#include"stack"
#include"list"
#define LL long long int
#define INF 1000000000000
#define my_gease ios_base::sync_with_stdio(false);cin.tie(NULL);
#define YES cout<<"YES"<<endl;
#define NO  cout<<"NO"<<endl;
using namespace std;


LL dp[2000000][3][3];
LL recursion(LL index,bool dead,LL dead_left,vector<LL> &L,vector<LL> &R){

    LL N= (LL)L.size();

    if(index==N-1 and dead_left==1 and dead==true){
        return 0LL;
    }
    if(index==N-1 and dead_left==1 and dead==false){
        return 0LL;
    }
    if(index==N-1 and dead_left==2 and dead==false){
        return L[index];
    }
    if(index==N-1 and dead_left==2 and dead==true){
        return (LL)INF;
    }
    if(index==N-1){
        return(LL) INF;
    }
    if(dp[index][dead][dead_left]!=-1){
        return dp[index][dead][dead_left];
    }
    if(dead){
        if(dead_left==0LL){
            return dp[index][dead][dead_left]=min( 
                recursion(index+1LL,false,1LL,L,R) , 
                R[index] + recursion(index+1LL,true,0LL,L,R) );
        }
        else if(dead_left==1LL){

            return dp[index][dead][dead_left]=min(
                recursion (index+1LL,false,2LL,L,R) ,
                R[index]  + recursion(index+1LL,true,1LL,L,R));
        }
        else{
            return dp[index][dead][dead_left]=(LL)INF;
        }
    }
    else{
        if(dead_left==0LL){
            return dp[index][dead][dead_left]=(LL)INF;    
        }
        else if(dead_left==1LL){
            return dp[index][dead][dead_left]=min( R[index] + recursion(index+1LL,true,1LL,L,R),
                        recursion(index+1LL,false,2LL,L,R));
        }
        else{
            return dp[index][dead][dead_left]=min(L[index] + recursion(index+1LL,false,2LL,L,R),
                       L[index] + R[index] + recursion(index+1LL,true,1LL,L,R));
        }

    }
    return 0LL;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    my_gease;
    LL T;
    cin >> T;
    while(T--){
        LL N;
        cin >> N;
        vector<LL> L(N);
        for(auto &it:L){
            cin >> it;
        }
        vector<LL> R(N);
        for(auto &it:R){
            cin >> it;
        }
        for(LL i=0;i<N;i++){
            for(LL j=0;j<3;j++){
                for(LL k=0;k<3;k++){
                    dp[i][j][k]=-1LL;
                }
            }
        }
        LL ans=recursion(0LL,false,1LL,L,R);
        cout<<ans<<endl;
    }
}
1 Like

Hey @maity02saranya :wave:
Try this solution :

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

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	cin>>t;
	while(t--) 
    {
       ll n;
       cin>>n;
       vector<ll> a(n),b(n);
       for(int i=0;i<n;i++)cin>>a[i];
       for(int i=0;i<n;i++)cin>>b[i];
       ll sum= 0;
       for(int i=1;i<n;i++)
       {
           sum+=min(b[i-1],a[i]);
       }

       cout<<sum<<"\n";
	}
}