×

Author: Tuan Anh
Tester: Gedi Zheng
Editorialist: Praveen Dhinwa

Simple

greedy

# PROBLEM:

Andy and Bob are pizza delivery guys. They take tips of A[i] and B[i] corresponding to the ith 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.

• For passing the first subtask, you can directly use brute-force solution in which you will try to give each order to either Andy or Bob while respecting the X and Y condition.

• For passing the second subtask, you can use a dynamic programming solution having state f(i, j) denoting maximum total tip money among the first i orders where Andy has taken j orders up to now.

• For passing third subtask, you can use following greedy strategy. Sort all the orders by D[i] = ]|A[i] - B[i]|. Process the order one by one in the above sorted order and assign each order to either Andy or Bob greedily depending on relation between A[i] and B[i].

# EXPLANATION:

Try 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
Recursive brute force solution.

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);


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.
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 recursive solution, As total number of subsets of size N can be 2^N. (As each item can be either taken or not taken). So overall time complexity will be O(2^N).

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).

We 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 ith 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
i is equal to N, then as all the orders has been processed, tip money obtained from the remaining part will be zero.

Transitions
Now let us see the transitions. So we are currently at i^th position. For the current order, we will try both the possibilities ie. we will try to give it to Andy or Bob both depending on whether their count of orders taken has not exceeded from the desired limit (ie. X for Andy and Y for Bob).

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;
}
// inside the main function.
fill the memo array with -1.
ans = dp(0, 0)
// ans will be desired answer.


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
f[i][j] = Maximum tip money that can be got in first i order where Andy has taken j orders.
We can make come to f[i][j] from following states.
// give this current order to Andy. Can only be done when j > 0 and j <= X.
f[i - 1][j - 1] + A[i] where j > 0 and j <= X.
// give this current order to Bob. Can only be done when (i - j) > 0 and (i - j) <= Y.
f[i - 1][j] + B[i] where j > 0 and j <= X.
We will simply take the max of these two states to get the answer for f[i][j].

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]);
}


Let 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.
We can have following two cases:

• If A[i] > B[i], then we will try to assign it to Andy if possible (If after the assignment, limit of orders is not crossed). Otherwise we will assign it to Bob.

• If B[i] > A[i], then we will try to assign it to Bob if possible. Otherwise we will assign it to Andy.

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
Assume that for some i, A[i] > B[i] and you assigned order to Bob, loss encountered due to this assignment is D[i]. Similarly, for some i, B[i] > A[i] and you assigned order to Andy, loss encountered due to this assignment is D[i].

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];
}
}
}


Time Complexity
As we are only sorting an array of size n using comparator using D array. We can use Quicksort and mergesort which take O(n log n) time.

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

# AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:

This question is marked "community wiki".

2.4k52124164
accept rate: 21%

good question, enjoyed solving it. I couldn't score but I knew it was dp @dpraveen :-)

(28 Dec '14, 14:10)
1

@abcdexter24: Actually if one solves this problem completely after the contest, he can practice bitmask, dp, recursion and greedy all in one :)

