Proof of sorting algorithm.


  • 0
    S

    Proof

    Suppose we have an optimal solution:
    S_maximum = min(a_smallest, a_j) + S_other where a_smallest is the smallest number in the integer set and a_j is greater or equal to a_smallest.

    Let us proof the following statement.
    If there is a number (or numbers) a_between_a_smallest_and_a_j between a_smallest and a_j then it must satisfy to the condition: the second number paired with a_between_a_smallest_and_a_j can be only with the same value as a_between_a_smallest_and_a_j, i.e. there are two variants for optimal solution:

    • S_maximum = min(a_smallest, a_j) + S_other, where a_j - next smallest after a_smallest
    • S_maximum = min(a_smallest, a_j) + min(a2, a2) + min(a3, a3) + ... + S_other, where a_smallest <= a2 <= a3 <= a_j.

    We prove by contradiction.
    Suppose there is a number a_i between: a_smallest < a_i < a_j in solution. His paired number is a_k. So the optimal sum looks like: S_maximum = min(a_smallest, a_j) + min(a_i, a_k) + S_other.
    If a_i < a_k, then we can get greater sum with S_maximum = min(a_smallest, a_i) + min(a_k, a_j) + S_other, because a_j > a_i and a_k > a_i . Contradiction!
    If a_i > a_k, then we can greater sum with S_maximum = min(a_smallest, a_k) + min(a_i, a_j) + S_other. Contradiction!
    So for fixed smallest number a1 the optimal solution looks like: min(a1, a2) + other where a2 - next smallest after a1 or min(a1, aj) + min(a2, a2) + min(a3, a3) + other where a1 <= a2 <= a3 <= aj. Both this variants we can rewrote without decreasing sum into min(a1, a2) + min(a2, a3) + min(a3, a3) + min(a3, aj) + min(a4, a5) where a1<=a2=a2(second)=a3=a3=a3=a3<=aj - but this is just sorted numbers paired! So a_smallest can be only paired with next smallest number. Iterating through S_other with this logic we just get solution with sorting idea.

    Main idea

    The logic behind this is if we have an optimal solution S_max = min(a_smallest, a_k) + S_optimal_other we can replace a_k with the next smallest number after a_smallest (a_smallest_2) and put a_k in old a_smallest_2 position without decreasing sum. Repeating this trick for S_optimal_other we get sorted pairs.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.