TADELIVE - Editorial

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

the answer is 22.
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 :frowning:

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[100001],b[100001],c[10001];

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

Weak testcases in TADELIVE:
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.
My code link is below:
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[1] = 3 and B[1] = 5;
max(x,y) will be 5; which means bob will deliver the 1st pizza but we are updating
dp[1][1] = 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!