3
$\begingroup$

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

  1. Sort P from high to low.
  2. Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.

$\endgroup$
  • $\begingroup$ Perhaps you could share the solution with us, and we can help you make it more formal. $\endgroup$ – Yuval Filmus Aug 14 '15 at 22:06
3
$\begingroup$

Let's assume that optimal answer is $A = \{(free_1, paid_1), ..., (free_n, paid_n)\}$ where $\forall i: free_i \le paid_i$, also sort this pairs by $paid$, i.e. $paid_1 \le paid_2 \le ... \le paid_n$.

I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.

If there is such $i$ that $paid_{i-1} > free_i$, take 2 pairs $(free_{i-1}, paid_{i-1}), (free_i, paid_i)$ (in this case we need to pay $paid_{i-1} + paid_{i}$) and swap prices:

  1. In case $free_{i-1} \le free_i$ we got $(free_{i-1}, free_i), (paid_{i-1}, paid_i)$ (need to pay $free_i + paid_i$);
  2. In case $free_{i-1} > free_i$ we got $(free_{i}, free_{i-1}), (paid_{i-1}, paid_i)$ (need to pay $free_{i-1} + paid_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free_i < free_{i-1} = paid_{i-1} < paid_i$).

We have:

  1. $paid_1 \le paid_2 \le ... \le paid_n$, that gives sorted sequence: $\{paid_1, paid_2, ..., paid_n\}$
  2. $\forall i: paid_{i-1} \le free_i \le paid_i$ (more intuition: in sequence from p.1 we insert $free_i$ on appropriate places), that gives sorted sequence: $\{free_1, paid_1, free_2, paid_2, ..., free_n, paid_n\}$

So we show that optimal answer can be expressed in form of sorted array.

$\endgroup$

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.