← All solutions

Shortest judge solution: 541 bytes. Shortest team solution (during contest): 517 bytes.

This problem is also pretty easy. We describe a way to determine if a given target difference d is possible to achieve; finding the minimum is then a simple matter of binary search.

Sort the inputs so that p₁ ≤ p₂ ≤ . . . p_2nk . First observe that we may without loss of generality assume that in an optimal solution, the smallest outputs in each pair of chips will be of the form p_i , p_i+1 (so that the power output difference is p_i+1 − p_i ).

Let us say that the first battery of a machine is the one with smallest power in the machine. Note that if the first battery of a machine is p_i then by observation above we can assume that the power difference of that machine is p_i+1 − p_i .

Now consider the machines sorted in increasing order of power of their first battery. Clearly, the first machine has power difference p₂ − p₁ . For the second machine, the first battery can be any one of p₃ , . . . , p_2k+1 . We then greedily choose the first i^∗ ≥ 3 such that p_{i^∗ +1} − p_i^∗ ≤ d, and use this for the second battery (if no such i^∗ ≤ 2k + 1 exists, there is no solution). Then we look at the third machine. The first battery of this can be either of p_{i^∗ +2} , . . . , p_4k+1 , and we again greedily choose the first one resulting in a power output smaller than d. We continue this process until all batteries have been assigned.