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.
#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.