(28 Dec '14, 14:27)

Are there some good tutorials on state dp ?

(28 Dec '14, 14:41) 3★

For the DP solution should be this part

    BobOrders = i - j;
if (BobOrders + 1 <= Y) {
res = max(res, B[i] + dp(i + 1, j + 1));
}

BobOrders = i - j;
if (BobOrders + 1 <= Y) {
res = max(res, B[i] + dp(i + 1, j));
}

(28 Dec '14, 14:46) 2★

@dev8546: Yes, corrected.

(28 Dec '14, 14:53)

 1 For all those who are getting partial points, try these case: 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: More test Cases with correct Output: http://ideone.com/rOMkjI answered 28 Dec '14, 14:02 1.9k●1●10●39 accept rate: 14% 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/the-new-karma-system/ 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
 1 My Simple Solution Make another array named as SUB[i]=abs(A[i]-B[i]) After that sort sub and also store their original corresponding index . Use, Optimizing sorting algo answered 28 Dec '14, 14:06 2★ambika93 81●1●8 accept rate: 0% So when SUB[i] equals SUB[i-1] you will check the two arrays (take the maximum). Nice approach, will check it. (28 Dec '14, 14:13)
 1 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 11 accept rate: 0% 1 yes it should be 28 (28 Dec '14, 17:08)
 1 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 11 accept rate: 0%
 0 @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 21●2 accept rate: 0% 1 Your code returns 14 for: 2 1 1 5 6 6 8  (28 Dec '14, 14:15)
 0 @rishabhprsd7 Getting AC on All these cases but still got 10 points.... Here is my submission link.solution answered 28 Dec '14, 14:22 2★emin3m 62●9 accept rate: 3% dont check solution...just saw your edit for case 1 and 2 (28 Dec '14, 14:24) emin3m2★ Your solution failed for last test case http://ideone.com/9g6mFg (28 Dec '14, 14:28) i edited that case because according to constraints 0 cannot be the tip value.. but if your code was passing previous case then it will pass this too..!! also as @betlista mentioned your code fails on last case add by @betlista... (28 Dec '14, 14:31)
 0 My simple Algorithm: Sum=0;  for i from 0 to N-1 if A[i]>B[i] && X!=0:  Sum+=A[i]; --X; else Sum+=B[i]  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 28●6 accept rate: 0% Check last test case 2 1 1 5 6 6 8  (28 Dec '14, 14:26)
 0 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 Link to code answered 28 Dec '14, 14:30 21●2 accept rate: 0% Your code fails with 2 1 1 6 8 5 6  should be 13, your code returns 12 - http://ideone.com/CpHHDI (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 if(v->first<=0 && a
 0 Can somebody explain the last test case mentioned above? answered 28 Dec '14, 14:32 26●1 accept rate: 33% 1 Because both can deliver just one, the max is when Andy deliver first one for 5 and Bob second one for 8. Bob cannot deliver both... (28 Dec '14, 14:36) as both can deliver only one so there can be two combinations either (bob get 6 and andy get 6 which is equal to 12) or (andy get 5 and bob get 8 which is equal to 13), so 13 is the answer and not 12..!! (28 Dec '14, 14:45)
 0 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 1●1 accept rate: 0% Your code returns 18 for 3 2 1 7 4 9 7 2 3  correct answer is 20, I kind of do not like cmp function, but maybe I'm wrong... (28 Dec '14, 15:53) no it should be 7+4+9 3 2 1 7 4 9 7 2 3 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)
 0 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 1.0k●1●9 accept rate: 19% 1 it should be 28 6+5+9+8 (28 Dec '14, 17:09) Thanks :) now I get it.. (28 Dec '14, 17:22)
 0 Guys give attention to sorting d[i] in decreasing order rather than increasing.. answered 28 Dec '14, 18:32 1 accept rate: 0%
 0 i got 40 points for this solution http://www.codechef.com/viewsolution/5663762 plz tell where my code is lacking :/ thanks in advance :) @betlista can u help :) answered 28 Dec '14, 19:20 5★root8950 63●4 accept rate: 0% 2 Test these 8 6 8 15 50 77 52 27 62 63 61 350 271 916 438 281 998 125 241 your output:3588 correct output:3620 9 5 9 60 98 21 52 9 15 62 74 83 552 893 44 920 52 830 155 40 557 your output:4054 correct output:4077  you may check these links: Your Code: http://ideone.com/KCvugn AC Code:http://ideone.com/rOMkjI (28 Dec '14, 19:51) 1 i forgot to check the condition thanks :) (28 Dec '14, 20:00) root89505★ welcome.. :) (28 Dec '14, 21:25)
 0 @dpraveen: do add the psuedocode for backward dp in subtask 2. answered 28 Dec '14, 19:48 11●2 accept rate: 0% @krish2311: Added, sorry for being so late :( (29 Dec '14, 15:20)
 0 Can be go via Merge_Sort. answered 28 Dec '14, 21:19 2★ipg2014 1 accept rate: 0%
 0 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 3★raks8877 1 accept rate: 0% found lot of cases on which your code fails: Check these: Your Output: http://ideone.com/CXnUov AC output: http://ideone.com/rOMkjI (29 Dec '14, 00:32)
 0 I got AC on 10 pts and 30 pts on my sol and TLE on some test-cases 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 test-cases mentioned below..I think some minor mistake i am making. Here are my two codes : Getting 40 pts : 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 1●2 accept rate: 0% You are sorting vector v` and then you are not using it. I missed something? (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)
 0 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 5●2 accept rate: 0%

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);

}

2★piya210
1
accept rate: 0%

 0 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 0★zstring 1 accept rate: 0%
 0 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) { } answered 11 Jan '15, 12:54 2★ybatra 1 accept rate: 0%
 0 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 0★codeius 11 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×11,590
×1,259
×780
×716
×68

question asked: 28 Dec '14, 14:00

question was seen: 6,486 times

last updated: 13 Jul '15, 18:54