2
\$\begingroup\$

I am trying to solve this question: https://www.codechef.com/problems/TADELIVE

Andy and Bob are the only two delivery men of Pizza-chef store. Today, the store received N orders. It's known that the amount of tips may be different when handled by different delivery man. More specifically, if Andy takes the ith order, he would be tipped Ai dollars and if Bob takes this order, the tip would be Bi dollars.

They decided that they would distribute the orders among themselves to maximize the total tip money. One order will be handled by only one person. Also, due to time constraints Andy cannot take more than X orders and Bob cannot take more than Y orders. It is guaranteed that X + Y is greater than or equal to N, which means that all the orders can be handled by either Andy or Bob.

Please find out the maximum possible amount of total tip money after processing all the orders

  • 1 ≤ N ≤ 10⁵
  • 1 ≤ X, Y ≤ N
  • X + Y ≥ N
  • 1 ≤ Ai, Bi ≤ 10⁴

I have used a dynamic programming approach:

"""
https://www.codechef.com/problems/TADELIV]
"""

"""
https://www.codechef.com/problems/TADELIV]
"""

from functools import lru_cache


@lru_cache(maxsize=None)
def optimal_sum(x, y, i):
    if i >= len(a):
        return 0
    if x == 0:
        return sum(b[i:])
    if y == 0:
        return sum(a[i:])
    sum_with_a = a[i] + optimal_sum(x-1, y, i+1)
    sum_with_b = b[i] + optimal_sum(x, y-1, i+1)
    return max(sum_with_a, sum_with_b)


n, x, y = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
ans = optimal_sum(x, y, 0)
print(ans)

Sadly this timed out :( How do I make it run faster?

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give a sense of the magnitude of X and Y here for the case that times out? Also, how deep does the LRU cache go before it starts discarding state? \$\endgroup\$ – Eric Lippert Dec 17 '19 at 19:22
  • 1
    \$\begingroup\$ Also, I don't understand your logic for the base case. Suppose X is zero. This means that Andy takes no more orders, so the remaining order tips should be the sum of all the remaining orders for Bob, not just the current order for Bob, right? Can you explain the logic here? \$\endgroup\$ – Eric Lippert Dec 17 '19 at 19:27
  • \$\begingroup\$ @Eric Lippert you're right; fixed it. Added constraints in the question -- they're also present in the link. Also, the cache grows without bound \$\endgroup\$ – nz_21 Dec 17 '19 at 19:36
  • \$\begingroup\$ I must be missing something here, because it seems to require only simple arithmetic, rather than dynamic-programming. Suppose, without loss of generality that A < B. Then Bob should handle all of the last Y orders, and Andy the remainder (i.e. the first N-Y orders). What have I missed? \$\endgroup\$ – Toby Speight Dec 17 '19 at 19:55
  • 1
    \$\begingroup\$ @TobySpeight: Great minds think alike; I just posted an equivalent algorithm in my answer. :) \$\endgroup\$ – Eric Lippert Dec 17 '19 at 20:10
6
\$\begingroup\$

Often it is the case that reformatting the data leads to insights. Let's take a look at the test case:

A: 1 2 3 4 5
B: 5 4 3 2 1

Now let's suppose that we subtract the smaller of each pair from both, and take the sum of the smallers:

A: 0 0 0 2 4
B: 4 2 0 0 0

If we can find the maximum tips available in this problem, the real result will be that amount plus 1 + 2 + 3 + 2 + 1.

Can you now see how to solve the problem more easily?

Unfortunately it appears that the tags are misleading; dynamic programming does not buy you much, but a greedy algorithm does.

Your greedy algorithm works out for that test-case. I'm not sure if it works in general. Could you expand a bit on the intuition?

First off, it should be clear that we can always reduce the problem to one where the columns are of this form where one or both are zero; "subtract the smaller from both" always works.

So the problem now is: we must choose up to X numbers from row A, and up to Y numbers from row B, such that their sum is maximized.

The proposed algorithm is: always take the largest number remaining. Suppose we have:

A: 0 0 2 1 5  -- choose up to 2
B: 4 2 0 0 0  -- choose up to 4

We now have to make assignments, and we do it in order from highest to lowest benefit. Start with the biggest bang:

           A
A: 0 0 2 1 5  
B: 4 2 0 0 0  

Then the next:

   B       A
A: 0 0 2 1 5  
B: 4 2 0 0 0  

Now we have a tie, so pick both:

   B B A   A
A: 0 0 2 1 5  
B: 4 2 0 0 0  

And now we've exhausted A, which leaves

   B B A B A
A: 0 0 2 1 5  
B: 4 2 0 0 0  

What's the intuition that the greedy algorithm works? Examine the first choice. If, say, we gave Bob the 5/0 delivery and take the zero tip, what does that get us? It only gives Andy the opportunity to make the lower-valued "1/0" delivery later on, which is not a win; we've given up five to gain one.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your greedy algorithm works out for that test-case. I'm not sure if it works in general. Could you expand a bit on the intuition? \$\endgroup\$ – nz_21 Dec 17 '19 at 20:12
  • \$\begingroup\$ @nz_21: I've added some thoughts. \$\endgroup\$ – Eric Lippert Dec 17 '19 at 20:29
  • 1
    \$\begingroup\$ Your answer makes the problem seem like child's play. Shame I can't +2 :( \$\endgroup\$ – Peilonrayz Dec 18 '19 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.