DBOY - Editorial

why we cant use recursive approach? please elaborate more

Why can’t we simply use Greedy approach? For example, in the sample test case we can simply fill the tank 4 times on the 5 litres station.
Edit: I realised my mistake, re-read the question. Now, it looks like the Coin Change Problem.

https://www.codechef.com/viewsolution/26789381
used 1-d dp can be done like this as well

#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long int
using namespace std;

int main() {
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
    
        int km[n],fuel[n],dp[2000];
    
        for(int i=0; i<n; i++) cin>>km[i];
        for(int i=0; i<n; i++) cin>>fuel[i];
    
        for(int i=0; i<=1000; i++) dp[i] = mod;
    
        for(int i=0; i<n; i++){
            dp[fuel[i]] = 1;
        }
    
        for(int i=0; i<n; i++){
            for(int j=0; j<1001; j++){
                if(dp[j]!=mod){
                    if(j+fuel[i]<1001){
                        dp[j+fuel[i]] = min(dp[j+fuel[i]], dp[j]+1);
                    }
                }
            }
        }
    
        ll ans = 0;
        for(int i=0; i<n; i++){
            ans+=dp[2*km[i]];
        }
    
        cout<<ans<<'\n';
    }
    return 0;
}

My solution

How’s this possible??

My approach is also similar to coin change but used ID dp array
#include <bits/stdc++.h>
using namespace std;

    int main() {
        
        int T;
        cin>>T;
        
        while(T--)
        {
            int n;
            cin>>n;
            int a[n],b[n],c[n],i,j,cn=0,x,y;
            
             for(i=0;i<n;i++)
            {cin>>a[i];
            a[i]*=2;
                
            }
            for(i=0;i<n;i++)
            {cin>>b[i];
            
                
            }
            sort(a,a+n);
            int n1=a[n-1];
            int dp[n1];
            sort(b,b+n);
            dp[0]=0;
            for(i=1;i<=n1;i++)
            { x=100000;
        
            dp[i]=x;
                for(j=0;j<n;j++)
                {
                if(i<b[j])
                 break;
                  if(1+dp[i-b[j]]<x)
                  x=1+dp[i-b[j]];       //whenever there is a valid disatance to cover assign the value to x. 
                  dp[i]=x;
                }
                
            }
            
            for(i=0;i<n;i++)
      { cn+=dp[a[i]];
        
          
      }
       cout<<cn<<'\n';
        }



    	return 0;
    }

Hello Coders!!
Pls help me to find whats wrong with this code. i am getting WA.

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

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int i,n,left = 0,count = 0, innercount;
cin>>n;
int *dilevery = new int[n];
int *station = new int[n];
for(i = 0; i<n; i++){
cin>>dilevery[i];
dilevery[i] *=2;
}
for(i = 0; i<n; i++)
cin>>station[i];
for(i = 0; i<n; i++){
innercount = 0;
int dil = dilevery[i];
int inc = station[i];
if(dilevery[i] <= left){
left = left - dilevery[i];
continue;
}
dilevery[i] = dilevery[i] - left;
while(dilevery[i] > 0){
dilevery[i] = dilevery[i] - station[i];
if(innercount > 0)
station[i] = station[i] + inc;
innercount++;
count++;
}
left = station[i] - dil;
}
cout<<count<<endl;
delete [] dilevery;
delete [] station;
}
return 0;
}

A greedy solution won’t work. Consider K[]={1,3,4,5} and H[i]=7…greedy solution returns 3(ie. 5+1+1) but the optimal solution is 2(ie. 4+3)

H:{4 2 3 1}
K:{1 4 3 3}
why 6 can’t be an optimal ans for this case??

I am using Java for this. Since I am trying to find minimum value I am initially filling the dp table with large values.
Here when I am filling dp table with Long.MAX_VALUE I am getting WA but when I am filling dp table with 10000 I am getting AC.
Why is this?
Here is my code:
https://www.codechef.com/viewsolution/32461370

UNABLE TO UNDERSTAND WHY I AM GETTING TLE…I USED MEMOIZATION APPROACH

int arr[1005][505];

ll int solve(vectorfuel,ll int dist,ll int n)
{

if(dist==0)
return 0;

else if(n==0 && dist!=0)
return INT_MAX;

else if(dist<0)
return INT_MAX;

else if(arr[dist][n]!=-1)
return arr[dist][n];

else
return arr[dist][n]=min(1+solve(fuel,dist-fuel[n-1],n),solve(fuel,dist,n-1));

}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);

tc()
{
ll int n,temp,a; vector fuel ; vector dis;
cin>>n;
temp=n;
while(temp–)
cin>>a,dis.pb(a); // pb is push_back
temp=n;
while(temp–)
cin>>a,fuel.pb(a);
rsort(fuel); //reverse sort
fsort(dis); // simple sort

ms(arr,-1);
ll int ans=0;

ans=solve(fuel,2*dis[n-1],n);

ans=0;
for(int i=0;i<=n-1;i++)
ans+=arr[2*dis[i]][n];

cout<<ans<<endl;
}
return 0;
}

After assign
for j = 1; j ≤ max{2 × H[i]}; j++:
dp[j] = Integer.MAX_VALUE
max sure if you use Integer.MAX_VALUE function it not work so you need to Integer.MAX_VALUE/10
assign

Thank you for this explanation.