PROBLEM LINK:Author: Tuan Anh DIFFICULTY:Simple PREREQUISITES:greedy PROBLEM:Andy and Bob are pizza delivery guys. They take tips of A[i] and B[i] corresponding to the i^{th} order. Note that each order will be taken by only one person. Andy can take at most X orders and Bob can take Y. You have to divide the orders between Andy and Bob such that total tips is maximized. You are also given a constraint that X + Y ≥ n, which will guarantee that none of the orders will go unprocessed. QUICK EXPLANATION:Primarily there are three possible solutions depending on the subtasks.
EXPLANATION:Let us start with subtasks in increasing order of difficulty. Subtask 1Try brute force solution by assigning each order to either Andy or Bob. You can implement this method either recursively or using bitmasks. For understanding about bitmask, you can refer to this and that link. Pseudo Code ans = 0; // (i, totalTipMoney) signifies that upto now, i orders has been processed, // and totalTipMoney is amount of total tip money for this particular assignment up to now. rec(i, andyOrders, bobOrders, totalTipMoney) { if (i == N) { // i.e. all the orders has been processed if (andyOrders <= X && bobOrders <= Y) { // if the arrangement is valid. ans = max(ans, totalTipMoney); } } else { // try giving this order to Andy rec(i + 1, AndyOrders + 1, BobOrders, totalTipMoney + A[i]); // try giving this order to Bob rec(i + 1, AndyOrders, BobOrders + 1, totalTipMoney + B[i]); } } // inside main function rec(0, 0, 0, 0); // Now ans will be your required answer. Recursive bit mask brute force solution. ans = 0; // we are iterating over all subsets of size N. // If current bit of mask is zero, means that current order is given to Andy // Otherwise it means that order is given to Bob. for (mask = 0; mask < (1 << N); mask++) { cur = 0; // cur denotes the total tip money corresponding to this arrangement of orders. AndyOrders = 0; BobOrders = 0; for (i = 0; i < N; i++) { if (mask & (1 << i)) { cur += A[i]; // Andy takes the order. AndyOrders++; } else { cur += B[i]; // Bob takes the order. BobOrders++; } } if (andyOrders <= X && bobOrders <= Y) { ans = max(ans, cur); } } Time Complexity For bitmask solution, As we know total number of subsets of N items can be 2^N. For each subset (represented by mask), we also execute an inner O(N) loop too. So overall time complexity will be O(2^N * N). Subtask 2We will use a dynamic programming solution. Note that for dynamic programming solution, we need to visualize the process of assigning orders from left to right. So we should think that we are kind of trying to assign the orders from left to right (ie. from order 0 to order N  1). Assume that we are currently at i^{th} position and we have decided the assignment of orders up to now ( i.e. up to (i  1)^{th} position). Now what information do we need to know about the assignment done up to now? Do we really need the information about the exact assignment of orders? Or are we only interested in count of orders assigned to Andy and Bob. Note that we only need to know the number of orders being assigned to Andy. We can find number of orders assigned to Bob easily because we know up to now i  1 orders has been processed. So number of orders of Bob will be i  1  number of orders of Andy. So our state of dp solution will be dp(i, j) which denotes that up to first i orders, j of them has been assigned to Andy. Base Case Transitions Pseudo Code dp(i, j) { if (memo[i][j] != 1) { return memo[i][j]; } res = 0; if (i == N) { // all orders are processed. res = 0; } else { // Decide for order i. // If can give to Andy, try giving it. AndyOrders = j; if (AndyOrders + 1 <= X) { res = max(res, A[i] + dp(i + 1, j + 1)); } // If can give to Bob, try giving it. BobOrders = i  j; if (BobOrders + 1 <= Y) { res = max(res, B[i] + dp(i + 1, j)); } } memo[i][j] = res; return res; } Note that the above explained solution is using forward dp, you can very easily write backward dp too. Some times, backward dp is more intuitive to understand. Backward dp Pseudo Code // Asumming one based indexing. int f[N + 1][X + 1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= X && j <= i; j++) { int x = 0; if (j <= X) { x = f[i  1][j  1] + A[i]; } int y = 0; if ((i  j) <= Y) }{ y = f[i  1][j] + B[i]; } dp[i][j] = max(x, y); } } int ans = 0; for (int j = 0; j <= X; i++) { ans = max(dp[N][j]); } Subtask 3Let us denote D[i] = A[i]  B[i]. Now we will sort all the orders in decreasing order of D.
Now we will process the orders one by one.
Note that the condition X + Y >= n guarantees that we will be able to assign the order to one of the persons. Proof of the Solution As we want to minimize the loss encountered, it is better to process the orders having high possible losses, because we can try to reduce the loss in the starting part. There is no point of doing an order which is high loss after an order with less loss. You can prove it easily by exchange argument. Note that this is an intuitive explanation, More formal proof can be made along the similar lines using loss parameter defined above. Pseudo Code // Create D array. // Sort the orders in the decreasing order of D[i]. totalTipMoney = 0; for (i = 0; i < n; i++) { if (A[i] > B[i]) { if (andyOrders + 1 <= X) { andyOrders++; totalTipMoney += A[i]; } else { bobOrders++; totalTipMoney += B[i]; } } else { if (bobOrders + 1 <= Y) { andyOrders++; totalTipMoney += B[i]; } else { andyOrders++; totalTipMoney += A[i]; } } } // totalTipMoney is our answer. Time Complexity You can use sort function in C++ or Arrays.sort function in Java. You can O(n^2) selection, insertion, bubble sort etc. to solve Subtask 1 and 2. Note that in this problem, for sorting A and B using D array will require use of comparators. For understanding comparators in C++, you can refer to following article written by me. Problems to Practice Please add more problems for practice !! AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
This question is marked "community wiki".
asked 28 Dec '14, 14:00

