Can someone please tell me the recurrence tree of this problem.Thanks in advance.
1 Like
#include
#include
#include
#include
using namespace std;
int main() {
int t;
scanf("%d",&t);
int H[501],K[501];
int N,max;
while(t--)
{
int dp[501][1001];
max=0;
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&H[i]);
if(max<H[i])
max=H[i];
}
for(int i=1;i<=N;i++)
scanf("%d",&K[i]);
dp[0][0]=0;
for(int j=1;j<=max*2;j++)
dp[0][j]=1000000000;
for(int i=1;i<=N;i++)
{
for(int j=0;j<=2*max;j++)
{
dp[i][j]=dp[i-1][j];
if(K[i]<=j)
dp[i][j]=min(dp[i][j],1+dp[i][j-K[i]]);
}
}
int sum=0;
for(int i=1;i<=N;i++){
sum=sum+dp[N][2*H[i]];
}
printf("%d",sum);
}
// your code goes here
return 0;
}
```
why my answer is giving WA pls help
The approach I have taken is like this.
Let M[1…1001] be an array , where M[i] denotes the minimum number of refills needed to cover a distance i.
From this we get the recurrence M[i] = min(k = 0 to (i/2)){ M[k] + M[i - k] }
Using a bottom up approach, we can build a solution.
Initially M[i] = inf for all i
IF i is an element of K[i], M[i] = 1
After this we can do the bottom up approach as follows:
for(i = 1 ; i <= 1000 ; i++)
{
for(j = 0 ; j <= (i / 2) ; j++)
{
if(M[i] > (M[j] + M[i - j]))
M[i] = M[j] + M[i - j];
}
}
Finally summing just the distances we need:
sum = 0;
for(i = 0 ; i < n ; i++)
sum += M[2 * h[i]];
printf("%d\n" , sum);
Hope this helps :)
Link to my solution:http://www.codechef.com/viewsolution/5265891
1 Like
I know its a very old question but I was trying it as a practice and noticed a strange thing:
Going by the for loops as in the solution setting give AC. But interchanging the order of for loops gives wrong answer. Any one who can throw some more light?
@betista’s solution and @prakash1529’s comment also highlights the same phenomenon. Any pointers to this mistery?
can anyone tell me what’s wrong with my code? here’s my code CodeChef: Practical coding for everyone
Getting WA, help me to find the error
code: ymxAP0 - Online C++ Compiler & Debugging Tool - Ideone.com
for those who are getting wrong answer by solving like coin change problem and getting AC after interchanging the loop. You are getting wrong answer because you are not checking the overflow condition while updating table[i].i.e. in statement (table[i]=1+table[i-k[j]]), table[i-k[j]] can be INT_MAX and hence 1+table[i-k[j]] can cause overflow. Here is the correct code. It shows AC.
Hope this help.
8 Likes
Hmmm… Surprisingly, just interchanging for loops as given in the solution section is getting AC. How does it makes a difference whether we iterate over {K}-> {H} or {H}-> {K}. Interesting and frustrating!!!
1 Like
I think in your code, there is an extra factor in the complexity.
This is due to the fact that a coin can be used more than once.
So, your worst case complexity is- O(N × max{Hi} × max{Hi}).
@prakash1529 Maybe taking into account cache misses in the target system , your observation makes sense 
What’s wrong with this strategy?
I have used a greedy strategy, such that it selects the biggest Ki such that Ki < H[i]*2, and then subtract that value from H[i]*2 and then apply the same procedure on this new value until H[i]*2 becomes 0.
I have used STL set data structure for this so the complexity is NlogN but I’m getting WA (not TLE).
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
vector<int> H(N);
for (size_t i = 0; i < H.size(); ++i)
cin >> H[i];
set<int, greater<int>> K;
for (int i = 0, k; i < N; ++i)
{
cin >> k;
K.insert(k);
}
int ans = 0;
for (size_t i = 0; i < H.size(); ++i)
{
int h = H[i] * 2;
while (h)
{
int temp = *K.lower_bound(h);
//cout << temp << endl;
h -= temp;
++ans;
}
//cout << endl;
}
cout << ans << endl;
}
}
Greedy strategy will not work in the following case
K: 3 4 5
H:3 4 5
Correct answer: Going to K[0] twice
Greedy strategy will not give any answer, since your answer would be actually 5(which is K[2])+1(which is not present)
I guess the statement that at least one answer exists is a bit confusing
As per the previous questions asked about whether we can use recursion or not, I am here to answer that…
And the answer is a big NO…
eg: consider h[]={10 , 11 } and k[]={4,5}
if we trace the recursion across the twice of maximum i.e., 2*11=22, then we get the tree as:-
we never get minimum for 2x10=20 unlike bottom up approach
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;
}