TADELIVE - Editorial

dynamic-programming
editorial
greedy
ltime19
simple

#1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Simple

PREREQUISITES:

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:

Let us start with subtasks in increasing order of difficulty.

Subtask 1

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*);
		// try giving this order to Bob
		rec(i + 1, AndyOrders, BobOrders + 1, totalTipMoney + B*);
	}
}
// 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*; // Andy takes the order.
			AndyOrders++;
		} else {
			cur += B*; // 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).

Subtask 2

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

Subtask 3

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

Please add more problems for practice !!

AUTHOR’S, TESTER’S and Editorialist’s SOLUTIONS:

setter
tester
editorialist


#2

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


#3

My Simple Solution

Make another array named as SUB*=abs(A*-B*)

After that sort sub and also store their original corresponding index .

Use, Optimizing sorting algo


#4

@rishabhprsd7 Getting AC on All these cases but still got 10 points…
Here is my submission link.
TADELIVE MY CODE


#5

@rishabhprsd7 Getting AC on All these cases but still got 10 points… Here is my submission link.solution


#6

My simple Algorithm:

Sum=0;

for i from 0 to N-1

if A*>B* && X!=0:

   Sum+=A*;

   --X;

else

   Sum+=B*

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


#7

What happens when A* == B*, 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


#8

Can somebody explain the last test case mentioned above?


#9


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.


#10

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


#11

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


#12

subtracting the price array and sorting and then optimizing works… i have solved this ques by the same method… is the approach accurate??


#13

Guys give attention to sorting d* in decreasing order rather than increasing…


#14

i got 40 points for this solution
http://www.codechef.com/viewsolution/5663762 plz tell where my code is lacking :confused:
thanks in advance :slight_smile:
@betlista can u help :slight_smile:


#15

@dpraveen: do add the psuedocode for backward dp in subtask 2.


#16

Can be go via Merge_Sort.


#17

http://www.codechef.com/viewsolution/5658539

plz somebody check what i missed and got 10 points :frowning:
(my code clears all above test cases)


#18

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 :

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.


#19

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 :smiley:


#20

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*[j]=0;
}
}
for(i=0;i<n;i++)
{
cin>>a*;
}
for(i=0;i<n;i++)
{
cin>>b*;
}
for(i=1;i<=n;i++)
{
dp*[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*[j]= max(p,q);
}
}
ans = 0;
for(i=0;i<=x;i++)
{
if(dp[n]>ans)
ans = dp[n]
;
}
cout<<ans<<endl;
return(0);

}