CODEWITHSUNDEEP
algorithm
Sepehr Omidvar
Sepehr Omidvar

Reputation: 137

Greedy Algorithms. How to solve this problem?

Suppose you are given two sets A and B, each containing n positive integers. You can choose to reorder each set however you like. After reordering let ai be the i-th element of set A, and let bi be the i-th element of set B. You then receive a payoff of (a1 ^ b1) × (a2 ^ b2) × ... × (an ^ bn). Give a polynomial algorithm that will maximize the payoff.

Answer: I think if we sort both sets increasingly, the problem will solve. It needs o(nlog(n)) time. Does anyone have a counterexample?

Upvotes: 0

Views: 4617

Answers (3)

Mian Xiong
Mian Xiong

Reputation: 1

I think there could be an easier way to compare (ai^bj * aj^bi) with (ai^bi * aj^bj) when ai < aj and bi > bj, that is to take the logarithm of both. Then the problem transfers to compare the value of bjlog(ai) + bilog(aj) and bilog(ai) + bjlog(aj), and then we can do a simple subtraction operation. And it is easy to tell (bi - bj)log(aj) > (bi - bj)log(ai). So, bjlog(ai) + bilog(aj) > bilog(ai) + bjlog(aj) => ai^bj * aj^bi > ai^bi * aj^bj.

Upvotes: 0

kaya3
kaya3

Reputation: 51152

It's straightforward to prove that the greedy algorithm - i.e. pair the largest number with the largest exponent, then the next-largest number with the next-largest exponent, and so on - is optimal.

Suppose the product includes two terms a[i] ** b[i] and a[j] ** b[j], where a[i] < a[j] and b[i] > b[j]. It follows that (a[i] ** b[j]) * (a[j] ** b[i]) is greater than (a[i] ** b[i]) * (a[j] ** b[j]) because they differ by a factor of (a[j] / a[i]) ** (b[i] - b[j]), which by assumption is a number greater than 1 to the power of a number greater than 0, so this factor is greater than 1. Therefore, we can improve the payoff by swapping b[i] with b[j], and hence the original payout was not optimal because it could be improved upon by making the swap.

It follows that your greedy algorithm is correct in the sense that it does indeed maximise the payoff.

Upvotes: 2

OmG
OmG

Reputation: 18838

As a hint, we can reduce the problem to another simple version. If you log from the formula we will have:

b1 log(a1) + ... + bn log(an)

Now suppose we have two vectors V1 = <b1, b2, ..., bn> and V2 = <a1, a2, ..., an>. Hence, the formula is the dot product of these two vectors (V1.V2). By the definition of the dot product we know that V1.V2 = |V1|*|V2|* cos(theta). By permutating the elements of V1 and V2 we know the norm of V1 and V2 will not change. Hence, we need to maximize cos(theta) (that theta is the degree between V1 and V2). So, we need to minimize theta (to maximize cos(theta)).

Upvotes: 0

Related Questions