TADELIVE - Editorial

editorial
, , , ,
61

i will edit the mistake in a sec…but still isn’t it weird the code passed all but 2 test cases…?

62

@krish2311: Added, sorry for being so late :frowning:

63

Test cases are not very strong…

64

that was so lame what i had done…thank u for pointing out the mistake…

65

Believe me, I’m very good in doing similar mistakes :smiley:

1 Like
66

my D[j] = Bob[j] - Andy[j] and then I sort array D (in descending order) using comparable interface so that I can store index . After that I loop through array D and give all orders to Bob until I find a value D[j] less than 0 or j reaches max orders Bob can deliver. The remaining orders are assigned to Andy … Got AC :smiley:

67

why this code is showing sigsegv error??
can any body answer??

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
int n,x,y,ans,i,j,p,q;
cin>>n>>x>>y;
int a[n],b[n];
int dp[n+1][x+1];
for(i=0;i<=n;i++)
{
for(j=0;j<=x;j++)
{
dp[i][j]=0;
}
}
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n;i++)
{
cin>>b[i];
}
for(i=1;i<=n;i++)
{
dp[i][0] = dp[i-1][0] + b[i-1];
}
for(i=1;i<=n;i++)
{
for(j=1;j<=x&&j<=i;j++)
{
p=0;
if(j<=x)
{
p = dp[i-1][j-1]+a[i-1];
}
q=0;
if((i-j)<=y)
{
q = dp[i-1][j]+ b[i-1];
}
dp[i][j]= max(p,q);
}
}
ans = 0;
for(i=0;i<=x;i++)
{
if(dp[n][i]>ans)
ans = dp[n][i];
}
cout<<ans<<endl;
return(0);

}

68

can anyone explain me why greedy technique is giving optimal solution. I am not able to convince myself why greedy is giving optimal solution. I have read the exchange argument, but not able to relate it.

Thanks

69

We don’t need below condition at line number 6 in backward dp as It has already been taken care in for loop at line number 4
if (j <= X) {

}

70

Guys can someone explain me in the test case given in the program andy and bob have 3 orders each
5 3 3
1 2 3 4 5
5 4 3 2 1

Andy can be assigned the last 3 orders of the first row and bob can be assigned the first three orders of the second row.Hence the total comes up to 24 yet we get an o/p of 21 why is that.

71

I got all the above cases correct but Codechef still shows WA. What could be the reason?

This is the code:

#include<iostream>
#include<vector>

typedef long long int ll;

using namespace std;

ll mem_total(ll N, ll *A, ll *B, ll X, ll Y, ll **mem)
{
	if(N==0)
		return 0;

	if((X>0 && mem[X-1][Y] != 0) && (Y>0 && mem[X][Y-1] != 0))
		mem[X][Y] = max(A[N-1] + mem[X-1][Y], B[N-1] + mem[X][Y-1]);
	else
		mem[X][Y] = max(X>0?(A[N-1]+mem_total(N-1, A, B, X-1, Y, mem)):0,
					Y>0?(B[N-1]+mem_total(N-1, A, B, X, Y-1, mem)):0);
}

main()
{
	ll N, X, Y;

	cin>>N>>X>>Y;
	
	ll **mem;

	mem = new ll*[X+1];
	for(int i=0; i<=X; i++)
		mem[i] = new ll[Y+1];

	ll A[N], B[N];

	for(ll i=0; i<N; i++)
		cin>>A[i];
	for(ll i=0; i<N; i++)
		cin>>B[i];

	mem_total(N, A, B, X, Y, mem);

	cout<<mem[X][Y]<<endl;
}
72

a great question ,
make me realize that my DP approach was cyclic and was getting wrong ans.
took me over an hour to figure it our