×

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.5k52132169
accept rate: 20%

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)

 3 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●11●41 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●2●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 23●3 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 In the forward DP, when the i^th order is taken by Bob shouldn't the statement be res = max(res, A[i] + dp(i + 1, j )); rether than res = max(res, A[i] + dp(i + 1, j + 1)); ?? link This answer is marked "community wiki". answered 28 Dec '14, 15:03 1 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:

×14,487
×1,790
×1,005
×877
×69

question asked: 28 Dec '14, 14:00

question was seen: 8,354 times

last updated: 28 Dec '17, 23:24