 There is very loose test data in this problme.Because my submission got AC but actually my code is not correct in many cases.
https://www.codechef.com/viewsolution/24866074
this code produces wrong output.
example test case-
7 5 2
1 2 3 4 5 6 7
5 4 3 2 1 12 14
produced output->53
correct output->41

for all those who r getting 100% correct answers try this one:
5 1 4
1 1 1 1 1
5 5 5 5 6

hey @tuananh93 in my solution answer of the above test case gives 21 which is wrong but still, I got 100%.
So,plz check it.
also try it in this way:
5 1 4
1 1 1 1 1
6 5 5 5 5.

Hey, please check my sol it is giving 22 and approach is tooo easy.

``````#include <bits/stdc++.h>

using namespace std;

int main(){
int N, X, Y; cin >> N >> X >> Y;
int arrx[N];for(int i = 0; i < N; i++) cin >> arrx[i];
int arry[N];for(int i = 0; i < N; i++) cin >> arry[i];
int diff[N];for(int i = 0; i < N; i++) diff[i] = arry[i] - arrx[i];
int x = 0, y = 0;
sort(diff, diff + N, greater<int>());
int ans = 0;
for(int i = 0; i < N; i++){
ans += arrx[i];
if(y < Y){
if(diff[i] < 0 && y + X >= N) continue;
y++;
ans += diff[i];
}
}
cout << ans;
return 0;
}

// 4 1 3
// 7 5 2 2
// 6 2 9 8``````

I think there is a mistake in solution …
in greedy approach, in else condition … beneath bobOrders + 1<=Y
there should be bobOrders++. but instead andyOrders is written.

@rajesh_rxca Certainly mate. Here is the thing, i have implemented greedy, but it still doesn’t get AC.
I do not know where i am going wrong!
SOL i dont understand what is wrong with my solution, its working fine with all the possible cases i can think of
#include
#include
using namespace std;
int a,b,c;

bool criteria(int i,int j)
{
return c[i]>c[j];
}
int main()
{
long long n,x,y,sum =0;
int i = 0;
cin>>n>>x>>y;
long long d[n];
for(i;i<n;i++)
cin>>a[i];
for(int i = 0;i<n;i++)
{
d[i]=i;
cin>>b[i];
c[i]=a[i]-b[i];

``````}

i=0;
sort(d,d+n,criteria);
if (x>n)
x=n;

while(i<x && c[d[i]]>-1  )
{
sum +=a[d[i]];
i++;

}

while(i+y <= n-1)
{
sum +=a[d[i]];
i++;
//cout<<a[d[i]]<<endl;

}

while(i<n)
{
if(y--)
{
sum=sum+b[d[i]];
i++;
}

}
cout<<sum<<endl;
``````

}

Another way to look at it is we have to prioritise orders in which there is a large difference between the tips of Andy & Bob, as there is large amount of profit to be gained here. Eg:
3 1 2
7 2 9
6 8 6
As we can see order no. 3 should be dealt with before order no. 1 otherwise you could end up making less profit. So it seems like a good idea to use a “priority queue” to prioritise orders which have a large difference between the tips offered to the respective delivery men.
Solution: https://www.codechef.com/viewsolution/30710248

1 Like

My wrong solution (AC): https://www.codechef.com/viewsolution/30290374
Fails for input
4 1 4
1 2 3 4
1 1 1 1

Correct output: 7
My Output: 10

2 Likes

4 3 1
6 2 9 8
7 5 2 2
ANSWER SHOULD BE 28 but my code is giving 29.Still got AC.Please take a look how so…?
https://www.codechef.com/viewsolution/34864494

Test Case defines the Problem:
5 5 1
5 4 4 4 4
6 4 4 4 6

Hello,
Can anyone provide more formal proof of greedy approach using contradiction or greedy exchange or any other resource regarding this

Can anyone Help me regarding the TADELIVE problem.
https://www.codechef.com/viewsolution/43301926

Here’s my code it only fails one case from subtask 2 and one from subrask 3. can anybody please explain why .

https://www.codechef.com/viewsolution/44563608

We can do a little math here, and the solution turns out very simple and easy to understand.
Let A=[a1, a2, …, aN], B=[b1, b2, …, bN] respectively be the arrays containing the money that Andy and Bob can get for the orders from 1 to N.
We use a binary vector M=[m1, m2, …, mN] where 1s represent for orders taken by Andy and 0s represent for ones taken by Bob.
The total money that Andy and Bob can get is computed as:
money = M x A + (1 - M) x B = M x (A - B) + B
where “x” is the dot product operation. As we can see the total money depends on the difference (A-B). To maximize the money, we need to select as many as possible the orders which result in the highest (A_i - B_i) values.

in the DP table
for i=1; and j = 1;
let A = 3 and B = 5;
max(x,y) will be 5; which means bob will deliver the 1st pizza but we are updating
dp = 5; which means one(i=1) pizza has delivered and one (j=1) pizza is deliver by Andy. but actually the that one pizza is deliver by Bob;

I am confused that the DP state is storing the correct delivery information or not.

correct me if I am doing and mistake in understanding the DP states!