For all those who are getting partial points, EDIT 1: 4 2 2 5 4 5 2 5 5 7 1 ans=19 4 2 2 5 5 7 1 5 4 5 2 ans=19 4 2 2 5 4 2 2 5 3 3 1 ans=14 4 2 2 5 3 3 1 5 4 2 2 ans=14 2 1 1 5 6 5 7 ans=12 2 1 1 5 7 5 6 ans=12 2 1 1 5 6 6 8 ans=13 4 1 3 7 5 2 2 6 2 9 8 EDIT 2: ans=28 3 2 1 7 4 9 7 2 3 ans=20 EDIT 3: 8 6 8 15 50 77 52 27 62 63 61 350 271 916 438 281 998 125 241 ans=3620 9 5 9 60 98 21 52 9 15 62 74 83 552 893 44 920 52 830 155 40 557 ans=4077 EDIT 4: answered 28 Dec '14, 14:02
my code passed all these testcases. still got 10 points
(28 Dec '14, 14:06)
1
I know it is not a problem, but B[i] cannot be 0 ;)
(28 Dec '14, 14:08)
my solution passed all the above test cases :)
(28 Dec '14, 14:09)
can you add the link of your solution?
(28 Dec '14, 14:09)
@brobear1995: it failed on last test case, your code returns 13, test properly  http://ideone.com/OeLs9e
(28 Dec '14, 14:11)
which one ? but I know they are wrong. I was checking for different greedy approaches.
(28 Dec '14, 14:12)
ohh i am sorry for that case..@betlista
(28 Dec '14, 14:15)
1
@rishabhprsd7: Correct solution should work fine with that, just mentioned ;)
(28 Dec '14, 14:17)
1
@abcdexter24: I added one more test case (last one), you code returns 14 for this one...
(28 Dec '14, 14:18)
Hey btw @betlista how can you edit an answer? Are you in admin panel or is this because of your Karmas?
(28 Dec '14, 14:27)
@rishabhprsd7: According to this  http://blog.codechef.com/2014/11/18/thenewkarmasystem/ it's because of karma...
(28 Dec '14, 14:30)
@betlista please don't check with what I have submitted, i had better solution but couldn't submit in time :/
(28 Dec '14, 14:49)
showing 5 of 12
show all

4 1 3 7 5 2 2 6 2 9 8 should it not be 28? 6+5+9+8 the second last test case http://www.codechef.com/viewsolution/5663226 answered 28 Dec '14, 17:06

subtracting the price array and sorting and then optimizing works.. i have solved this ques by the same method.. is the approach accurate?? answered 28 Dec '14, 17:57

@rishabhprsd7 Getting AC on All these cases but still got 10 points.... Here is my submission link. TADELIVE MY CODE answered 28 Dec '14, 14:11

@rishabhprsd7 Getting AC on All these cases but still got 10 points.... Here is my submission link.solution answered 28 Dec '14, 14:22
dont check solution...just saw your edit for case 1 and 2
(28 Dec '14, 14:24)
Your solution failed for last test case
(28 Dec '14, 14:28)

My simple Algorithm:
for i from 0 to N1 if A[i]>B[i] && X!=0:
print Sum I am also passing all the test cases above. Still I got 10 points. Please help me.Whats wrong with my code.? http://www.codechef.com/viewsolution/5659232 answered 28 Dec '14, 14:23

What happens when A[i] == B[i], who is assigned to collect the tip? I got 10 for my submission and although the code is similar to the one provided in the editorial I am unable to figure what is (logically)wrong in my code. Help would really appreciated. Regards, Ankit answered 28 Dec '14, 14:30
(28 Dec '14, 14:37)
@betlista I know my code is failing for cases but what is logically incorrect with my code and the code in the editorial? Also, when both A[i] and B[i] are same who do we assign to collect the tip?
(28 Dec '14, 14:49)
I think (but didn't test it yet) that logical problem is in
(28 Dec '14, 16:02)
@betlista I guess that's where the error might be. But, when diff==0 how do we decide who to assign the tip to Andy or Bob?
(28 Dec '14, 16:13)
@ankitdhall given the solution is greedy you should make that choice greedily too. Consider that you have sorted the difference array in ascending order. Now if A[i]==B[i] then you know that the difference is zero therefore it will always be beneficial for Bob to take that order(if he can) because further orders ahead will generate more tip for Andy. Consider the simple case 2 1 1 5 6 5 5 Sorted difference array is : 0 1 if Andy takes the first order, total tips are 10. Greedily choosing we always give the order to Bob(if we can) when the difference is zero. In that case tips=11.
(28 Dec '14, 22:08)
@ironmandhruv yea thanks for clearing my doubt! I had done the same thing but I still seem to get WA for 2 cases. Could you help me figure where the logical problem could be? Here's my code: http://www.codechef.com/viewsolution/5665140
(29 Dec '14, 00:35)
showing 5 of 6
show all

http://ideone.com/6dYTti My code works for all these test cases. But in the contest it was wrong for one of the cases for 30 points and one for 60 points.Rest all it was correct answer. answered 28 Dec '14, 15:15
Your code returns 18 for
correct answer is 20, I kind of do not like
(28 Dec '14, 15:53)
no it should be 7+4+9 3 2 1 Hope you understood..!! :)
(28 Dec '14, 16:14)
Thanks . I was doing a silly mistake of interchanging bob and alice's turns. It got accepted now
(28 Dec '14, 16:20)

should not second last case output be 26.. as 1st would deliver 7 and second one would 2+9+8=19 and hence 19+7=26.. and please help me where my code is wrong? http://www.codechef.com/viewsolution/5661711 answered 28 Dec '14, 16:50

Guys give attention to sorting d[i] in decreasing order rather than increasing.. answered 28 Dec '14, 18:32

i got 40 points for this solution answered 28 Dec '14, 19:20
2
Test these 8 6 8 15 50 77 52 27 62 63 61 350 271 916 438 281 998 125 241 you may check these links:
(28 Dec '14, 19:51)
1
i forgot to check the condition
(28 Dec '14, 20:00)
welcome.. :)
(28 Dec '14, 21:25)

@dpraveen: do add the psuedocode for backward dp in subtask 2. answered 28 Dec '14, 19:48
@krish2311: Added, sorry for being so late :(
(29 Dec '14, 15:20)

http://www.codechef.com/viewsolution/5658539 plz somebody check what i missed and got 10 points :( (my code clears all above test cases) answered 28 Dec '14, 23:57
found lot of cases on which your code fails:
(29 Dec '14, 00:32)

I got AC on 10 pts and 30 pts on my sol and TLE on some testcases of the 60 pts. I was finding the maximum in each case which was the problem. So I decided to sort it. Now it runs fast but getting WA in test case of 30 pts and 1 in 60 pts. And My Code is clearing all the testcases mentioned below..I think some minor mistake i am making. Here are my two codes : Getting 40 pts : http://www.codechef.com/viewsolution/5659672 Getting 10 pts : http://www.codechef.com/viewsolution/5666065 Someone pls point out the mistake i am making.... Edit 1 : Got a test case for which i get WA. 6 5 5 76 8 64 12 77 56 397 240 293 287 137 433 My 2nd code gives 1466 and first code gives 1727 (which is the correct one) I still cant figure out the mistake while i am making while sorting. answered 29 Dec '14, 12:07
You are sorting vector
(29 Dec '14, 15:08)
i will edit the mistake in a sec...but still isn't it weird the code passed all but 2 test cases....?
(29 Dec '14, 15:18)
Test cases are not very strong...
(29 Dec '14, 15:41)
that was so lame what i had done...thank u for pointing out the mistake....
(29 Dec '14, 15:42)
1
Believe me, I'm very good in doing similar mistakes :D
(29 Dec '14, 15:43)

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 :D answered 29 Dec '14, 22:50

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[i1][0] + b[i1]; } for(i=1;i<=n;i++) { for(j=1;j<=x&&j<=i;j++) { p=0; if(j<=x) { p = dp[i1][j1]+a[i1]; } q=0; if((ij)<=y) { q = dp[i1][j]+ b[i1]; } 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); } answered 31 Dec '14, 03:18

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 answered 31 Dec '14, 07:21

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 } answered 11 Jan '15, 12:54

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. answered 13 Jul '15, 18:54

I got all the above cases correct but Codechef still shows WA. What could be the reason? This is the code:
answered 27 Dec '17, 08:42

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 answered 28 Dec '17, 23:24

good question, enjoyed solving it. I couldn't score but I knew it was dp @dpraveen :)
@abcdexter24: Actually if one solves this problem completely after the contest, he can practice bitmask, dp, recursion and greedy all in one :)
Are there some good tutorials on state dp ?
For the DP solution should be this part
@dev8546: Yes, corrected.